# 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 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 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 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 at 0:57
Does something have to be expressible in a language in order to exist? –  paw88789 Jul 14 at 1:08

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 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 at 2:03
"Let $x$ be an arbitrary real number ..." can I discuss the properties of $x$, or not? –  Asaf Karagila Jul 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 at 15:35

"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 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 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 at 2:03
So a real number must not necessarily have ANY definition whatsoever? –  frogeyedpeas Jul 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 at 2:17

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 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 at 1:47

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 at 1:21
@frogeyedpeas: Sure, here you go - proofwiki.org/wiki/Cantor%27s_Theorem –  Kyle Gannon Jul 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 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 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 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 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 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 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 at 2:10
I meant to get more general than that "number without finite description that obeys x" is a statement that can be made and such a number has now been connected to. We are basically attempting to prove there exist numbers without finite descriptions that do not have any property that can be discussed finitely –  frogeyedpeas Jul 14 at 2:12