## infinities

To prove: There are more irrationals than there are rationals. In more formal terms, the cardinality of ℝ, the set of all real numbers, is greater than the cardinality of ℚ, the set of rational numbers of the form a/b, where a and b are integers and b ≠ 0.

Proof: We use the intermediate result that the rationals are countable.

By contradiction, let φ: ℤ+ → [0,1] be a one-to-one correspondence between the counting numbers and the subset of ℝ that falls in the closed unit interval. We should be able to list the binary expression of each such real number in a table as follows:

φ(1) = 0.a11a12a13...

φ(2) = 0.a21a22a23...

φ(3) = 0.a31a32a33...

...

φ(i) = 0.ai1ai2ai3...aii...

...

where all of the aij's are binary integers, 0 or 1.

Next consider the real numbers

m = 0.a11a22a33...aii...

and

m' = 0.a11'a22'a33'...aii'...

where ajj = 0 ⇒ ajj' = 1 and ajj = 1 ⇒ ajj' = 0, for all j.

We assert that m' is not on the above list, as m' differs in at least one place from every item on the list. A contradiction, and our result is established.

QED

cactuspear home