# Are the real numbers really uncountable?

Consider the following statement

Every real number must have a definition in order to be discussed.

What this statement doesn't specify is how that loose-specific that definition is. Some examples of definitions include:

"the smallest number that takes minimally 100 syllables to express in English" (which is indeed a paradox)

"the natural number after one" (2)

"the limiting value of the sequence $(1 + 1/n)^n$ as $n$ is moved towards infinity, whereas a limit is defined as ... (epsilon-delta definition) ... whereas addition is defined as ... (breaking down all the way to the basic set theoretic axioms) " (the answer to this being of course e)

Now here is something to consider

The set of all statements using all the characters in the English in English language is a countable set. That means that every possible mathematical expression can eventually be reduced to an expression in English (that could be absurdly long if it is to remain formal) and therefore every mathematical expression including that of every possible real number that can be discussed is within this countable set.

The only numbers that are not contained in this countable set are...

That's a poor question to ask since the act of answering it is a violation of the initial assumption that the numbers exist outside of the expressions of our language.

Which brings up an interesting point. If EVERY REAL number that can be discussed is included here, then what exactly is it that is not included?

In other words, why are the real numbers actually considered to be uncountable?

-
"The set of all statements using all the characters in the English language is a countable set." On what basis do you claim that? – Théophile Jul 14 '14 at 0:48
True: finite words in finite alphabets are countable. That means that one cannot name all real numbers using any finite alphabet and finite words. – Pedro Tamaroff Jul 14 '14 at 0:51
@frogeyedpeas I suppose I allow the possibility of statements with infinitely many words. I got trapped at a store just today with a saleswoman who wouldn't stop talking, and I had to nod and slowly back away. – Théophile Jul 14 '14 at 0:56
@frogeyedpeas No, you're being very sloppy with your definitions. Saying that one cannot name all real numbers using any finite alphabet means some surjection fails to exist, from a set of words $\bigcup_{n\geqslant 0} A^n\to \Bbb R$ in an finite alphabet $A$. In fact, we could even take $A$ to be a countable alphabet. – Pedro Tamaroff Jul 14 '14 at 0:57
Does something have to be expressible in a language in order to exist? – paw88789 Jul 14 '14 at 1:08

"The real numbers are uncountable" means that, in the set-theoretic universe where we have defined "the set of natural numbers" and "the set of real numbers", there is not a function that is a bijection between these two sets.

It means nothing more, and nothing less than that.

There are all sorts of traps, mistakes, and really subtle misunderstandings one can run into by trying to ascribe more meaning to this statement than it actually has.

You may find Skolem's paradox an interesting topic to read about, given that it involves a rigorous and precise way to see the real numbers as countable in a sense different from what is meant by "the real numbers are uncountable", and the consequent difficulties people have trying to unravel what's going on.

-
Yep. Pretty much on the money. +1. – MPW Jul 14 '14 at 1:38
So to dig a bit deeper into this, the real numbers appear to be now no longer "the numbers that include the integers and all that are not the integers but still defined with functions" but rather "a set of numbers that by definition/series-of-deductions cannot be put into one-to-one correspondence with the integers" – frogeyedpeas Jul 14 '14 at 1:42
No: those are the same set. Your fixation on "definition" is the problem, and it is not a requirement of a real number. – trb456 Jul 14 '14 at 2:03
So a real number must not necessarily have ANY definition whatsoever? – frogeyedpeas Jul 14 '14 at 2:06
Yes, an individual real number need not have a definition. But the set of real numbers is guaranteed to contain the limit of any Cauchy sequence, which is the purpose of the real numbers (i.e completeness). It may seem strange that these can coexist, but it is not really a problem. Any situation where you have an application will likely yield a definition of a real. But if working generally, you don't need a specific definition of a real (e.g. sums of limits are limits of sums). This is not a big deal. – trb456 Jul 14 '14 at 2:17

Every real number must have a definition in order to be discussed.

True.

But don't confuse discussing the set of all real numbers with discussing individual real numbers. I can reason correctly about the collection of heads of states of countries without even knowing what countries exist. Similarly I can reason about the set of all real numbers without being able to name every single one.

(But having said that, if you work hard enough you can turn your argument into a bona fide theorem, the downward Löwenheim–Skolem theorem. But it doesn't quite say what you're saying.)

-
I am not content with this yet, because individual real numbers can also be specified. Even ones whose digits cannot ever be known (see the discussion on Vadim's answer regarding a busy-beaver number) so when you say specific real number. I naturally ask "which" but of course you cannot answer that question because to do so you would need to formulate an english-statement which I've already counted. The other avenue then is to prove is that the equivalence of these two sets must create a primitive contradiction (ex: 1 = 0 or there are finite primes etc...) but I can't find one yet. – frogeyedpeas Jul 14 '14 at 2:02
By primitive contradiction, I mean a contradiction to a theorem that is independent of Cantor's |R| > |N| since of course theorems built on this statement would be contradicted but that does not tell us anything new from our premise – frogeyedpeas Jul 14 '14 at 2:03
"Let $x$ be an arbitrary real number ..." can I discuss the properties of $x$, or not? – Asaf Karagila Jul 14 '14 at 7:15
I'm not sure what the issue is @frogeyedpeas . When a mathematician says "there exists an x such that..." they're not saying "there exists an x, with definition Y, such that...". If you want to, you can study numbers with this property but that has no bearing on the existence of the other numbers. – Dan Piponi Jul 14 '14 at 15:35
"Every real number must have a definition to be discussed" - why is that the case? – Carl Mummert Dec 15 '14 at 12:38

OP has rediscovered computable numbers. Indeed there are only countably many numbers that can be computed by a terminating Turing machine. The Church-Turing thesis extends this from Turing machines to all algorithmically computable numbers. Hence almost all real numbers are not algorithmically computable. A minority of mathematicians called constructivists reject the existence of non-computable numbers.

-
I am familiar with this concept. So is it fair to say then that by definition a non-computable number cannot have a definition in the English language that refers to it? I would like to ask if the following is at all relevant? a number defined as "this number is 0.0 followed by the sequence of digits formed by the values of the busy beaver function evaluated at N = 0 to infinity" the church turing thesis states this number is non-computable yet I am able to still specify this number through this finite language – frogeyedpeas Jul 14 '14 at 1:35
The English language is vague and difficult to prove things about; this is why logicians construct formal objects and definitions, such as computable numbers. It is certainly true that one may describe in English certain reals that are non-computable. – vadim123 Jul 14 '14 at 1:47
You are mistaken about the position of constructivists. If there are any mathematicians who reject non-computable reals, it would maybe be the Russian constructivists specifically. But there are plenty of other constructivists who say no such thing. – Andrej Bauer Aug 3 '14 at 17:36
There is a gap between “computable” and “definable”(the latter is weaker/broader); it’s very poor to ignore this distinction while pretending to be an expert. – Incnis Mrsi Dec 15 '14 at 14:37

This question is really much more of a philosophy question, but I do think it is an important. I'd like to ask you two questions in return, "Do you believe that powersets exist? And do you believe we can talk about the set of natural numbers?" Using your definition, we can essentially describe every natural number. We say, $0$ is the smallest natural number, $1$ is the successor of 0, and so on. Now, if you don't believe that we can talk about the set containing $all$ natural numbers, namely $\mathbb{N}$, then my argument dies here. But I am not a finitist (at least not yet) and so I think we can talk about $\mathbb{N}$.

I also believes that powersets exist. Now, Cantor showed that no set has the same cardinality as its powerset (which is actually not a hard proof). Also note, that it is not difficult to show that there is a (natural) one-to-one correspondence between $\mathbb{R}$ and $P(\mathbb{N})$. Hence, $|\mathbb{R}|=|P(\mathbb{N})| >|\mathbb{N}|$. Therefore, if you believe in powersets and infinite sets, you must believe that there are sets which are uncountable. Since the real numbers are in bijection with an uncountable set (namely $P(\mathbb{N})$), they too must be uncountable.

Now I will get to your question: "What exactly is not included?". Note that since we can only describe countably many mathematical sets, we can only describe countably many subsets of $\mathbb{N}$. Therefore, we can only describe countably many elements of $P(\mathbb{N})$. These are known as the computable sets. Now, we can define some real numbers which are non-computable, but "most of" the real numbers we do know are computably defined (by looking at the pre-image of the one-to-one correspondence).

-
I believe power-sets exist but I do not see why a power set of an infinitely large set must necessarily be on another cardinal order. Could you link me a proof? – frogeyedpeas Jul 14 '14 at 1:21
@frogeyedpeas: Sure, here you go - proofwiki.org/wiki/Cantor%27s_Theorem – Kyle Gannon Jul 14 '14 at 1:22
So what appears to be the case is that there is nothing we can actually examine logically that isnt in the countable set mentioned in my question, but somehow the real numbers still contain something. Ie: objects outside of the scope of that which can be logically examined ever. Which brings up the philosophical point " does an idea that never be thought formally exist?" which i'll agree seems better suited for a philosophy stack exchange – frogeyedpeas Jul 14 '14 at 1:28
The canonical non-computable number is one whose digit values depend on whether certain programs halt or not. Since we can't work out certain digits, we can't approximate it to arbitrary precision, which is the definition of a computable number. For certain values of "we" of course, probably a Turing machine ;-) – Steve Jessop Jul 14 '14 at 3:15
@frogeyedpeas: yes, the countable "set" of numbers that you're talking about is not identical to the countable set of computable numbers. I say "set" in snigger quotes because you're speaking English, and the axiom schema of separation of course doesn't really let us define sets using English. So as you've already identified, the definitions you're talking about include some that are paradoxical. But regardless of which definitions "make sense" and truly have a corresponding number, they're countable ;-) – Steve Jessop Jul 14 '14 at 3:25

What you are saying basically boils down to the statement that there are real numbers which have no finite description, which makes a lot of sense given that they are described infinite strings of digits. It doesn't sound that surprising when you put it this way.

-
No its a bit subtler than that. Every infinite string we can conceive of can be meta-stated using english. There is an example in the comments but I will bring it here for convenience: consider 0.1010010001... which is spaced with a sequentially increasing string of 0's and then a 1. that can be restated as "0.1 followed by k 0's and then a 1 with k starting at 1 and incrementing by 1 each time this rule is applied" now i have locked in a pattern. In fact every real number for which we can list a decimal expansion is by definition a computable real the set of which is countable – frogeyedpeas Jul 14 '14 at 1:59
One may naturally respond to this as (well what if we instead did...) and the key is that every statement that can be made is still counted in my set so there is no single number that can be given as a counterexample. The only way to go about this is to prove that some fatal contradiction (ex: 1= 0, primes are finite, Fermat's is true etc..) occurs or that to decide one way or another about this statement is outside the realm of provability – frogeyedpeas Jul 14 '14 at 2:06
Of course you can't describe a number that can't be described finitely. But you can deduce the existence of such numbers. Just because a treasure chest is buried underground and you can't see it with your eyes doesn't mean it's not there. – Grumpy Parsnip Jul 14 '14 at 2:08
Just because some real numbers admit a finite description, such as the example you give with a "locked in pattern," doesn't mean they all have such a description. As you mention, you can deduce the existence of examples with no finite description logically. – Grumpy Parsnip Jul 14 '14 at 2:10
Ah, the key is that not just one number has been connected to this statement, but infinitely many. You could pick one number, but you still have infinitely many more that have no description, and if you are restricting to a language where every sentence has exactly one meaning, you can't use this trick again to get a new number without adding more verbiage. – Grumpy Parsnip Jul 14 '14 at 2:14

The countably infinite set $c{\mathbb R}$ of computable real numbers is difficult to define and to handle. But it is embedded in the uncountable set ${\mathbb R}$ which is easy to handle and is characterised by a small set of reasonable axioms. Beginning with data from $c{\mathbb R}$ we freehandedly argue in the environment ${\mathbb R}$ and arrive at "guaranteed" elements of ${\mathbb R}$ (solutions of equations, as $x=\tan x$, etc.) that are at once accepted as elements $c{\mathbb R}$.

-
This doesn’t address the question “why are the real numbers actually considered to be uncountable?” and may serve only as an obfuscation of the real problem. Set-theoretical embedding, as a concept, is on bad terms with computability theory – that’s the source of paradoxes, not perceived “difficulty to define and to handle” computable elements. – Incnis Mrsi Dec 15 '14 at 10:04

Almost every real number is undefinable (roughly meaning that you can't write down a formula for it). The fact that there are "so many" real numbers depends on properties such as the least upper bound property. What's responsible for this ultimately is the fact that the background logic includes the law of excluded middle, accompanied by the classical interpretation of the existence quantifier. Having said that, in constructive mathematics there is an analogue of Cantor's diagonalisation argument.

In more detail, the various characterisations of the reals are going to be equivalent only in the context of classical logic. In constructive mathematics the least upper bound property fails; see for instance Bishop's book, page 4. When classical logic is the background logic, what is responsible for the uncountability of the reals is the "presence" of undefinable real numbers. The OP was obviously puzzled by this: how can a number exist if you can't specify it at all?

In fact, such "numbers" don't "exist" in a constructive setting. From the constructive viewpoint, their dubious "existence" is wholly dependent on an unbridled application of the law of excluded middle, rejected by constructivists (again with the proviso that Cantor's diagonalisation argument remains meaningful in a constructive setting as well; see Bishop's book).

-
The background logic of what? I do not need excluded middle and proofs by contradiction to define real numbers. I need it only for some “fine” results in analysis. – Incnis Mrsi Dec 15 '14 at 9:57
@IncnisMrsi, Well, you can define the real number system as a whole, but "how many" real numbers there are, so to speak, depends on whether your framework is constructive or not. – user72694 Dec 15 '14 at 14:50
Please, edit your answer to avoid suggestion that excluded middle is a critical requisite of the concept of real numbers. – Incnis Mrsi Dec 15 '14 at 15:02
@IncnisMrsi, that depends on what you mean by the real numbers. Do your real numbers satisfy the least upper bound theorem? – user72694 Dec 15 '14 at 15:39
“My” basic concept of real numbers, possibly, depends neither on set theory nor on second-order logic. Can you explain better what is “upper bound theorem”? – Incnis Mrsi Dec 15 '14 at 19:49

Yes, there is an unrefutable argument that $2^ω$ is not countable, namely Cantor’s diagonal argument mentioned by @user72694. What exactly this argument says? Apart of the rest of set theory, as well as confusions between a theory and metamathematics; see @Hurkyl’s answer for analysis. Cantor’s diagonal argument shows that a surjective mapping from $\mathbb N$ to $2^{\mathbb N}$ is impossible. It is also obvious that an injective mapping from $\mathbb N$ to $2^{\mathbb N}$ is possible. What follows from it?

Under assumptions of set theory, there is further conclusion that $2^{\mathbb N}$ is greater than $\mathbb N$. Most mathematicians, especially those working in analysis and probability theory (due to measure theory), deem it intuitive.

Computability theory offers an opposite intuition for the same Cantor’s diagonal thing: we can’t enumerate all infinite binary sequences. It is dubious that there are more such sequences than natural numbers – isn’t the set of all algorithms countable? We do not know which of them is “greater”, but we definitely see that $2^{\mathbb N}$ is more complex because we can easily embed $\mathbb N$ to it, whereas impossibility to map $\mathbb N$ onto $2^{\mathbb N}$ (both “to map” and “$2^{\mathbb N}$” in the computable sense) leads to Turing’s halting problem.

Whether $2^ω$ is “greater” than $ω$ or just “more complex” depends on whether do we trust set theory or computability theory – the two present conflicting and intuitively incompatible narratives. Resolution of the problem pertains to philosophy.

I, Incnis Mrsi do not discuss real numbers, but due to binary fractions the difference between it and $2^{\mathbb N}$ (infinite binary sequences) is insignificant. Feel free to edit the post to fill it.

-
Users telling well-known ZFC trivia (and even without referring to ZFC or where did they get it) receive upvotes, whereas this text received a downvote instead of fixing problematic parts (if there are). Trying to request help from competent guys… – Incnis Mrsi Dec 15 '14 at 19:38