Set Theory - Part 3

Theorem 3: |Q| = |N|

Proof: First we prove the easy half, that |N| ≤ |Q|, and then the harder one: that |Q| ≤ |N|. To prove |N| ≤ |Q|, we need to construct a function F_1-1: N ® Q. This is easy, because each natural is also a rational, so we can use a version of the identity function: f(n) = n/1.

F = {<n,<n,1> | n Î N}. To prove |Q| ≤ |N|, we need to construct a function

G_1-1: Q ® N. Consider the following function: g(k,n) = 2^k(2n+1) - 1.

What might be wrong with this function? It might not be defined for some rational, it might return a value not in N, and it might not be 1-1. Lets consider each in turn. Since 2^k is defined for any natural number k, and so is 2n, it certainly returns some number for every rational <k,n>. Might one of these numbers not be in N? Might it be a negative number, or not a whole number? The smallest that 2^k can be is 1, because 0 ≤ k. The smallest 2n can be is 0, and thus 2n+1 is at least 1, and thus 2^k(2n+1) must be at least 1, so g(k,n) is never negative. Is this function 1-1? Lets apply the definition of 1-1 to this function and see.

G is a 1-1 function from A to B « " <a₁,b₁>,<a₂,b₂>Î G[ a₁ = a₂ « b₁ = b₂]. In this case that translates into:

" <<k₁,n₁,>,2^k1(2n₁+1) - 1>, <<k₂,n₂,>,2^k2(2n₂+1) - 1>Î G

[ (n₁ = n₂ & k₁ = k₂) « (2^k1(2n₁+1) - 1 = 2^k2(2n₂+1) - 1)].

It should be obvious that (n₁ = n₂ & k₁ = k₂) ® (2^k1(2n₁+1) - 1 = 2^k2(2n₂+1) - 1). So all the work is in establishing that: (2^k1(2n₁+1) - 1 = 2^k2(2n₂+1) - 1) ® (n₁ = n₂ & k₁ = k₂).

Lets do this with natural deduction style proofs, just like we did in class for the section on sentential logic. Beging with this statement on the bottom of the page as a goal, and work backwards. It is a conditional sentence, so we can assume the antecedent and try to prove the consequent:

Now lets work forwards a little from the assumption. Add 1 to both sides in the first step, and divide both sides by 2^k1 and then 2n₂+1 in the second:

Now lets work backwards, in which case our goal is n₁ = n₂ & k₁ = k₂. This is a conjunction, so lets use conjunction introduction to split it up into two goals:

Lets try to prove k₁ = k₂ first. This is atomic. We can’t build it with introduction rules. It is not embedded above, so lets go indirect, and try a reductio ad absurdum:

This leaves us with the task of figuring out an absurdity (contradiction) to prove. Work forward with the assumption just introduced: k₁ ≠ k₂. If k₁ ≠ k₂ then either

k₁ > k₂ or k₁ < k₂. Now we can use argument by cases:

In the righthand subproof, in which k₁ < k₂, line 3 is available. From the right side of the equation, we know that 2^k2 is even, and 2^k1 is either a smaller even number or 1. In either case the right hand side of the equation on line 3 is an even number. But both the numerator and denominator on the left hand side of equation 3 are odd, and so the left hand side of equation 3 is odd. But an odd cannot equal an even, so we have derived an absurdity:

If we flip the numerator and denominator on each side of the equation in line 3, then we can produce an analgous argument for the case where k₁ > k₂. Now we know that k₁ = k₂, so we can use it in proving that n₁ = n₂. But now look at the equation in line 3 again, and you will see that the right hand side must equal 1, so 2n₁+1 = 2n₂+1, from which it is immediate that n₁ = n₂. Q.E.D.

We have proved that the rationals are no bigger than the naturals, even though there are an infinity of rationals between every two natural numbers. But recall that in the very first week of class we proved that there is a number that cannot be expressed as a rational, namely Ö 2. So even though we can find a rational q₁ arbitrarily close to Ö 2 but less than it, and one that is arbitrarily close to it but greater q₂, and then an infinity of rationals between q₁ and q₂, we can never exactly hit Ö 2. So there are still holes in the rationals! Next class we consider the Reals, which include the rationals and their holes, and show that there are more Reals than rationals.