5
$\begingroup$

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!

  • 0
    @AsafKaragila: Agreed (though "field" is not needed, only order properties, which is cut-speak for subset relations)2012-09-25

3 Answers 3

3

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

  • 1
    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.2014-05-14
3

(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} and such that $r_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.

  • 0
    @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.2012-09-28
0

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)