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}$.

  • $\begingroup$ 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. $\endgroup$ – R. Burton Feb 13 at 20:22
  • 1
    $\begingroup$ @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. $\endgroup$ – tempquestionasker Feb 13 at 20:26
  • 4
    $\begingroup$ I don't see why this is even possible? Did you see this claim somewhere? $\endgroup$ – Asaf Karagila Feb 13 at 20:42
  • $\begingroup$ @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. $\endgroup$ – tempquestionasker Feb 13 at 21:10
  • 1
    $\begingroup$ Still sounds suspicious. $\endgroup$ – 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.

  • $\begingroup$ Lost my other account due to computer auto-update, but yes I'm answering my own question. $\endgroup$ – tempquestionasker Feb 14 at 16:04
  • 1
    $\begingroup$ 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? $\endgroup$ – Shervin Sorouri Feb 14 at 16:22
  • $\begingroup$ @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$ $\endgroup$ – tempquestionasker Feb 14 at 16:55
  • $\begingroup$ 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$? $\endgroup$ – Shervin Sorouri Feb 14 at 17:01
  • $\begingroup$ @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. $\endgroup$ – tempquestionasker Feb 14 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.