2 of 2

35.1 E, O and Z

In Chapter 34 you learned about the infinite set of natural numbers, N.

E = {0, 2, 4, 6 …}
O = {1, 3, 5, 7 …}
Z = {… -2, -1, 0, 1, 2 …}

There are many other infinitely big sets of numbers as well.

For example, consider E, the set of even numbers: {0, 2, 4, 6 …}.

Or O, the set of odd numbers: {1, 3, 5, 7 …}.

The set of positive and negative whole numbers, the integers, is commonly called Z.

Z = {… -2, -1, 0, 1, 2 …}

Let’s see if you can figure out the size of each of these sets.

We can use a 1-to-1 correspondence to show that E and N are the same size.

We can use a 1-to-1 correspondence to show that E and N are the same size.

0—0
1—2
2—4
3—6
Etc.

You might have noticed that sometimes there is a nice mathematical function that expresses the 1-to-1 correspondence between two sets. In this case, it is n×2.

We won’t worry about figuring out the function in this class. All that matters is that you can see how to associate the elements of two sets so that there’s a clear 1-to-1 correspondence between them.

Let’s continue. How about the odd numbers?

If you could figure that out, then you should be able to give the 1-to-1 correspondence that shows that the sets have equal cardinality.

Next we consider the hardest example so far. Recall that Z is the positive and negative integers (whole numbers):

Z = {… -2, -1, 0, 1, 2 …}

How does its size compare to N?

This question was difficult. But remember: infinity can be surprising!

It is very natural to think that Z is bigger than N, because it has two ellipses “…”.

That means that a tempting way to create a 1-to-1 correspondence fails. For example, we wrote Z like this:

Z = {… -2, -1, 0, 1, 2 …}

So you might start with -2 and try to pair it this way (we use parentheses around negative numbers so you can see the minus sign):

0—(-2)
1—(-1)
2—0
3—1
4—2
5—3
Etc.

That is not a real 1-to-1 correspondence.

But that is not a real 1-to-1 correspondence, because it does not account for the other ellipsis. What about all the negative numbers that come before -2?

You might have realized that this correspondence fails. If so, that is great!

But just because one attempt fails, it does not follow that no correspondence exists.

But just because one attempt fails, it does not follow that no correspondence exists.

Instead, we have to use some creativity in order to find the correspondence, but it can be done!

Notice this: say we don’t start with -2 from Z. We start at 0, and then go to 1. But instead of continuing to 2, we jump back to -1.

If we flip-flop between positive and negative numbers like that, every element of Z will be paired with an element of N.

That means there is a 1-to-1 correspondence. Amazing!

That means there is a 1-to-1 correspondence, and they are the same size. Amazing!

Let’s see if you’ve got the idea.

In this section we considered three more infinite sets, E, O and Z, and we proved that they are all the same size as N.

Even Z, which seemed larger, is still just size ℵ0.

0 is infinitely big. So how could anything be bigger than it?

Maybe that shouldn’t be surprising, after all. ℵ0 is infinitely big. So how could anything be bigger than it?

Maybe there only one size of infinity?