# Intuitive reconciliation between Dedekind cuts and uncountable irrationals

I've looked around, haven't found a good explanation of this one.

Basically, I'm looking for the simplest route to get from these starting points:

• The set of all rational numbers is countably infinite
• There exists a set of rational numbers A such that all members of A are less than x, and A has no greatest element.

To this end point:

• The set of all irrational numbers is uncountably infinite

I've seen various people trying to argue that this is a contradiction. I am not one of those people.

I'm just looking for clarity on how you go about getting from the countable, dense set of rationals to the uncountable, dense set of irrationals with these starting points.

I'm familiar with other means of getting to the uncountability of the reals, which combined with the countability of the rationals demonstrates that the irrationals are uncountable. Just looking for how you get to that point using these starting points.

• You could inject ${\cal P}(\Bbb N)\setminus{\cal P}_{\rm fin}(\Bbb N)\to \Bbb R$ via continued fractions. – arctic tern Jul 24 '16 at 3:02

Here's a reasonably direct way that doesn't require developing arithmetic or limits in $\mathbb R$, or even arithmetic on $\mathbb Q$, if only we know that $\mathbb Q$ is densely ordered in the sense that for any $a<b$ there exists at least one $c$ with $a<c<b$.

First, since we already know that $\mathbb Q$ is countable, fix a bijection $\psi:\mathbb N\to\mathbb Q$. (I'm assuming $0\notin\mathbb N$, for notational convenience).

Lemma. Let $f$ be any function $\mathbb N\to\mathcal P(\mathbb Q)$. Then there exists an $A\in\mathbb R$ such that $A$ is not in the range of $f$.

Proof. Set $a_0 = 0$, $b_0 = 1$, and define a sequence of pairs of rational numbers $(a_n,b_n)$ by doing the following for $n=1,2,3,\ldots$:

• Let $I_n = \{q\in\mathbb Q \mid a_{n-1} < q < b_{n-1}\}$ and $B_n = f(n) \cap I_n$.
• If $B_n$ is nonempty, then let $a_n=a_{n-1}$ and $b_n = \psi(\min\psi^{-1}(B_n))$ -- that is the first rational number in $B_n$, according to the enumeration $\psi$.
• Otherwise, let $a_n = \psi(\min\psi^{-1}(I_n))$ and $b_n=b_{n-1}$.

We see that $a_0 \le a_1 \le a_2 \le \cdots$ and $\cdots \le b_2 \le b_1 \le b_0$, and that $a_n<b_n$ for every $n$. Now let $$A = \{ q\in \mathbb Q \mid \exists n: q<a_n \}$$

It is easy to verify that $A$ is a Dedekind cut. Furthermore, every $f(n)$ is different from $A$. Namely: if $B_n$ was nonempty, then $f(n)$ contains $b_n$, but $A$ doesn't. Otherwise, $A$ contains a number between $a_{n-1}$ and $a_n$, but $f(n)$ doesn't.

End proof.

Now, to see that there are uncountably many irrationals, let $g:\mathbb N\to\mathbb R$ be any countable sequence of (Dedekind representations of) irrational numbers. We must then find an irrational number that is not in the range of $g$.

Consider the function $$f(n) = \begin{cases} g(n/2) & \text{when n is even} \\ \text{the Dedekind cut for }\psi(\frac{n+1}{2}) & \text{when n is odd} \end{cases}$$ The range of $f$ is the range of $g$ together with all of the rational numbers. So when the Lemma gives us an $A$ that is not in the range of $f$, then this $A$ is (1) irrational, and (2) not in the range of $f$, as required.