Are the real numbers really uncountable?

Question

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?

Answer 1

"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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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}$.

Answer 8

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.