Real Numbers as Well Defined Sets

Question

For every construction of the reals, we define a real number to be some kind of set of rational numbers (such as cuts or sequences).

However, the number of symbols we have to formulate the description of a set is finite (analytic functions, infinite sums, etc), and I assume sets can only be defined as finite strings of logical symbols.

Every number I can think of, including transcendentals, and even the Chaitin Constant, can be described as such.

Where is the fallacy in saying, then, that the real numbers are countable (as, for instance, well defined cuts seem to be)?

Answer 1

The number of describable numbers is countable. But there are some real numbers you cannot write a formula for.

Also, describable numbers is an ill defined concept. You get contradictions along the lines of "the smallest number not describable in less than eleven words." So you have to specify what is an allowable formula. Maybe something like: $x$ is describable if $P(x)$ is a proposition in standard set theory for which it can be proven, using the standard axioms, that there exists a unique real number for which $P(x)$ holds.

Answer 2

The diagonalization argument will then say that any describable sequence of describable real numbers is not exhaustive, because there is a process for converting the description of the sequence to a description of a real number that is not in the sequence.

The collection of all describable reals can be countable or not, and might or might not form a well defined mathematical object, depending on definitions and on the framework in which it is considered (is your mathematics describable-ist or not?). What diagonalization shows is that it is never describably countable.

Answer 3

Let me add something that was overlooked by the other answers.

First of all, the collection of Dedekind cuts itself is definable if we allow second-order quantification. That is, we can write a formula $\varphi(A)$ in the language of $\leq$ such that $A$ is a set of rational numbers and $\varphi(A)$ is true if and only if $A$ is a Dedekind cut (this depends on the flavor you chose for the cuts, if those are sets, or partitions of $\Bbb Q$ etc. in either case you can define what it means to be a cut).

But the fact that we can define what it means to be a cut doesn't mean that every cut is definable. Look at $\Bbb Q$ with the language of $\leq$ with first-order logic. Every element is rational, so to define the rational numbers we only need to write the formula $x=x$. But no element is definable, because $\Bbb Q$ has plenty of automorphisms when only considered as an ordered set.

So even if we consider $\Bbb Q$ in the language of $\leq$, and allow second-order variables with full semantics (i.e. we consider all the subsets of $\Bbb Q$ as our second-order sets), we can still only define what it is to be a cut, not each and every cut for itself.

And if you think about it, it makes sense. What does it mean to be a cut? It really is a conjunction of infinitely many formulas all using parameters. $r$ is the cut between $A$ and $B$ if $r$ satisfies $q<r$ for every $q\in A$ and $r\leq q$ for every $q\in B$. That's the conjunction of $\aleph_0$ formulas.

So while the number of formula which are the conjunction of finitely many formulas (with parameters!) is indeed countable, the number of infinite conjunctions like that is no longer countable.

---

To sum up, your mistakes lie in two crucial points:

1. The fact that the set of cuts is [second-order] definable, does not mean that every cut is definable. Id est, the elements of a definable set need not be definable.

2. Cuts are definable from infinitely many parameters, and there are uncountably many such sets of parameters, each defining a different cut.