More than Infinite?

You might think that infinity is pretty easy to understand. All you have to do is start counting, 1, 2, 3, 4, … and then imagine that you never stop. The set of numbers so described {1, 2, 3, 4, …} is called the natural numbers and is an infinite set. So far so good. But then you start asking yourself some questions and things seem to quickly go awry.

For example, which set is bigger: {1, 2, 3, 4, …} or {2, 4, 6, 8, …}? How could you even answer the question? You could assume that since the even numbers are a proper subset of the natural numbers that the set of natural numbers is bigger. That makes sense, we took away all the odd numbers. Okay, but, let’s start counting the even numbers, the first (1) even number is 2, the second (2) even number is 4, the third (3) even number is 6, and so on. But doesn’t this counting of the even numbers go on forever just like the natural numbers. As a matter of fact, isn’t this counting of the even number exactly the set of natural numbers? So how can we say that the evens are a smaller set; if to count them you need all of the natural numbers?

Maybe you’re beginning to see that things aren’t as simple as they seem. We need to be careful when thinking about concepts like infinity. This is where mathematics comes to our rescue. It is there that we will find the careful definitions and methods that help us answer questions about infinity in a logical and consistent manner.

The first question we have to answer is: just how should we measure the size of a set? After we’ve answered that question, in a manner that works for both finite and infinite sets, then we can start comparing the sizes of some infinite sets. The size of a set is called its cardinality. Two sets have the same cardinality if their elements (or members) can be placed in 1-1 correspondence with each other. A 1-1 correspondence is a rule or procedure that assigns to each and every member of the first set a unique member of the second set in such a way that the members of the second set are exhausted.

Here's an example. Let X = {1, 2, 3, 4} and Y = {2, 4, 6, 8} be sets. Then the rule (r1) that assigns 2 to 1, 4 to 2, 6 to 3, and 8 to 4 is a 1-1 correspondence. The rule (r2) that would assign 2 to 1, 2 to 2, 4 to 3 and 4 to 4 is not a 1-1 correspondence as it doesn’t exhaust the set Y (it never assigns 6 or 8 to any member of X) and it doesn’t assign a unique element of Y to each element of X (both 1 and 2 are assigned 2).

In any case, since we can find a 1-1 correspondence (the rule r1) between X and Y (we only have to find one), we can say that X and Y have the same cardinality or, informally, that X and Y have the same number of elements.

We can’t put A = {a, b, c} and B = {1, 2, 3, 4} into 1-1 correspondence. There would always be an unused element from B. Or, if we tried to establish the correspondence in the other direction, we would not be able to find a unique member of A for each member of B (we would run out of elements of A).

For finite sets, cardinality agrees with our intuitive notion of number. A set has 8 elements if it has the same cardinality as the set {1, 2, 3, 4, 5, 6, 7, 8}. This is just good old fashion counting.

Now let’s return to our first question. Is the cardinality of the even natural numbers the same as the cardinality of all of the natural numbers? I say it is. To prove this I have to construct a 1-1 correspondence between the two sets. If e is an even number then it will be placed in correspondence with e ⁄ 2. This rule clearly applies to each and every even number. The result is always a whole number and thus a member of the natural numbers. Does this rule exhaust the natural numbers? Or rephrased, for any number n is there an even number e with the property that e ⁄ 2 = n. Sure, just let e = 2n. As there is a 1-1 correspondence between the even numbers and the set of all the natural numbers, they have the same cardinality.

The set of natural numbers is important enough that its cardinality is given a special name. Sets with the same cardinality as the natural numbers are called countable. The cardinality of the natural numbers is also referred to as ‪א₀‬ (aleph naught). Can we find an infinite set with cardinality different from the natural numbers? Where should we look?

Our search for an infinite set that has cardinality different from the natural numbers takes us to an unlikely location. The interval between the number 0 and the number 1. It is obvious that this interval contains an infinite number of elements, just consider { 1/2, 1/3, 1/4, 1/5, … }. Maybe all of the fractions between 0 and 1 have a different cardinality that the natural numbers.

Unfortunately, the answer is no. To prove this claim, I, again, have to come up with a 1-1 correspondence between the fractions (the rational numbers, to use the proper name) and the natural numbers. On the blackboard below, I have plotted a point on a two dimensional grid for each rational number (actually the grid show more than the rational numbers, as both 2/4 and 1/2 represent the same number, but that doesn’t affect our proof). The vertical axis represents the numerator and the horizontal axis represents the denominator of each fraction. A few numbers are labeled to make this clear.

Now, how do we count these? The next blackboard shows a scheme for counting these fractions. First we count the fractions whose numerator and denominator total one { 0/1 }. Then we count those whose numerator and denominator total two { 0/2, 1/1 }. Then we count those where the total is three { 0/3, 1/2, 2/1 }. We continue our counting in this fashion. Every natural number is assigned to one and only one fraction and the set of fractions will obviously be exhausted.

That means rational numbers have the same cardinality as the natural numbers. Why, then, did I say the answer would be found in the interval between 0 and 1? Because there are numbers in that interval that cannot be represented as fractions. What kind of numbers? Numbers like √(2) - 1.

I will prove the √2 cannot be represented as a fraction, or that it is irrational, and (famously in mathematics) leave the proof that √(2) - 1 is not rational to the interested reader. Before we review the proof, we have to understand the basic method. The demonstration I will present relies on a technique called proof by contradiction.

Let’s say (rather abstractly) that you want to prove the assertion: if a then b, where a and b are propositions (statements that can be either true or false). To do a proof by contradiction you assume that a is true, but b is false. Or more concretely: We are trying to prove: If x = √2 then x is not rational; to do a proof by contradiction we assume that x = √2 and x is rational. Arguing from these premises we then proceed step by step, each step following logically and correctly from the one before. Eventually we end up with a contradiction to a known fact or, even, one of the initial premises.

If the final step of a line of reasoning is incorrect, it can mean only one of two things. There was an error in one of the steps or the assumptions are themselves incorrect. But we know the steps are right (we were very careful); therefore, the assumptions must be wrong. Our assumption is that our theorem is incorrect. If that assumption is false then the theorem must be true. In our case we assumed that x is rational, so when we find a contradiction we will know that x is irrational.

The blackboard below presents the proof. I’ll just make a few comments. Two numbers are relatively prime when they have no common divisor. So the assertion in the proof below that a and b are relatively prime is the same as saying that a ⁄ b is a fraction reduced to lowest possible terms. 4 ⁄ 6 is not in lowest possible terms. 2 ⁄ 3 is. It is always possible to find a lowest possible terms representation of a fraction.

I am going to claim that the set of all numbers (rational and irrational together or the real numbers) between 0 and 1 has a cardinality different from that of the natural numbers. To prove this I need to show that there is not a 1-1 correspondence between the natural numbers and this interval of real numbers. The method of proof will again be contradiction.

This means that I am going to assume that such a correspondence does exist. From this assumption I will derive a contradiction. The contradiction will prove that no such correspondence can exist.

Our proof will rely on the fact that every real number can be written out in a decimal representation. For rational numbers the decimals are eventually repeating, like 3 ⁄ 11 = 0.272727272727… or 1 ⁄ 4 = 0.250000000…. For irrational numbers the decimals never settle in to a repeating pattern √(2) - 1 = 0.4142135623730951….

We assume the existence of a 1-1 correspondence, that means that to every natural number there corresponds a unique real number and that the set of real numbers between 0 and 1 is exhausted. Let's write down what such a correspondence has to look like.

A note on notation: d₁ is the decimal number corresponding to 1, d₂ the decimal number corresponding to 2, d_n is the general term, that is the decimal number corresponding to an arbitrary natural number n. Further d₁₁ is the 1^st digit of the decimal number corresponding to 1, d₂₃ is the 3^rd digit of the decimal number corresponding to 2, and so on.

Now let's recall our claim. Using the method of proof by contradiction we are assuming the existence of a 1-1 correspondence between the natural numbers and the real numbers between 0 and 1. If such a correspondence exists then it must look like the one above; an assignment of a decimal number to each natural number. Further, as this is a 1-1 correspondence, it must exhaust the set of all real numbers between 0 and 1.

Now, consider the circled positions in the display below. We have constructed a new decimal number (d) from the ones already in our list. d₁₁ means any digit different that d₁₁ (so if d₁₁ is 3 we pick 6). [Tiny technical note: we shouldn’t pick nines. Why? Because .29999999…. is the same as .30000000000…, so if we pick nines we could run into a problem later.]

The new number we have constructed is a number between 0 and 1 so, as our correspondence exhausts the numbers between 0 and 1 it must be in the list above it. But that’s our contradiction, because it cannot be. It differs in at least one decimal place from each of the numbers in our list.

Stop here for a minute to review the proof yourself. We have shown that there can be no 1-1 correspondence between the natural numbers and the real numbers between 0 and 1. There are more real numbers than natural numbers.

There are at least two different sizes of infinity!

Here is a special bonus section for those of you who are still with us. Consider the unit cube. It can be described by ordered triples (x, y, z) where 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 and 0 ≤ z ≤ 1. I am going to show that the cardinality of the unit cube is the same as the cardinality of the interval [0, 1]. In other words, there is enough space on one edge of a cube for all the points in the cube.

Here is the correspondence between an arbitrary point in the cube (x, y, z) and a point on the interval d: Let d = .x₁y₁z₁x₂y₂z₂x₃y₃z₃… where x_n is the n^th decimal digit of x.

Things really do seem to go awry (at least our intuition is not much of a guide) when talking about infinity.

Nicolas Minutillo, January 22, 2003 (revised February 9, 2003) (Mathematics)