countability of reals

mueckenh_at_rz.fh-augsburg.de
Date: 01/05/05 

Date: 5 Jan 2005 04:07:34 -0800

Theorem. A one-to-one correspondence can be set up between the set IQ
of all rational numbers of the interval (0,1) and the set IX of all
irrational numbers of the interval (0,1)

Definition. a U A: Union of the number a (interpreted as a set) and the
set A.

Define the empty sets Q_0 and X_0.
Choose any irrational number x_1 of (0,1).
x_1 U X_0 = X_1.
Choose any rational number q_1 satisfying 0 < q_1 < x_1.
q_1 U Q_0 = Q_1.
Choose any further irrational number x_2 of (0,1).
x_2 U X_1 = X_2.
Choose any further rational number q_2 satisfying m_1 < q_2 < x_2,
where m_1 = max({x of X_1: x < x_2}).
q_2 U Q_1 = Q_2.
...
Choose any further irrational number x_n+1 of (0,1).
x_n+1 U X_n = X_n+1.
Choose any rationale number q_n+1 of (0,1) satisfying m_n < q_n+1 <
x_n+1,
where m_n = max({x of X_n: x < x_n+1}).
q_n+1 U Q_n = Q_n+1.

Continue until one of the sets IQ or IX is exhausted.

The set IQ of rational numbers of (0,1) cannot be exhausted
prematurely, because there is at least one rational number between any
two different real numbers like m_n and x_n+1. The maximum m_n < x_n+1
can always be found, as long as n is a natural number and, therefore,
X_n is a finite set. The set of all rational numbers is countable,
i.e., any rational number of IQ can be equipped with a finite index n.

As long as the pairs q_n, x_n have natural numbers as indices,
transfinite induction is not required.

This proves the theorem: The cardinality of IX is not larger than
cardinality of IQ. IX is countable.

Relevant Pages

  • Re: countability of reals
    ... > X_n is a finite set. ... any rational number of IQ can be equipped with a finite index n. ... > transfinite induction is not required. ... The cardinality of IX is not larger than ...
    (sci.math)
  • Re: Cantors proof that #(Evens) = #(Naturals) is inconsistent
    ... David Ferguson, PAY ATTENTION to the following two paragraphs since you ... If A and B are nonempty finite sets, and there is a 2-to-1 correspondence ... that the cardinality of E* is two times the cardinality of E, ... >> say that this is not a bijection. ...
    (sci.math)
  • Schroeder-Bernstein: is this proof OK?
    ... to-one correspondence between A and a subset B_1 of B and ... B_1 and A_2 have the same cardinality. ... Because g coincides with f on M, ... "basically sound" proof may still have errors: ...
    (sci.math)
  • Re: fastest way to print a lot of pdf files?
    ... >> within a classic system of mathematics like the one you have in mind, ... > indicates you don't know what cardinality means, ... > array of a finite set of symbols and the integers. ... Now tell me how they create that bijection of yours- indeed, ...
    (comp.os.linux.misc)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... all finite sets have the same cardinality, ... Every finite set has the same cardinality. ... it may serve as a definition of aleph-0. ... -- New York Times movie reviewer A. O. Scott ...
    (sci.logic)