Re: Non-countability of R

On Thu, 7 Aug 2008, Virgil wrote:
William Elliot <marsh@xxxxxxxxxxxxxxxxxx> wrote:

prove that "the set R of real numbers is uncountable".

PROOF. It is enough to show that the set I of all real
numbers r such that 0 <= r <= 1 is uncountable: this is
because |I| <= |R|. Assume that I is countable, so that
it can be written in the form {r_1,r_2,r_3,...}. Write
each r_i as a decimal, say

r_i = 0.r_{i1} r_{i2} ...

where 0 <= r_{ij} <= 9. We shall get a contradiction ny
producing a number in the set I which does not equal any
r_i. Define

s_i = 0 if r_{ii} <> 0; 1 if r_{ii} = 0

and let s be the decimal 0.s_1 s_2 ...; then certainly s \in
I. Hence s=r_i for some i, so that s_i=r_{ii}; but this is
impossible by the definition of s_i. QED

We remove all sequences that end in 999... to assure a bijection
between sequences and reals in [0,1).

If your construction rule does not ever produce either a 0 or a 9, which
is quite easy to arrange, you may allow all digit sequences in the list
from which you construct a non-member of that list.

Ok. that method requires an integer base > 3 and has the advantage
of not having to restrict the decimal expression to certain forms.

The restricitve method can work however for base 3.

Anyway, Cantor's original proof was that there were more that countably
many binary sequences, functions from N to , say, {m,w} where m =/= w.

There's a bijection between those and P(N). Seems likely that the
theorem you reference came before his reknown |S| < |P(S)|.

----
.

Relevant Pages

  • Re: Non-countability of R
    ... We remove all sequences that end in 999... ... If your construction rule does not ever produce either a 0 or a 9, ... that method requires an integer base> 3 and has the advantage ... The restricitve method can work however for base 3. ...
    (sci.math)
  • Re: Non-countability of R
    ... William Elliot wrote: ... producing a number in the set I which does not equal any r_i. ... We remove all sequences that end in 999... ... If your construction rule does not ever produce either a 0 or a 9, ...
    (sci.math)
Loading