Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  Hagen von Eitzen Sep 25 '12 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). –  Asaf Karagila Sep 25 '12 at 17:51
    
@AsafKaragila: Agreed (though "field" is not needed, only order properties, which is cut-speak for subset relations) –  Hagen von Eitzen Sep 25 '12 at 17:55

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

share|improve this answer
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. –  Carl Mummert May 14 at 11:30

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

share|improve this answer
2  
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. –  templatetypedef Sep 25 '12 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? –  Henning Makholm Sep 26 '12 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. –  templatetypedef Sep 27 '12 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. –  Asaf Karagila Sep 28 '12 at 7:50

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.