I am thinking about the Wikipedia (I understand disputed) article about “definable real numbers”.

It begins to say that,

A real number $a$ is first-order definable in the language of set theory, without parameters, if there is a formula $φ$ in the language of set theory, with one free variable, such that $a$ is the unique real number such that $φ(a)$ holds in the standard model of set theory (see Kunen 1980:153).

Later the article reads,

..most real numbers are not definable: the set of all definable numbers is countably infinite (because the set of all logical formulas is) while the set of real numbers is uncountably infinite (see Cantor's diagonal argument). As a result, most real numbers have no description (in the same sense of "most" as 'most real numbers are not rational').

I now place myself in the late 19 century, i.e. without access to language of set theory, and look at the concepts mentioned, countable and uncountable, simply in order to grasp a little of the discussion. (I am aware that this amateurish activity is not popular on this site and usually renders minus points, but I would still like to know a little of the discussion and I see no other way without set theory knowledge.)

I interpret the sequence the above sequence “the set of all definable numbers is countably infinite (because the set of all logical formulas is)” as follows:

The collection (perhaps: the set) of all limits of Cauchy sequences given e.g. as the limit of the sum of all infinite polynomials of $p(\frac{1}{n})$ with rational coefficients will be countable and therefore in a one-to-one correspondence with all other countable collection of numbers (sets?), perhaps (?) including the “set of all logical formulas”. For this reason it is similar to my intuitive understanding of “definition”, including a result of anything that can be constructed with a finite set of instructions.

I now consider this set (?) the definable real numbers, this time not defined by set theoretical terms, just by my simple Cauchy limits.

I now arrange my countable set to by subject to Cantor’s diagonal argument comparing places in a representation in a base. (I understand that this was not Cantor’s original version of the proof, but I assume it is still valid). Cantors proof gives, for the number of the nth place of the representation, a different alternative number and shows that a number $x$ exists which is not in the countable sequence. This process can be done in any base, and it can be done in a way that determines the representation of $x$. I believe in base 2 there will only be one alternative for the nth place, so the countable sequence will uniquely determine the number $x$.

My point is now that Cantor´s way of working amounts to a finite set of instructions in itself, producing a new number $x$ which is not part of the countable numbers which are the numbers that could be defined in a finite set of instructions. This therefore points to a contradiction of at least of my concept of “definition”. Does this sound reasonable and correct to you?

  • 1
    $\begingroup$ you might be interested in the concepts of computable and elementary real numbers, see section 2 of this paper arxiv.org/pdf/0805.0349v1.pdf $\endgroup$ – Vincent Oct 14 '15 at 14:43
  • $\begingroup$ Misleading title. This article/question would needlessly confuse any beginner. IMHO the notion of a "definable" number is a dead end. A better title might be "Are undefinable numbers for real?" -- something that would indicate the speculative nature of this "question." $\endgroup$ – Dan Christensen Oct 14 '15 at 16:20
  • $\begingroup$ That Wikipedia article has gots to get gone. $\endgroup$ – Asaf Karagila Oct 14 '15 at 17:44

If I understand your point correctly, you're saying that the diagonal argument shows that the set of definable reals cannot be countable.

The error in the argument (or at least an error) is this: To get that "diagonal number" $x$ you first list the definable reals in a sequence. For this to show that $x$ is definable the ordering of the sequence must be definable. But it's not. (You don't have a proof that the ordering is definable, and in fact the contradiction you erroneously derive shows that it is not.)

I like to put it this way: The definable reals are countable, but they are not "definable countable".

Ok, here's a way to define an ordering on the set of definable reals. We can define an ordering on the set of all formulas. Go through that list of formulas and cross off all the formulas that do not define a real.

That must be wrong. It's wrong because the condition "$\phi$ defines a real" is not decidable. (Proof: It must not be decidable, or else we'd have a contradiction...)

  • $\begingroup$ I must admit I thought that countable also meant that they could be placed in an order. I have seen a scheme of ordering of the rational numbers going in a zigzag out from (0,0). $\endgroup$ – Mikael Jensen Oct 14 '15 at 14:51
  • $\begingroup$ It does mean that they can be placed in order (meaning that there is a bijection with $\Bbb N$). The problem is that the order is not definable, hence the number $x$ that the diagonal argument gives you is not necessarily definable... $\endgroup$ – David C. Ullrich Oct 14 '15 at 14:57
  • $\begingroup$ I see your point. It feels like he axiom of choice backwards. You get a number but you don't what it is. But it was worth a try. $\endgroup$ – Mikael Jensen Oct 14 '15 at 19:42
  • $\begingroup$ I suspect that Tarski's Undefinability Theorem says something about this question, but I don't know enough logic to know what it says. Maybe "definable real" is something that can only be defined from "outside the universe"? Anyway, I think I read someplace (maybe here an math.stackexchange) that it's possible that every real number is definable? $\endgroup$ – bof Oct 15 '15 at 8:27

I think you have misunderstood the idea: descriptions are sentences of finite length. Then saying that the set of descriptions is countable is (via a fairly messy injection) actually much the same statement as that finite sequences of natural numbers are countable (basically, label all your symbols with natural numbers, then map the statement onto the corresponding finite sequence of them written in some order). And using a Cantor diagonalisation on this doesn't work, because it only produces infinite sequences of naturals.

On the other hand, the problem with using Cauchy sequences to define the reals is that there are loads of them that converge to "the same real number". Think of the infamous $0.99999\dotsm=1$ argument: I can change as many terms in that sequence as I like, and still set it up to have $1$ as its limit.

  • $\begingroup$ I did think about that issue (0.99999..) but I though that if you disregard the sequences with the same limits you would stil have an infinite number of numbers left. $\endgroup$ – Mikael Jensen Oct 14 '15 at 14:55

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.