Proof of uncountability of irrationals without using completeness of real numbers

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.