1
$\begingroup$

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)?

$\endgroup$
9
  • $\begingroup$ Your first sentence is, at best, inaccurate. You must be thinking of Dedekind cuts...? $\endgroup$
    – DonAntonio
    Nov 23, 2013 at 1:50
  • $\begingroup$ en.wikipedia.org/wiki/Definable_real_number $\endgroup$
    – Dustan Levenstein
    Nov 23, 2013 at 1:52
  • $\begingroup$ Per your edit: a sequence of rational numbers is not a set of rational numbers; it is a function $\mathbb N \to \mathbb Q$. $\endgroup$
    – Dustan Levenstein
    Nov 23, 2013 at 1:57
  • 1
    $\begingroup$ I don't think the particular construction of the real numbers used is relevant to your point. $\endgroup$
    – Dustan Levenstein
    Nov 23, 2013 at 2:05
  • 1
    $\begingroup$ @DonAntonio Of course you can define a real number to be the (e.g.) left hand set of a Dedekind cut of the rationals. $\endgroup$
    – Carsten S
    Nov 23, 2013 at 10:34

3 Answers 3

Reset to default
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Related to some of the answers at : math.stackexchange.com/questions/527248/… $\endgroup$
    – zyx
    Nov 23, 2013 at 2:32
  • $\begingroup$ Well no. The number of possible descriptions is countable. So what is ambiguous is not whether the number of describable numbers is countable. Rather it is which descriptions actually describe a real number. For example, your description of a number obtained by the diagonal process is not a proper description until you have told me what counts as a description. $\endgroup$
    – Stephen Montgomery-Smith
    Nov 23, 2013 at 2:47
  • $\begingroup$ Yes, I agree. I used to ponder these kinds of issues for days. I harbour a fantasy that one day ZF will be proven inconsistent (and in a really powerful way that will rule out any sensible set theory), and then these discussions will become moot. $\endgroup$
    – Stephen Montgomery-Smith
    Nov 23, 2013 at 2:54
  • $\begingroup$ One issue for example is whether the definition of "countable" (and the mathematical framework in use) allows a proof that a surjection from $N$ to a set or collection makes it countable. You can enumerate descriptions without being able to describably, or coherently in some other required way, single out the ones that make sense. $\endgroup$
    – zyx
    Nov 23, 2013 at 2:55
  • $\begingroup$ It also makes a difference whether you interpret definable to mean witnessed or unwitnessed existence of the proof (that $x$ is uniquely defined by $P(x)$). The list of properties $P_i$ is countable, but there is no way to place its subset that define unique $x$'s in bijection with $N$, unless each $P$ is packaged together with a proof that it uniquely defines an $x$. $\endgroup$
    – zyx
    Nov 23, 2013 at 4:55
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Yes, I said that in my second paragraph. $\endgroup$
    – Stephen Montgomery-Smith
    Nov 23, 2013 at 2:41
  • 1
    $\begingroup$ After specifying formally what 'describable' means, it is not necessarily true that the set of describable numbers is well defined, that if it is a set it is countable, or that there are real numbers lacking a formula. In that respect it is foundation-dependent. The set of descriptions is certainly countable. $\endgroup$
    – zyx
    Nov 23, 2013 at 2:45
  • $\begingroup$ You can write in ZF: "The set of $x$ for which ...". The only difficult part is showing that this set is not all of $\mathbb R$, because you cannot prove in ZF that ZF is consistent. $\endgroup$
    – Stephen Montgomery-Smith
    Nov 23, 2013 at 2:49
  • $\begingroup$ But if you work in an expanded set theory, namely ZF plus the axiom "ZF is consistent", then the set is well defined, and I can prove it is countable in my expanded set theory. $\endgroup$
    – Stephen Montgomery-Smith
    Nov 23, 2013 at 2:51
  • 1
    $\begingroup$ I don't understand what the consistency of ZF has to do with it. The fact that there are countably many descriptions does not imply that there countably many things so described. If you consider descriptions as objects in the meta-language, it doesn't even make sense to talk about a function from descriptions to real numbers. If you formalize descriptions in set theory, then the naive attempt to form a surjection from the set of descriptions to the set of real numbers so described may fail (because of the undefinability of truth.) $\endgroup$
    – Trevor Wilson
    Nov 23, 2013 at 5:58
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .