You’ve already learned about several infinite sets of numbers:

Natural numbers: N = {0, 1, 2, 3 …}

Even numbers: E = {0, 2, 4, 6 …}

Odd numbers: O = {1, 3, 5, 7 …}

Integers (pos. and neg.): Z = {… -2, -1, 0, 1, 2 …}

There are only two more sets of numbers we will consider.

In this section, we learn about Q, the rational numbers. In the next section, we learn about R, the real numbers.

**Q:** the rational numbers (fractions).**R:** the real numbers (rationals and irrationals).

The * rational numbers*, Q, are the numbers that can be expressed as fractions of whole numbers.

“Q” might seem like a weird name for the rationals. The solution to a fraction, though, is called a * quotient*. That’s where the name comes from. Plus “R” was already taken by the real numbers.

For example, the rational numbers include fractions like: 1/16, 3/4, 19/3, 441/166. All the integers are rational numbers as well, since a whole number can be expressed as a fraction over 1:

4 = 4/1

What the rationals do * not* include are all the

Q and R are just the positive rational and real numbers (and zero).

When we discussed Z, we learned that including negative as well as positive numbers does not really affect the size of an infinite set. So in this section we will just consider Q, the positive rational numbers (and zero).

Let’s see if you’ve got it.

Now that you know what Q is, here is what we want to know: how many rational numbers are there?

|Q| = ?

Before we try to answer that question, let’s compare Q to Z.

Recall that Z had two ellipses “…”.

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

That made it seem like Z was bigger than N. But we saw that if we flip-flop between positive and negative numbers, we could put Z into 1-to-1 correspondence with N.

Q has an infinite number of ellipses.

Q doesn’t just have one or two ellipses, though. Q has an infinite number of ellipses.

Take any two rational numbers, like 1/4 and 1/2. **There is always another rational number between them.**

For example, between 1/4 and 1/2 is 1/3. And between 1/3 and 1/2 is 5/12. And between 5/12 and 1/2 is 11/24.

**Density:** between any two numbers, there exists another number.

This property of Q, that between any two numbers there is another one, is called * density*.

Using the < relation, we can formalize density this way:

AxAyEz(~(x=y)->((x<z&z<y)v(y<z&z<x)))

The Domain = Q. What this sentence says is for any x and y in the domain, if x and y are different numbers, then there exists an element of the domain z which is between x and y.

Density means no rational numbers are “next to” each other.

Density is an amazing property. It means no two rational numbers are adjacent or “next to” each other, when they are in their numerical order.

In the natural numbers, by contrast, 1 is “next to” 2, and 2 is “next to” 3.

Density just says that * some* number exists between any two numbers. But if you think about it, that means that for any rational numbers, there are actually an

For example, say we start with two numbers, a and b. Density says that there is another number between them. Call it c.

Density also means there will be yet another number between a and c. Call it d.

This process goes on forever! Also notice that all of these additional numbers are between a and b.

What you can see, hopefully, is that density means there are an infinite number of ellipses “…” in Q. There is an ellipsis between every two numbers of Q!

That should make your head spin.

How could we ever pair all the members of Q off with N?, you should be thinking.

It takes some creativity to figure out how to show that Q and N are the same size with a 1-to-1 correspondence, but it can be done.

Here’s one neat way to do it.

Picture a giant table in a spread sheet program like Excel or Google sheets.

Each column is labeled with a number starting a 1. Each row is labeled in the same way: 1, 2, 3, etc. Like this:

We fill each cell with a fraction like this: column/row.

Each * cell* in this table is the intersection of a column and a row.

We fill each cell with a fraction like this: column number/row number.

If we start filling in the table, it looks like this:

We haven’t filled out the table completely, of course, because it keeps going infinitely to the right and down.

Every rational number from set Q is somewhere in this table (except 0).

Now consider this: every rational number from set Q is somewhere in this table (except 0). Every element of Q can be expressed as a fraction, such as 13/9. That number will then be in the 13th column and the 9th row.

You try it.

Since every element of Q besides 0 is in this table, we can use the table to make a 1-to-1 correspondence with N.

The first thing we’ll do is add 0 in the upper left corner. Then we’ll start there, and trace a line through the entire table, like this:

We use a snake-coil pattern for the line.

We use a snake-coil pattern for the line. The line goes on forever, just like the table. But the key thing to realize is that for any cell of the table, eventually it will get covered by the line.

If you understand the snake coil pattern, try this question.

Notice what the red line allows us to do: create a list of numbers which includes every element of Q.

Q = {0, 1/1, 2/1, 2/2, 1/2, 1/3, 2/3, …}

This way of writing Q does not follow numerical order. Instead, it follows the order of our red snake-coil line.

But it still includes every member of Q, * and it only has one ellipsis*. That is how it helps us create a 1-to-1 correspondence with N.

For a first attempt, we might try to pair each element of N with Q following that list:

0—0

1—1/1

2—2/1

3—2/2

4—1/2

Etc.

But there is a problem with this attempt. This is not a 1-to-1 correspondence. Can you tell why?

We said that every element of Q is on our spreadsheet table, but we didn’t say that every element is only on there once.

In fact every element is on there many times. For example, look at the diagonal down the middle of the table: 1/1, 2/2, 3/3, etc.

Every one of those cells is the same number: 1. So if we just paired every element of N with the cells of the table by following the red line, we would pair multiple different elements of N with the same element of Q.

But there is an easy solution: we just skip repetitions. As we follow the red line, at each new cell we just check to see if that number is the same as any of the previous numbers. If it is, we skip it. If it isn’t, we pair it with an element of N.

If you understand that plan, see if you can create the 1-to-1 correspondence.

|N| = |Q|. That is amazing!

This shows that |N| = |Q|. That is amazing! Even though Q is dense, and there are an infinite number of ellipses in it, Q is still size ℵ_{0}.

So far, every infinite set we have considered is still the same size, ℵ_{0}. That really makes it seem like there is only one size infinity.

Login

Accessing this textbook requires a login. Please enter your credentials below!