80-110: The Nature of Mathematical Reasoning

Spring 1998




1. The Theory of Infinite Sets - Part 2


-Review 1-1 functions and def. 1:

Def. 1: If A and B are sets, then A| ≤ |B| if and only if there is a 1-1 function from A to B (F1-1: A ® B).

We still do not yet have a definition of when two sets have equal cardinality, i.e., |A| = |B|. We will take a slight shortcut and define it as follows:

Def. 2: If A and B are sets, then |A| = |B| if and only if |A| ≤ |B| & |B| ≤ |A|.

We want to compare the cardinality of the natural numbers N, the odd natural numbers O, the integers I, the rationals Q, and the reals R.

N = {0,1,2,3,4,......}

O = {1,3,5,7,9,......}

I = { ...., -2,-1,0,1,2,.....}

Q = {<a,b> | a Î N & b Î N}

Notation: {x | P(x) } means : the set of all x such that x has property P. So we define the rationals Q as the set of all ordered pairs of natural numbers. In fact, to do it right we want to only include non-redundant rationals where the second number cannot be 0 (thinking of the first number as the numerator in a fraction and the second as a denominator, we canít divide by zero). So a better definition of Q is Q2:

Q2 = {<a,b> | a Î N & b Î N & b≠0 & " xÎN<a*x, b*x> = <a,b>}

The cardinality of the natural numbers N is À0 (aleph nought), i.e., |N| = À0. Any set with cardinality À0 is said to be denumerable, or countable. It turns out that the cardinality of O, I, and Q is the same as N, which is the smallest possible infinite cardinality, but none of these sets are as big as the reals R. First, lets prove that |O| = |N|, which will show that two infinite sets can have the same number of members, even though one is a proper subset of the other:


Theorem 1. |O| = À0

Proof: First we establish that |O| ≤ |N|, and then that |N| ≤ |O|. To establish that |O| ≤ |N|, we need to specify a function F1-1: O ® N. This is easy, because we can use the identify function: f(o) = o, which just means we give back the same number we are given, which works in this case because every odd number is also a natural. We can write this function as a set: F = {<o,f(o)> | o Î O & f(o) = o }. The function is obviously 1-1.

To show that |N| ≤ |O|, we need a function G1-1: N ® O. This is also not too bad. Its beginning looks pictorially like:


0 ® 1

1 ® 3

2 ® 5

3 ® 7

4 ® 9

. ® .

In general, this function is g(n) = 2n+1. How do we verify that G is 1-1? First apply the definition: G is a 1-1 function from A to B « " <a1,b1>,<a2,b2>Î G[ a1 = a2 « b1 = b2].

In this case that translates into:

" <n1,2n1+1>,<n2,2n2+1>Î G[ n1 = n2 « 2n1+1 = 2n2+1]

It is certainly the case that two natural numbers n1 and n2 are equal if and only if the two odd numbers 2n1+1 and 2n2+1 are also equal. Q.E.D. (which means the proof is done).

Theorem 2. |I| = À0, i.e., I is denumerable.

Proof: Left as homework.


Considered as fractions, the rationals Q are interesting partly because, unlike N,O, and I, they are dense, i.e., between every two rationals there is another rational:

So if we start with Q1 < Q2, there is a Q3 that is bigger than Q1 and smaller than Q2. And then there is a Q4 that is bigger than Q1 and smaller than Q3, etc., etc., forever. You can see that between any two natural numbers there are an infinity of rationals. So how can it be that the rationals are no bigger than the naturals? Here is where mathematical reasoning pays off. Assuming that our definition of equal cardinality is reasonable, we can prove that they have the same number of members. Our intuitions cannot make sense of the infinite, so we will let deductive mathematical reasoning take care of it for us.



Exercises: Prove Theorem 2: |I| = À0, i.e., I is denumerable, i.e., |I| = |N|