# Proving $\mathbb{R}$ is uncountable using Dedekind cuts?

I'm familiar with several proofs that the real numbers are uncountable (Cantor's initial proof, a proof by diagonalization, etc.). However, I've never seen a proof that the reals are uncountable that proceeds by showing that the set of Dedekind cuts of the rationals are uncountable. I'm aware that the set of all subsets of the rationals is uncountable, but not all of these sets are Dedekind cuts.

Is there a simple proof of the uncountability of $\mathbb{R}$ that works by showing the set of Dedekind cuts is uncountable?

Thanks!

• You show that the set of Dedekind cuts fulfills the premises used in Cantor's proof, i.e. cuts are totally and densely ordered and "cuts of cuts" are already cuts. Commented Sep 25, 2012 at 17:49
• @Hagen: But this is not really to use the Dedekind cuts to prove uncountability, this is to show that Dedekind cuts form a field which behaves like the real numbers, and therefore is uncountable (by other proofs, e.g. the diagonal argument). Commented Sep 25, 2012 at 17:51
• @AsafKaragila: Agreed (though "field" is not needed, only order properties, which is cut-speak for subset relations) Commented Sep 25, 2012 at 17:55

(Fleshing out Hagen's comment): The shortest way from Dedekind cuts to "uncountable" is probably:

First, show directly from the definition that the set of Dedekind cuts is a dense total order under set inclusion, and satisfies the supremum property (namely, the supremum of a bounded nonempty set of cuts is their union).

Then assume that we have some sequence of cuts $r_1, r_2, \ldots$. Our task is to find a cut that is not $r_i$ for any $i$. Define by simultaneous induction two sequences $a_n$ and $b_n$ by:

• $a_0 < b_0$ but they are otherwise arbitrary.
• For $i\ge 1$ select $a_i$ and $b_i$ such that $a_{i-1}<a_i<b_i<b_{i-1}$ and such that $r_i<a_i$ or $r_i>b_i$. It is easy to see that such $a_i$ and $b_i$ always exist at each step. (If you're working without the axiom of choice, first show that the cuts corresponding to the rationals are a countable dense subset and select $(a_i,b_i)$ as the first qualifiying pair of rationals at each stage).
• Finally, our sought cut is the supremum of the $a_i$s. This cannot be any $r_n$, because every $r_n$ is either less than some $a_i$ or greater than some $b_i$, and every $b_i$ is greater than all $a_i$s.

Thus no sequence of cuts contain all cuts, i.e., the set of cuts is not countable.

• Isn't this essentially equivalent to constructing the real numbers, then using Cantor's initial proof of the uncountability of the reals? It seems like this doesn't particularly leverage anything having to do with Dedekind cuts. Commented Sep 25, 2012 at 22:53
• @templatetypedef: Yes, the two parts are not tightly coupled. It's an attempt to do the job with as few detours as possible, so the properties proved in the first step are ones that are particularly simple to prove for Dedekind cuts (rather than what would have been needed, for example, to carry out the standard decimal-based diagonalization). It's somewhat unclear to me what else you were expecting -- a proof without any immediate steps where everything happens directly from the definition in a sudden flash of brilliance? Why would such a thing exist? Commented Sep 26, 2012 at 9:44
• I was hoping that perhaps there was a direct way to show that the set of Dedekind cuts of $\mathbb{Q}$ is uncountable that relied purely on the definition of a cut, rather than on the fact that they define the reals... if that's even possible to do. Commented Sep 27, 2012 at 4:15
• @templatetypedef: While you can prove that the power set of $\mathbb Q$ is uncountable, I don't see an argument while Dedekind cuts have to be uncountable. Commented Sep 28, 2012 at 7:50

You can't really show that $\mathbb R$ is uncountable using Dedekind cuts. If you can show that, then I am unaware of any such proof (and having a lot of work around the intro to set theory course in my university for the past few years, I doubt that I would not have known such proof). You can show that $\mathcal P(\mathbb N)$ is uncountable by this method though.

Dedekind cuts provide a method for constructing and defining the real numbers, rather than a direct method of proving their size is $2^{\aleph_0}$.

However in proving that $|\mathbb R|=2^{\aleph_0}=|\mathcal P(\mathbb N)|$ we can use Dedekind cuts to establish the $\leq$ direction by showing that if we fix an enumeration of $\mathbb Q$ as $q_n$, then the sets $A_r = \{n\in\mathbb N\mid q_n<r\}$ for $r\in\mathbb R$ form an injection from $\mathbb R$ into $\mathcal P(\mathbb N)$. Therefore there are at most $2^{\aleph_0}$ many real numbers.

The other direction usually involves the Cantor set construction and shows that there are exactly $2^{\aleph_0}$ many real numbers.

• I don't think it is too hard to directly construct an order isomorphism from the linear order on $2^{\omega}$ (the lexicographical one) to the inherited linear (subset) order on a set of Dedekind cuts that we construct. It would be very similar to constructing a Cantor scheme in the sense of descriptive set theory. That proof would not rely on the fact that Dedekind cuts define the reals, nor would it require taking any sort of suprema of Dedekind cuts. It just relies on the fact that $\mathbb{Q}$ is a dense linear order. Commented May 14, 2014 at 11:30
• first i dont see how the cuts are involved in your argument, second your argument is unnecessary, the cuts are by definition elements of the power set of Q. Commented Nov 12, 2023 at 9:12

The set of all infinite sequences with {0,1} is uncountable.

The set of all infinite sequences with {0,1} where all members are 0 from some place onwards is countable.

The complement set of sequences of {0,1} with infinite number of 1'ns is therefore uncountable.

We set up a 1x1 correspondence between this last set and cuts greater than 0 and less or equal 1 as follows:

If A = {An} is such a sequence, we define a subset of the rationals C(A)= {g: there is a natural N such that g < sum(1 to N)(An/2**n)}.

C(A) is a cut, and if A<>B, then C(A)<>C(B)