When we are going to talk about one set being bigger or smaller than another - at least, in terms of its cardinality, or “how many elements” are in the set - we need to start by being a bit more precise.

Definition:  We say that a set A has cardinality smaller than or equal to the cardinality of set B if we have an injective map

f:  A -----> B.

We will use the notation “A < B” whenever we have an injective** map like this one.

**The word “injective” means that any two things in A that are different must map to two different things in B!  For example, if A is the set consisting of the numbers 1, 2, and 3 and B is the set containing only the letters A, B, C, and D, we could make an injective map that takes 1 to A, 2 to B, and 3 to C.  We will write this, by the way, as f(1)=A, f(2)=B, and f(3)=C.  We could make a NON-injective map where 1 and 2 BOTH map to A, and 3 maps to B, but that’s not very useful!

We will use the notation  whenever we have such a map between A and B.  If A < B and B < A, then we say that A and B are the same size, or in more impressive sounding math speak, “A and B have the same cardinality.”  This isn’t quite the standard definition of “have the same size,” as a warning.

Okay... While this may sound somewhat arbitrary (“Shouldn’t it be the case that if we have an injective map from A to B and an injective map from B to A that we automatically have one of these bijections?”,) it’s worth checking out the proof of the theorem (the Schröder-Bernstein Theorem) that shows these two ideas are equivalent - if for no other reason than to convince yourself that it’s actually really hard to find one of these bijections, even if both maps are really nicely defined!

We will just assume that these are equivalent - two sets are the same size if EITHER we can find a bijection between them or we can find two different injections, in different directions.

Now... Onward to more exciting paradoxes!  In a series of exercises, we are going to show that there are as many fractions as there are natural numbers (i.e. whole, positive numbers!)

So far, so good.  Now starting at the top left corner and going in diagonals from the top right to the bottom left, cross out any fraction you see repeated.  For example, the first fraction you will cross out will be 2/2, and the second fraction you will cross out will be 4/2, then 3/3, and so on.  When you are done that (we could have done this for EVERY fraction, eventually,) you will be left with a grid (now missing some spots) of every fraction - each showing up exactly once.

With that, we have a bijection between the natural numbers and fractions (also known as “rational numbers.”)  Even though the rationals are all over the place - any interval on the entire real line, no matter how small, contains not just one, but infinitely many! - they are still only as big as the natural numbers.

Now, on to the scary “paradox” - which would be better phrased as a non-intuitive truth - there are WAY more numbers than either rational numbers or natural numbers.  In fact, there is no way to “count” even just the numbers between 0 and 1 on the real line - there are not just infinitely many of them, there are MORE than the only infinity we’d seen before!

Let’s see how that works.

Cantor’s Diagonalization Argument:

Let’s assume we could actually “count” all real numbers between 0 and 1.  This is smaller than ALL real numbers (the real line is VERY long, after all,) so it’s a good place to start.  When we say count, again, we mean we can make an ordered list of all of these real numbers between 0 and 1.  This amounts to putting them in bijection with the natural numbers, as all a list is doing is saying which real number is first, which is second, etc.

We have our list then:

1. 1. 0.x_{1,1} x_{1,2} x_{1,3} x_{1,4}....
   

2. 2. 0.x_{2,1} x_{2,2} x_{2,3} x_{2,4}....
   

3. 3. 0.x_{3,1} x_{3,2} x_{3,3} x_{3,4}....
   

4. 4. 0.x_{4,1} x_{4,2} x_{4,3} x_{4,4}....
   

5. 5...... etc.,
   

where each of the x_{i,j} are just some number 0,1,2,...,9, as these are our decimal representations of our real numbers between 0 and 1.

We’ve assumed that we have EVERY real number between 0 and 1 that is possible somewhere on this list.  Unfortunately for us, we can still make a NEW real number that is between 0 and 1 that CAN’T be on our list.  How do we do this?

Let’s write this new number x=0. x_1 x_2 x_3 x_4... as follows:

1. 1. For the first digit, we set x_1=3 if x_{1,1}=2, and x_1=2 if x_{1,1} wasn’t 2.
   

2. 2. For the second digit, we set x_2=3 if x_{2,2}=2 and x_2=2 if x_{2,2} wasn’t 2.
   

3. 3.... etc.
   

...

14. n. For the nth digit, we set x_n=3 if x_{n,n}=2 and x_n=2 if x_{n,n} wasn’t 2.
    

...

If we think about it, x cannot be anywhere in our list, because the way it was defined, it can’t equal the nth number on the list, because it doesn’t have the same nth digit!  This means that we COULDN’T have listed every real number between 0 and 1 like we had thought, and there must be a LARGER infinity than that of the natural numbers!

<<Back to Main>>