# Proof of uncountability of irrationals without using completeness of real numbers

I am studying countable sets and every proof of uncountability of real numbers uses completeness property? I know completeness is required to define irrtionals and real numbers, but if one considers irrational numbers or assigning a Dedekind cut of rational numbers to each irrational number or calling irrational numbers as gaps between rational numbers, can it be proved that those gaps are uncountable? Using nested interval theorem or decimal representation and other such proofs use completeness inherently. It is my understanding that completeness talks about ordering of elements, and countability is about cardinality of set

• Use Lebesgue measure. – GNUSupporter 8964民主女神 地下教會 May 6 '18 at 15:02
• When you write about completeness, what you have in mind is the fact that the reals form a complete ordered field? – José Carlos Santos May 6 '18 at 15:05
• There are incomplete extensions of the rational numbers (e.g., the field of real algebraic numbers) that are still countable. – Hagen von Eitzen May 6 '18 at 15:20
• The definition of the reals requires completeness so proving ANYTHING about the reals (specifically) will implicitely involve completeness. – fleablood May 6 '18 at 15:32
• Well, define the irrational numbers as the members of $\Bbb{N^N}$, and then it's easy. – Asaf Karagila May 6 '18 at 15:36

Say a Dedekind cut $(A, B)$ is between two irrationals $p<q$ if there are elements of both $A$ and $B$ in the interval $(p, q)$. We now argue as follows:

• Suppose $(A_n, B_n)$ (for $n\in\mathbb{N}$) is a sequence of Dedekind cuts; we want to build a Dedekind cut not in this sequence.

• Fix an enumeration $(s_i)_{i\in\mathbb{N}}$ of $\mathbb{Q}$.

• We define a pair of sequences of rationals $p_i, q_i$ as follows:

• $p_0$ is any element of $A_0$, $q_0$ is any element of $B_0$.

• Having defined $p_i, q_i$, we now define $p_{i+1}, q_{i+1}$ as follows:

• If $(A_{i+1}, B_{i+1})$ is not between $p_i$ and $q_i$, then we pick any rationals $p_{i+1}, q_{i+1}$ with $p_i<p_{i+1}<q_{i+1}<q_i$ with $s_i\not\in (p_{i+1}, q_{i+1})$.

• If $(A_{i+1}, B_{i+1})$ is between $p_i$ and $q_i$, we let $q_{i+1}$ be some element of $A_{i+1}$ in $(p_i, q_i)$, and let $p_{i+1}$ be some rational such that $s_i\not\in (p_{i+1}, q_{i+1})$.

It's an easy exercise to show that this construction does in fact give rationals $p_0<p_1<p_2<...<q_2<q_1<q_0$ and that there is no rational contained in every $(p_i, q_i)$ (think about how we handled $s_i$). Letting $$A=\{s\in\mathbb{Q}: s<p_i\mbox{ for some i}\},\quad B=\{s\in\mathbb{Q}: s>q_i\mbox{ for some i}\}$$ we get that $(A, B)$ is a Dedekind cut not equal to any $(A_n, B_n)$.

Note that what's really going on here is that completeness is essentially built into Dedekind cuts automatically.

A point which may look fishy in the above is the use of arbitrary choices. However, this is really just a device to make the proof more readable, and is easily avoided: we can always just pick an appropriate rational with minimal index according to the enumeration $(s_i)_{i\in\mathbb{N}}$, and such an enumeration can be given explicitly.

• so any definition of irrationals, as gaps or dedekind cuts, or any other form uses rationals too, which means completeness is inherent in the way we define irrationals. So though we are talking about cardinality, the way we defined the set involves completeness. and if we were to call irrationals as power set of naturals, then we could prove uncountability using power set theorem. do I have it right? – jnyan May 7 '18 at 4:53
• Well, if you use the minimal index instead of arbitrary choice, aren't you just moving the arbitrary choice to the enumeration $(s_i)$ instead? – SK19 May 8 '18 at 14:06
• @SK19 My point was about set theory, not style: by "arbitrary choice" I meant "application of the axiom of choice." The point is that in general, any "construction" which has a step like "pick some real number such that ..." is not guaranteed to go through without the axiom of choice; however, since here we're picking rational numbers, we can fix our favorite (totally explicit) well-ordering of the rationals and use that to avoid invoking the axiom of choice. – Noah Schweber May 8 '18 at 14:13

It is impossible to prove that the set of all irrational numbers we can think of (solutions of certain equations, values of special functions at rational points, etc.) is uncountable. There is no way around using some grand view assumption about ${\mathbb R}$. I shall work with decimal expansions, taking it for granted that each infinite decimal expansion gives a unique real number.

The basic fact is that given any set $A$ there is no surjective map $f:\>A\to{\cal P}(A)$. In particular there is no surjective map $f:\>{\mathbb N}\to{\cal P}({\mathbb N})$. As a consequence the set $B$ of binary sequences $$b:\>{\mathbb N}\to\{0,1\},\qquad k\mapsto b_k$$ is uncountable. Given a $b=(b_1,b_2,b_3,\ldots)\in B$ consider the infinite decimal $$\alpha(b):=0.\,b_1\,2\,b_2\,2\,2\,b_3\,2\,2\,2\, b_4\,2\,2\,2\,2\,b_5\,2\,2\,2\,2\,2\,\ldots\ .$$ Since this decimal is not periodic $\alpha(b)$ is irrational; furthermore $b\ne b'$ implies $\alpha(b)\ne\alpha(b')$. It follows that the irrational numbers form an uncountable set.

• This uses completeness when you assign the real number $\alpha(b)$. – fleablood May 6 '18 at 15:34
• @fleablood: I know; but we cannot prove something about "all numbers" without some input. My input was that any real number has a binary expansion. – Christian Blatter May 6 '18 at 15:48

Here's a direct proof that Dedekind cuts of $\mathbb{Q}$ form an uncountable set. All that's happening in this proof is that I'm back engineering the proof that $\mathbb{R}$ is uncountable based on decimal representation, so it's kind of boring and I'll leave some details out. But at least I won't use $\mathbb{R}$ itself, I'll just use an abstraction of "decimal representation".

Just to review, define a Dedekind cut of $\mathbb{Q}$ to be an ordered pair $(A,B)$ of nonempty subsets of $\mathbb{Q}$ such that $B = \mathbb{Q}-A$, and for every $a \in A$ and $b \in B$ we have $a<b$. Define a Dedekind cut $(A,B)$ to be rational if $A$ has a maximum or $B$ has a minimum, otherwise the Dedekind cut $(A,B)$ is irrational. Define an equivalence relation on Dedekind cuts: if $(A,B)$ is irrational it's not equivalent to anything else; if $(A,B)$ is rational then its equivalent to exactly one other, obtained by moving a maximum element of $A$ over to $B$ or a minimum element of $B$ over to $A$.

Consider an infinite sequence of non-negative integers $$(n_i) = (n_0, n_1, n_2, n_3, ...)$$ such that for each $i \ge 1$ we have $n_i \in \{0,1,2,3,4,5,6,7,8,9\}$. For each integer $K \ge 0$ we define the $K$th lower rational approximation of $(n_i)$ to be the rational number $$r_K(n_i) = \sum_{i=0}^K n_i 10^{-i}$$ and we define the $K$th upper rational approximation of $(n_i)$ to be $$s_K(n_i) = r_K(n_i) + 10^{-K}$$

Consider also a Dedekind cut $(A,B)$. We define $(n_i)$ to be a decimal expansion of $(A,B)$ if for all $K$ we have $r_K(n_i) \in A$ and $s_K(n_i) \in B$. One can prove a bunch of things about decimal expansions of Dedekind cuts. For example,

• Every Dedekind cut has a unique decimal expansion (constructed by induction), and the decimal expansion is eventually periodic if and only if the Dedekind cut is rational.
• For any infinite sequence $(n_i)$ as above, either $(n_i)$ is the decimal expansion of a unique Dedekind cut and that cut is irrational, or $(n_i)$ is the decimal expansion of exactly two Dedekind cuts and those two cuts for an equivalent pair of rational Dedekind cuts. Roughly speaking one defines the required Dedekind cut $(A,B)$ by letting $A$ be the set of all rational numbers $r$ such that there exists $K$ satisfying $r \le r_K(n_i)$.

As a consequence of the above two statements, it follows that the set of Dedekind cuts is countable if and only if the set of sequences $(n_i)$ is countable. But now the usual diagonalization argument kicks in, to prove that the set of sequences $(n_i)$ is uncountable.

We have the set of rational numbers $\mathbb Q$ and it has 'gaps'. It can be analyzed as a countably infinite densely ordered set.

Now we can always add in some of those 'missing gaps'. Let $G$ be a countably infinite set of 'gap fixes' for $\mathbb Q$. Then $T = \mathbb Q \cup G$ is another countably infinite densely ordered set. This will never get rid of all the 'gaps' since we have the following (see Back-and-forth method):

Any two countably infinite densely (linear) ordered sets without endpoints are order isomorphic.

Interestingly, fixing a countable number of gaps doesn't make any 'real progress' at all.

So if you believe that the linear ordered set $\mathbb R$ has no 'gaps', then the irrationals must be uncountable.

By the time the OP can make precise mathematical arguments concerning the real numbers and 'gaps', he will no doubt be just as comfortable speaking about the real numbers as connected and/or complete.

The standard argument I know to prove the uncountability of the real numbers shows that $[0,1]$ is already uncountable. This is proved by contradiction, i.e. assuming $[0,1]$ would be countable then the numbers could be enumerated in a sequence and then a number $x$ is constructed that is within $[0,1]$ but not in the sequence, leading to a contradiction. I guess the completeness used here is that $x$ is in fact a real number.

Let's see if we can transfer this proof to the irrationals. Let $a_n$ be an enumeration of $[0,1]\setminus\mathbb{Q}$. Construct $x$ like that: the $n$-th digit $b_n$ of $x$ is defined by $$b_n=\left\{\begin{array}{rl} 1&\text{if n=k! for some k\in\mathbb{N} and n-th digit of a_n is not 1}\\ 2&\text{if n=k! for some k\in\mathbb{N} and n-th digit of a_n is 1}\\ 3&\text{if n\neq k! for all k\in\mathbb{N} and n-th digit of a_n is 4}\\ 4&\text{if n\neq k! for all k\in\mathbb{N} and n-th digit of a_n is not 4} \end{array}\right.$$

(This construction idea is borrowed from Liouville.) To guarantee the existence of $x$, we need the axiom of choice. For one reason or another, the completeness of $\mathbb{R}$ is integrated in the end, because else I couldn't ensure that the constructed $x$ is actually a number. $x$ is definitely not in $(a_n)$ by construction, we can prove this with induction. And finally $x$ cannot be rational, because the distance between a $1$ or $2$ to the next $1$ or $2$ increases evermore (we could have used any superlinear function for that, but $k!$ came from the inspirational source).

• This is wrong. You cannot claim that you can construct your $x$ without essentially the same justification for the typical proof. In both cases, you are defining a sequence of decimal digits and claiming that it is the representation of some real number. So it makes no sense to claim that one requires the completeness of reals but the other does not. – user21820 May 8 '18 at 13:27
• @user21820 Hm, interesting... But aren't I'm rather using the fact that rational numbers can be defined as having a period when written as $\sum_{n\in\mathbb{N}}b^{k-n}a_n$ (with $b,k$ natural, $b > 1$ and for all $n$ holds $0\leq a_n<b$) and irrational numbers being the rest of "numbers", where "number" is any sequence that can be formally written like that? From this point of view I don't use completeness of $\mathbb{R}$ but rather work with the embedding of $\mathbb{Q}$ in the function space $\mathbb{N}^{\{-1\}}\times\{0,...,b-1\}^\mathbb{N}$. Wouldn't you agree? – SK19 May 8 '18 at 14:02
• As I said very clearly, whatever you claim you are using is no less than the standard proof, and that is why your post is wrong. And "1.000.." and "0.999.." are distinct representations of the same real, so you cannot claim that reals are simply 'sequences that can formally be written like that'. You will have a hard time proving the basic properties for reals if you construct it via a syntactic route like that, and arguably any such construction is implicitly based on completeness. If completeness did not hold for reals, it would be impossible to construct them that way! – user21820 May 8 '18 at 15:20
• @user21820 I've tried to tie in your objection into the answer. On the upside, even the accepted answer admits some way of using completeness. Anyway, I'll let my answer stay here because I think a direct proof of the uncountability of $\mathbb{R}\setminus\mathbb{Q}$ has its own merit. – SK19 May 8 '18 at 15:32
• Thank you very much for editing your answer. Indeed, in my opinion every diagonal argument must use completeness at some intrinsic level, because after all the reals are based on that. Please let your answer stay! – user21820 May 8 '18 at 16:33