# The Axiom of Choice and definability

I've seen a lot of relations between the notion of the existence of a definable set with a given property and the necessity of AC is proving that there is a set with the property. For example:

• Under ZFC, the reals can be well-ordered, and under ZF, it is consistent that the reals cannot be well-ordered. There is no definable well-order of the reals.
• Under ZFC, there is a Lebesgue-nonmeasurable set, and under ZF, it is consistent that every subset of the reals is Lebesgue-measurable. There is no definable Lebesgue-nonmeasurable set.

How does one formalize or prove this relationship, either in general or for particular cases such as these? It makes some intuitive sense to me that the sets described in the axioms of ZF can all be described via comprehensions (i.e. $\bigcup X=\{x|\exists y\in X:x\in y\}$, $\{a,b\}=\{x|x=a\vee x=b\}$, $f(X)=\{x|\exists y\in X:x=f(y)\}$, and so on), while the choice function described in AC is inherently not definable given only its domain, so facts which are provably dependent on AC must also inherit this nonconstructive nature, but I have no idea how to prove any of that.

• There is a definable relation on the real numbers that is provably a well-ordering if we assume $V=L$, for example. This relation is $\Delta^1_2$, by the way, which is fairly close to being a Borel set - which is definable too. If I am not mistaken this set is also non-measurable. Apr 25, 2013 at 8:58
• That statement is quite a revelation, if I understand you correctly. Are you saying that there is an explicit formula that describes a well-order of the reals? Even under $V=L$, I don't understand how that could be possible. What is the formula? Apr 25, 2013 at 9:04
• There is an explicit formula which well-orders the universe under $V=L$. We then restrict it to the real numbers, and we're about done. Apr 25, 2013 at 9:04
• Ah, I see. So, what's the first real number? Apr 25, 2013 at 9:07
• Well, it's not like I had any idea how you define the real numbers and in what sort of manner you wish to represent them. Even as Dedekind cuts the answer is still somewhat ambiguous, how do you represent the rational numbers? The integers? And so on. Apr 25, 2013 at 9:29

In fact ZF also has non-definable sets. All you need is that classical logic holds and that it is a subtheory of ZFC.

Let $\phi(x)$ state that $x$ is a set that is a well ordering of the reals if a well ordering of the reals exists. By excluded middle there is such an $x$, because if there is a well ordering of the reals, we can use that, and if there is no well ordering of the reals we can take anything (the empty set, say). So we know that $ZF \vdash (\exists x)\phi(x)$.

Suppose that we can define such an $x$. Formally this means that there is a formula $\psi$ such that $ZF \vdash (\exists ! x) \psi(x)$ and $ZF \vdash (\forall x)\psi(x) \rightarrow \phi(x)$. Since ZF is a subtheory of ZF we also have the same for ZFC. That is, $ZFC \vdash (\exists ! x) \psi(x)$ and $ZFC \vdash (\forall x)\psi(x) \rightarrow \phi(x)$. But ZFC proves that there is a well ordering of the reals, so in ZFC, $\phi(x)$ is logically equivalent to the statement that $x$ is a well ordering of the reals. Therefore $\psi$ must define in ZFC a well ordering of the reals and we get a contradiction.

So any classical subtheory of ZFC has "undefinable sets," but like Asaf Karagila says, there are extensions of ZFC where every set is definable. The axiom $V = OD$ is sufficient to do this (which is implied by the axiom $V = L$ that Asaf mentioned). The idea behind this is that you construct sets in a well behaved way and the "definition" of, say, the well ordering of the reals would be "the first well ordering of the reals that is constructed."

• Nice answer. How do you show that $\psi$ cannot define in ZFC a well-ordering of the reals? May 4, 2013 at 20:55
• @Jacob It is a standard theorem in set theory. IIRC there is quite a nice proof in Boolean Valued Models by Bell, but it probably also appears in the standard set theory texts (Kunen, Jech, etc).
– aws
May 4, 2013 at 21:01
• The idea of the proof is that you define a particular boolean valued model using a boolean algebra with lots of automorphisms. You show that definable sets in the model are fixed by all automorphisms and that you can construct a real in the model that is not fixed by all automorphisms.
– aws
May 4, 2013 at 21:09
• @Jacob: It's somewhat of a technical construction, but it's a very standard one. In fact this was the second independence result in $\sf ZF$, right when Cohen came up with forcing. The idea is that we add enough generic reals to the universe, and then we reduce to an inner model in which choice fails. I actually wrote a couple of answers which are introductory to symmetric extensions, and permutation models on this very site. If you are familiar with forcing then you can find my thesis on my home page (in my profile) where there is a basic introduction to symmetric extensions by forcing. May 5, 2013 at 0:28

Here is how I would formalise the notion of definability.

Definition. Let $\phi\left(x\right)$ be a formula in the language of set theory (with the unique free variable $x$), and let $\mathsf T$ be a set of sentences in the language of set theory (usually $\mathsf{T=ZF}$ or $\mathsf{T=ZFC}$). We say $\phi\left(x\right)$ defines a set in $\mathsf T$ iff $$\mathsf T\vdash\exists !x\phi\left(x\right).$$ Here, $\exists !x\phi\left(x\right)$ is an abbreviation for a formula meaning "there is a unique $x$ such that $\phi\left(x\right)$".

Example. The formula $\forall y\left(y\notin x\right)$ defines a set in $\mathsf{ZFC}$.

Definition. First note that if $\phi\left(x\right)$ defines a set in $\mathsf T$, then by adding some constant symbol $c$ to our language and the axiom $\phi\left(c\right)$ to $\mathsf T$, we obtain a conservative extension of $\mathsf T$. I will then say that $c$ is a constant term for $\mathsf T$ and that $\phi\left(x\right)$ defines $c$ in $\mathsf T$.

Example. The formula $\forall y\left(y\notin x\right)$ defines $\emptyset$ in $\mathsf{ZFC}$. Similarly, if $c$ is a constant term for $\mathsf{ZFC}$ then so are $\bigcup c$, $\mathcal P\left(c\right)$ and $\left\{x\in c:\psi\left(x\right)\right\}$. This allows us to use $\emptyset$, $\bigcup$, $\mathcal P$ and set-builder notation as we normally would when working in $\mathsf{ZFC}$.

Here is how I would try to describe the difference between Choice and the other set-building axioms in this setup. First consider any set-building axiom of $\mathsf{ZF}$, i.e. anything except Extensionality or Foundation. It is an exercise to see that the axiom can be written in the form $\forall y_1,\dots,y_n\exists x\varphi\left(x,y_1,\dots,y_n\right)$, where $\mathsf{ZF}\vdash\forall y_1,\dots,y_n\exists !x\varphi\left(x,y_1,\dots,y_n\right)$ (note the "!" here). (Technically, Infinity is not of this form in its usual formulation, but it can be replaced an axiom defining $\omega$ in $\mathsf{ZF}$.) Hence if $c_1,\dots,c_n$ are constant terms for $\mathsf{ZF}$, then $\varphi\left(x,c_1,\dots,c_n\right)$ defines a set in $\mathsf{ZF}$. However, if $\mathsf{ZF}$ is replaced by $\mathsf{ZFC}$, then this argument clearly breaks down.

I think it is in this sense that definability corresponds to not needing the axiom of choice. However, one might also try to formalise this idea as follows.

Conjecture. If $\phi\left(x\right)$ defines a set in $\mathsf{ZFC}$, then $\phi\left(x\right)$ defines a set in $\mathsf{ZF}$.

One could also interpret this as saying that "the axiom of choice does not help with uniqueness proofs". However, it is false (assuming that $\mathsf{ZF}$ is consistent).

Counterexample. Let $\phi\left(x\right)$ be the formula meaning "$x$ is an initial ordinal (i.e. well-orderable cardinal), and for every infinite set $y$ there is an injection $x\to y$". Clearly $\mathsf{ZF}\vdash\left(\exists x\phi\left(x\right)\right)\Leftrightarrow\phi\left(\omega\right)$, and $\mathsf{ZFC}\vdash\phi\left(\omega\right)$. But (providing we formalise the notion of "infinite set" appropriately, and assuming that $\mathsf{ZF}$ is consistent), $\mathsf{ZF}\not\vdash\phi\left(\omega\right)$. Hence $\phi\left(x\right)$ defines $\omega$ in $\mathsf{ZFC}$ but does not define a set in $\mathsf{ZF}$.

• You link to MathOverflow, but in fact on this very site the question "$X$ is infinite if and only if $\aleph_0\leq|X|$, without the axiom of choice" was asked several times on this very site. May 4, 2013 at 18:38
• @Asaf Please could you recommend a more appropriate link? I'll happily edit it in. May 4, 2013 at 18:42
• Pick your pick: math.stackexchange.com/q/247164/622 and math.stackexchange.com/q/235653/622 and math.stackexchange.com/q/308342/622. I recall discussing it on several other places a well, but those three should suffice for starters. May 4, 2013 at 18:48
• My gut feeling is that your "Theorem" is false, because the same kind of reasoning can be used to "deduce" the axiom of choice. (See, for instance, the derivation of AC in Martin-Löf type theory.) May 4, 2013 at 19:19
• The inductive step is far too vague. Here is one problem: in the set-forming axioms, one can use parameters, so the "constant" terms must have variables. But once you allow that, then one can derive a form of meta-AC: suppose we have a proof of $\forall x . x \in X \to \exists y . y \in x$; then we can construct a definable term $c (x)$ such that $\forall x . x \in X \to c (x) \in x$; then by replacement, $\exists f . (f : X \to \bigcup X) \land \forall x . x \in X \to f (x) \in x$. May 4, 2013 at 20:13