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.a₁₁a₁₂a₁₃...

φ(2) = 0.a₂₁a₂₂a₂₃...

φ(3) = 0.a₃₁a₃₂a₃₃...

...

φ(i) = 0.a_i1a_i2a_i3...a_ii...

...

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

Next consider the real numbers

m = 0.a₁₁a₂₂a₃₃...a_ii...

and

m' = 0.a₁₁'a₂₂'a₃₃'...a_ii'...

where a_jj = 0 ⇒ a_jj' = 1 and a_jj = 1 ⇒ a_jj' = 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