Why is this contradiction using axiom of constructibility incorrect?

Question

Today I thought of this paradox and I'm trying to find the wrong assumption that causes it. Does anyone know what is wrong in the following argument:

let $$A=\{x\in \mathbb{R}|\exists\phi:\forall a\neq x: \phi(x)=true \wedge \phi(a)=false\}$$ where $\phi$ is a formula with one free variable

Gödel proved that there exist a specific well-ordering on a subset of $\mathbb{R}$ in ZFC and showed under the axiom of constructibility that this subset is $\mathbb{R}$. Denote that ordering "$\leq$"

Now consider the set $\mathbb{R}\smallsetminus A$. It has a unique least element $e$ under "$\leq$" which satisfies $$\phi(x):=(x\in\mathbb{R}\smallsetminus A) \wedge (\forall y \in \mathbb{R}\smallsetminus A:x \leq y)$$ so $e\in A$ which is a contradiction.

Thanks in advance.

Answer 1

There are a couple steps in your argument that are broken. (For simplicity, let's just assume at the outset that we're working in a model of $ZFC+V=L$.)

• The set $A$ is defined by quantifying over formulas. This can't be done in first-order logic. So, we can't talk about $A$ directly, necessarily. In particular, the formula "$x$ is the $\le$-least element of $\mathbb{R}-A$" isn't a first-order formula, and so can't be used to show that $x$ is in $A$. This is related in spirit to the Berry paradox (https://en.wikipedia.org/wiki/Berry_paradox). You have to be careful when talking about definability!

• A more minor objection: You assume that $\mathbb{R}-A$ is nonempty. How do you know this? In fact, this is not necessarily true - see http://arxiv.org/abs/1105.4597.

Answer 2

This is a common misunderstanding of what does it mean for a real number to be definable.

There are one of two possible mistakes here:

1. $\phi$ is a formula in the language of set theory. But then you can't quantify over it, because $\phi$ is not an object of the universe of set theory, it is an object of the meta-theory.

2. $\phi$ is limited to some structure defined using $\Bbb R$ (first, second, whatever order field axioms with some additional functions or operators as you'd like).

   In that case, either you end up being able to define every real number, or you found a real number which is not definable in this given structure, which gives it a definition outside the structure. Namely, you've shown that the first real number which is not definable in this structure, is in fact definable in the full universe of sets.

   This is not a contradiction to anything. Just like no element of $\Bbb Q$ is definable as a linearly ordered set, but of course that you can do some sort of parameter free definition of $\Bbb Q$ which gives you some canonical enumeration and therefore you can pick the least rational in that enumeration. This is not a definition over a linearly ordered set anymore.

It should also be pointed out that despite this being a misunderstanding, there are in fact models where every real number is definable (in the global sense of the word, namely you are allowed to use the entire set theoretic universe for the definition).

Answer 3

You say: Let $$A=\{x\in \mathbb{R}|\exists\phi:\forall a\neq x: \phi(x)=true \wedge \phi(a)=false\}$$ where $\phi$ is a formula with one free variable.

Consider this: For each $x$ you can always choose $\phi(y)$ to be the simple formula $y = x$. Then $\phi(x)$ is $x = x$, which is $true$, while for $a \neq x$, $\phi(a)$ is $a = x$, which is $false$.

This implies $A = \mathbb{R}$. So your final argument cannot be carried out, because the difference set is actually empty.