# Is it always possible to “disintegrate” a set to obtain an uniquely definable total ordering?

This looks like it should be a simple question, but I can't quite do it.

Let $$A$$ be a set in ZFC. So it's well-orderable and in particular there exist total ordering. The question is about uniquely definable total ordering (when talking about definable we allow to use this set $$A$$ as parameter). Now it might be too hard to actually define such a total ordering, so we allow ourselves to "disintegrate" or "unfuzzying" the set first, by making a set $$B$$ and a surjection $$f:B\rightarrow A$$, and require that $$B,f$$ are uniquely definable. Then we could maybe define a total ordering on $$B$$. The question is: can this always be done, and be done uniformly (with $$A$$ as parameter)?

If you want a more technical phrasing of the question, it is as follow. The question is whether there exist a ZFC formula $$\phi(a,b,h,r)$$ with the following property: for any ZFC universe $$\mathcal{U}$$ and any element $$A$$ in $$\mathcal{U}$$, then there exist an unique tuple $$B,f,R$$ in $$\mathcal{U}$$ such that $$\mathcal{U}\models\phi(A,B,f,R)$$, and further more, $$f$$ is a surjection $$B\rightarrow A$$ and $$R$$ is a total ordering on $$B$$.

So anyone help?

If the question were changed to "well-ordering" then the claim should be false, intuitively. Because a well-ordering on $$B$$ induce a definable injection $$A\rightarrow B$$ that is a right inverse to $$f$$, which in turn induce a definable well-ordering on $$A$$. And even though I can't prove it, it seems wrong to be able to define a well-ordering on any arbitrary sets, like $$\mathbb{R}$$.

• Depending on the version of AC you are using, it may be possible to define a well-ordering on (almost) any set. In ZF extended with the axiom of global choice (the usual AC in NBG), "there exists a well-ordering on $A$" is trivial. – R. Burton Feb 13 at 20:22
• @R.Burton:just the version in ZFC. I have heard (but not sure), that under very strong axioms you can literally well-order the entire universe in a definable manner, so picking one object out of anything can be trivially done in a definable manner. – tempquestionasker Feb 13 at 20:26
• I don't see why this is even possible? Did you see this claim somewhere? – Asaf Karagila Feb 13 at 20:42
• @AsafKaragila: I heard something like that during a talk, but I was lost for most of the talk, and only notice because the speaker specifically mentioned that it's a trick to "cheat" and put a total ordering on sets that shouldn't be possible, as long as we accept multiple copies of the same element. But it looks obviously true to me. Intuitively, attach a tag to each element to let us total order them; but the tag isn't uniquely defined so you end up with a bunch of objects in B corresponding to a single object in A. – tempquestionasker Feb 13 at 21:10
• Still sounds suspicious. – Asaf Karagila Feb 14 at 9:49

This is an answer I got from reddit, rephrased in my own words which I think is clearer.

Let $$C$$ be a set of pair of ordinal, then it uniquely defines a (potentially infinite) directed graph, where the vertices are all the ordinals that appeared in a pair, and the directed edges are these pairs. Let this graph be called $$G(C)$$.

The $$\in$$ relation on the transitive closure of $$A$$ form a well-founded graph $$G$$. We can write a formula that restrict our attention to consider only those $$C$$ which defines a graph isomorphic to this $$G$$. The isomorphism is unique as well, since these are well-founded, call it $$g(C):V(G(C))\rightarrow V(G)$$.

Hence once we restrict to all $$C$$ that define a well-founded graph isomorphic to $$G$$, then we have a definable function that pick out an element of $$A$$ for each $$C$$, namely the element correspond (through the unique isomorphism) to the smallest ordinal that is a vertex in the tree. In notation, $$f(C)=g(C)(\min\{\alpha\in V(G(C))|g(C)(\alpha)\in A\})$$

Consider any arbitrary element $$a\in A$$. By axiom of choice we can get a bijection $$A\rightarrow|TC(A)|$$ that send $$a$$ to $$0$$. Let $$G$$ induce a graph through this bijection, we obtain a set $$C$$. Then $$f(C)=a$$ because $$g(C)(0)=a$$ and $$0$$ is clearly the smallest ordinal.

So define our $$B$$ to be the set (easily check to be a set) of all $$C$$ that define a well-founded graph with vertices in $$|TC(A)|$$ only that is isomorphic to $$G$$, and $$f$$ be the $$f$$ above but restricted to $$B$$ so that it's a function. By the argument in the previous paragraph, $$f$$ is surjective.

Now pair of ordinal has a definable well-ordering, by lexicographic ordering. So sets of pair of ordinals has a total ordering, by comparing the minimum elements in each of their differences.

And easily check that the above construction are uniform and work in all ZFC universe.

• Lost my other account due to computer auto-update, but yes I'm answering my own question. – tempquestionasker Feb 14 at 16:04
• Since $A$ may not be transitive, I don't see how the isomorphisms you describe with the $C$'s can be unique. Also even before that, I don't see why there exist such $C$ for any given $A$, e.g. pick some none-empty $A$ such that $\in | A \times A = \emptyset$ , then any $C$ representing such an $A$ must have no edges and by definition can't have any vertices either and then it can't represent the "discrete" set $A$, no? – Shervin Sorouri Feb 14 at 16:22
• @ShervinSorouri: that seems to be a problem, yes. What about instead of $A$ tree we replace it with the graph of its transitive closure - which is uniquely definable from $A$ too? And $C$ only define a well-founded graph, not tree anymore? And when we pick out element from $A$ we look for the smallest ordinal vertex that correspond to an element in $A$ – tempquestionasker Feb 14 at 16:55
• Pardon me, but I don't quite understand your construction. I kinda understand what $B$ is, but I don't know what $f$ does. So can you please explain what $f(C)$ is, for $C \in B$? – Shervin Sorouri Feb 14 at 17:01
• @ShervinSorouri:I fixed the answer above to deal with the errors you pointed out. Anyway, $f$ looks at the vertices of $C$, figure out through the isomorphism which vertices belong to $A$, then pick out the vertices that is minimum (since these vertices are ordinal which is well-ordered), then pick the element of $A$ correspond to this vertex. – tempquestionasker Feb 14 at 17:32