The Irrational and the Transcendental

We begin counting , and we can go on as long as we want. These are known as the counting numbers, the whole numbers, the cardinal numbers, the natural numbers, and they certainly seem natural and intuitive enough because the universe contains so many objects that we can count. Natural numbers were likely the first mathematical objects conceived by early humans. Some animals, too, it seems, have a concept of numbers, as long as the numbers don't get too large.

For many centuries, zero was not included among the natural numbers, and even now there is no firm consensus. (Text books on number theory usually tell you on the first page whether the author includes zero among the natural numbers.)

On the other side of zero are the negative whole numbers. To refer to all the positive and negative whole numbers as well as zero, the word integer does just fine. The integers go off into infinity in two different directions:

To refer to only the positive whole numbers starting at 1, the term positive integers works well. For positive numbers starting with zero (that is, the term non-negative integers is unambiguous and not too wordy.

Rational numbers are numbers that can be expressed as ratios of integers, except that a denominator of zero is not allowed. For example,

is a rational number, also commonly written in the decimal form:

Rational numbers also encompass all the integers, because any integer (47, say) can be written as a ratio with 1 on the bottom:

Any number with a finite number of decimal places is also a rational number. For example,

can be represented as the ratio:

Some rational numbers, such as

require an infinite number of digits to be represented in a decimal form:

This is still a rational number because it's a ratio. Indeed, any number with a repeating pattern of digits somewhere after the decimal point is a rational number. This is a rational number,

if the digits 23456 keep repeating forever. To demonstrate that it's rational, let represent the number:

Now multiply both sides by 100,000 :

It's well known that if you subtract the same value from both sides of an equality, you still have an equality. That means that you can subtract the two values in the first expression from the two values in the second expression: Subtract from and from and the decimals disappear:

So:

That's a ratio, so it's a rational number.

Just offhand, rational numbers seem to be quite complete. If you add two rational numbers, you'll get another rational number. Subtract, multiply, or divide rational numbers, and the result is also rational.

One might assume (as people did for many years) that all numbers are rational, but consider the hypotenuse of this simple right triangle:

According to the Pythagorean Theorem,

or

or

Does there exist a ratio of two integers that, when multiplied by itself, equals 2? One can certainly search and find many rational numbers that come very close. Here's one:

This one is just a little bit short. Multiplied by itself it's about . Maybe if we keep searching we'll find one that's perfect.

Or are we wasting our time?

It's hard to prove that something doesn't exist, but mathematicians have developed a type of proof that often comes in handy in such circumstances. It's called an indirect proof or a proof by contradiction, or the Latin reductio ad absurdum ("reduction to absurdity"). You begin by making an assumption. Then, you logically follow the implications of that assumption until you run into a contradiction. That contradiction means that your original assumption was incorrect.

Reductio ad absurdum proofs seem roundabout, but they are probably more common in real life than we realize. An alibi is a form of reductio ad absurdum. If the defendant were at the scene of the crime and at his mother's house, it would mean he was at two different places at the same time. Absurd.

Let's begin by assuming that the square root of 2 is rational. Because it's rational, there exist whole numbers and such that:

Are and both even? If so, divide them both by 2 and use those numbers instead. If they're still both even, divide them both by 2 again, and keep doing this until either or (or both) is odd.

Square both sides of the equation:

Or:

Notice that a squared is 2 times squared. That means that a squared is even, and the only way that squared can be even is if is even. Earlier I indicated that and can't both be even, so we now know that is odd. If is even, it equals 2 times some number, which we'll call :

Or:

Or:

That means that squared is even, which means that is even, which is contrary to the original requirement that and can't both be even.

Hence, the original assumption that the square root of 2 is a rational number is flawed. The square root of 2 is incontrovertibly irrational. Expressed as a decimal, the digits keep going with no discernable pattern:

The number can't be expressed exactly without an infinite supply of paper, pen, and time. Only an approximation is possible, and the ellipsis acknowledges our defeat. The closest you can come to expressing this number finitely is providing an algorthm for its calculation.

There's a reason why the terms that we use - rational and irrational - oddly seem to pass judgment on the mental stability of the numbers. Irrational numbers are also sometimes called surds, to which the word absurd is related. The ancient Greeks were familiar with irrational numbers but they didn't like them very much. According to legend (but not reliable history), it was Pythagoras's disciple Hippasus who in the sixth century BCE determined that the square root of 2 is irrational. The legend continues to report that this finding was so disturbing to these logical and rational Greeks that Pythagoras and his followers tried to suppress it by tossing Hippasus into the Mediterranean Sea. They would certainly have preferred that irrational numbers didn't exist. Diophantus, in rejecting irrational numbers as solutions to his problems, was carrying on a long tradition in finding irrational numbers not quite to his taste.

With the decimal notation that we have (but the ancient Greeks did not), it's easy to create numbers that are clearly irrational. Just wnte down something nutty without a repeating pattern of digits. For example, here's a number with some kind of crazy pattern in the decimals, but it's certainly not repeating:

After the decimal point, there's a 0 and one 1, then a 0 and two ls, then a 0 and three ls, and so forth. This is not a rational number! It cannot be represented by ratio of two integers. It is, therefore, irrational.

The square root of 2 is a solution to the following equation:

It's the same as an equation I showed earlier except that the 2 has been moved to the other side of the equal sign. The cube root of 17 (which is also an irrational number) is a solution to the following equation:

Both of those equations are called algebraic equations. Here's another algebraic equation:

An algebraic equation has one variable, usually called . (Algebraic equations are not the same as Diophantine equations because Diophantine equations can have multiple variables.) The algebraic equation has a series of terms - five of them in this last example - that sum to zero. Each term contains the variable raised to a power, which is a whole number or zero. (Because anything to the zero power equals 1, the fifth term can be interpreted as times to the zero power.) Each variable raised to a power is multiplied by an integer coefficient, in this example, the numbers , and . These coefficients can be zero, as is the case with the "missing" term of to the third power.

Algebraic equations tend to show up a lot in real-life problems, so they've come to be considered quite important. The general form of an algebraic equation is:

where is a positive integer and are integers. It's possible to wrte this more concisely as a summation:

Here's the example I showed earlier:

In this equation, (the highest exponent, called the degree of the polynomial) is 5, and equals equals equals 0, and so on.

The solutions to an algebraic equation (also called the roots of the equation) are called algebraic numbers. An -degree polynomial has at most unique solutions.  The algebraic equation

has solutions of 3 and 7 .

The square root of 2 is one solution of the algebraic equation:

The negative square root of 2 is the second solution.

The category of algebraic numbers also includes all integers and all rational numbers. For example, the integer 5 is the solution of the algebraic equation

and is the solution of:

Some algebraic equations can be solved only with square roots of negative numbers:

This equation looks insolvable because any number multiplied by itself is a positive quantity, so adding 5 to it won't ever yield zero. Square roots of negative numbers are called imaginary numbers. (The square root of is assigned the letter for convenience.) Despite the name, imaginary numbers are very useful and have actual real-world applications.

Sometime in the eighteenth century, mathematicians began speaking of real numbers in contrast to imaginary numbers. By definition, the category of real numbers includes everything except numbers involving square roots of negatives.

Real numbers are also referred to as the continuum because real numbers can be visualized as all the points on a continuous line:

Some integers are labeled on this line, but by themselves the integers obviously could not form a continuous line.

But neither can rational numbers. Rational numbers certainly seem very dense on the line. Between any two rational numbers, for example, and , you can insert another rational number which is the average of the two:

But there still exist gaps between the rational numbers where irrational numbers reside. For example, one such gap corresponds to the square root of 2 .

Now, we're coming at the subject of categorizing numbers from two directions. We've defined a category called algebraic numbers that are solutions to algebraic equations. This category of numbers includes integers, rational numbers, and many irrational numbers such as square roots and cube roots. We've also defined a category called real numbers, which are all numbers that do not involve square roots of negative numbers. The question that now poses itself is this:

Are all real numbers also algebraic numbers? Or are there some real numbers that are not solutions of algebraic equations?

In the 1740 s, Leonhard Euler - the indefatigable Swiss-bom mathematician, whose name is pronounced "oiler" - speculated that nonalgebraic numbers do indeed exist, and these he called transcendental numbers because they transcend the algebraic. Proving that transcendental numbers existed was tough. How do you prove that a particular number is not the solution of some extremely long and unspeakably hairy algebraic equation?

The existence of transcendental numbers was an open question until 1844 , when French mathematician Joseph Liouville (1809-1882) devised a number that he was able to prove was not algebraic. Displayed with the first 30 decimal places, the number Liouville chose was:

But that excerpt doesn't quite reveal the complete pattern. Liouville constructed this crazy number with factorials. The factorial of a number is the product of the number and all positive integers less than itself, and is represented by the exclamation point:

and so forth. Liouville's Number (as it is sometimes called) contains a in the , , and so forth, decimal places. Liouville designed this number specifically for proving that it was not the solution of any algebraic equation. The increasing scarcity of nonzero digits is the key to the proof.

In 1882, German mathematician Ferdinand Lindemann (1852-1939) proved that one of the most famous irrational numbers of all time was also transcendental. This is , the ratio of the circumference of a circle to its diameter:

Lindemann showed that was not the solution to an algebraic equation, and this fact provided an insight into a very old problem: For over two millennia, mathematicians and non-mathematicians alike had been trying to "square the circle." The problem can be stated simply: Given a circle, use a straightedge and compass to construct a square with the same area as the circle. (A similar problem is called the rectification of the circle, and it requires constructing a straight line with a length equal to the circle's circumference.) So fanatically did people try to solve this problem that the ancient Greeks even had a word for the obsessive activity: , literally, to tetragonize.

Using a straightedge and compass to construct geometrical shapes is equivalent to solving certain forms of algebraic equations. Because is not a solution to an algebraic equation, you cannot represent the number in a geometrical construction. Squaring the circle with a straightedge and compass is impossible.

Another famous transcendental number is symbolized by the letter (for Euler). If you calculate this number

for increasingly large values of , you'll approach :

You can also calculate by this infinite series involving factorials:

You can calculate it, but it's not a solution to any algebraic equation.

Over the past century many numbers have been shown to be transcendental, but there exists no general process for determining whether a number is transcendental. For example, the jury is still out on:

Turing's paper (and this book) restricts itself to real numbers (not imaginary numbers), and the following diagram summarizes the most important categories within the realm of the reals:

This diagram is not to scale.

Wait: What do I mean by that?

All those categories of numbers are infinite, right? There are an infinite number of integers, an infinite number of fractions, an infinite number of irrationals, right? Infinite is infinite, right? There aren't different sizes of infinity, are there? There can't be an infinity that's larger than another infinity, can there? Right? Infinity has never been an easy subject, regardless of whether it's approached from a philosophical, theological, or mathematical perspective. In mathematics, however, infinity can scarcely be avoided. We are compelled to examine this concept of infinity with all the bravery we can summon.

The relentless persistence of the natural numbers to get bigger and bigger seems to lie at the very root of our concept of the infinitely large. Whatever number we count to, we can always count one more. Real numbers can get infinitely large as well, of course, but only because they tag along with the natural numbers. Real numbers also allow us to ponder the infinitely small as we divide and subdivide the continuum into smaller and smaller pieces.

Are these two infinities - the infinity of the never-ending natural numbers, and the infinity of the density of the continuum - similar in some way? Or are they completely different?

The following discussion will be a little easier if we're armed with some rudimentary set theory. A set is a collection of objects, which are called the elements of the set. A set is often symbolized with a pair of curly brackets. For example,

is identical to the previous one. The number of elements in a set is called the cardinal number of the set, or the set's cardinality. The cardinality of the finite set shown above is 4 . Sets that have the same cardinality are said to be equivalent.

Some sets have a finite cardinality; others have an infinite cardinality. Consider the set of positive integers:

The cardinality is certainly infinite. That's also true for the set of even positive integers:

What is the relationship between the cardinalities of these two sets?

Perhaps our immediate instinct is to say that the first set has double the number of elements as the second set because the second set is missing all the odd numbers. That's certainly one way of looking at it, and that would be true if the two sets were finite. But how can we speak of one set having "double the number" of elements of another set when they're both infinite?

Let's try to count the elements of the second set. What does it really mean to count something? It means to put the items into correspondence with the natural numbers: "Number 1, number 2 , number " we recite, as we touch the noses of our subjects.

We can count the even positive integers in the infinite set by corresponding each of them to the natural numbers:

For every positive integer, there's a corresponding even number. For every even number, there's a corresponding positive integer. Looking at it this way, now the two sets appear to be exactly the same size, which means that they're equivalent. Is this a paradox or what? (Actually, this peculiar characteristic of infinite collections was noted by Galileo in and is sometimes called Galileo's Paradox.)

Nobody seems to have worried too much about this paradox until Georg Cantor began wrestling with it. Cantor, the mathematician largely credited with founding set theory, was born in St. Petersburg. His father was a merchant who drove his son to excel in whatever he did. Cantor's mother was a member of the Böhm family of musicians. Cantor himself displayed talents in art as well as music, but at the age of 17 he decided to "devote his life to mathematics."4 He attended the Polytechnicum in Zurich, and the University of Berlin. In 1869 , Cantor got a teaching job at the University of Halle, where he remained for the rest of his life.

In 1873 , in a letter to mathematician Richard Dedekind (1831-1916), Cantor pondered correspondences such as the one between natural numbers and even numbers, and wondered whether a similar correspondence could be established between the natural numbers and real numbers. He suspected not, but he couldn't see why. "I cannot find the explanation which I seek; perhaps it is very easy," Cantor wrote.  Famous last words.

A set whose elements can be paired off with the natural numbers is now said to be* enumerable* (or sometimes denumerable or countable). A set is enumerable if we can order the elements or list them in some way, because any list can be numbered - that is, paired off with the natural numbers starting with 1,2 , 3 , and so on. All finite sets are enumerable, of course. The real problem involves infinite sets.

For example, consider the integers including negative and positive integers as well as zero. Is this set enumerable? Yes, it is, because we can list all the integers starting at zero:

That's not the way the integers are usually listed, but this particular pattern clearly demonstrates that a single list contains all the integers.

Interestingly enough, the rational numbers are also enumerable. Let's begin with positive rational numbers, and let's not worry if we have a few duplicates in the list:

Do you see the pattern? With the first item in the list, the numerator and denominator add up to 2 . The next two items on the list have numerators and denominators that add up to 3 . The next three items on the list have numerators and denominators that add up to And so forth. A list that continues like this contains all the positive rational numbers. We can include negative rational numbers by just alternating between positive and negative. Therefore, the rational numbers are enumerable.

In a paper published in 1874, "On a Property of the Set of Real Algebraic Numbers",  Cantor showed that even the algebraic numbers are enumerable. As you'll recall, algebraic numbers are solutions to algebraic equations, which have the general form

where is a positive integer and are integers. For any particular algebraic equation, let's add up all of the coefficients (the values) and itself. Let's call that number the equation's height. For a particular height (for example, 5), there are a finite number of algebraic equations. Each equation has at most solutions. Thus, all the algebraic numbers can be listed in order of their heights and their solutions. The algebraic numbers are therefore enumerable.

What about the transcendentals? Can the transcendental numbers be listed in some manner? It hardly seems likely! There's not even a general procedure for determining whether a particular number is transcendental!

What about the real numbers, which encompass algebraic numbers and transcendental numbers? Can the real numbers be enumerated?

In that same 1874 paper where Cantor demonstrated that the algebraic numbers are enumerable, he also demonstrated that the real numbers are not enumerable.

Cantor began his proof by assuming that the real numbers are enumerable. He assumes that there exists some way to enumerate the real numbers, and that they've been enumerated in a list like so, symbolized by subscripted omegas:

Cantor is going to show that this list is incomplete - that no matter how this list was made, it simply cannot contain all the real numbers.

Pick any number (alpha) and a larger number (beta). You can represent these two numbers on a number line like so:

Now start going through your enumerated list of real numbers until you find the first two real numbers that are between and . These two numbers are greater than and less than . Call the lesser of these two numbers and the greater

Continue going through your list of real numbers from where you left off until you find two new numbers between and Call these two numbers and

And again:

It should be obvious that this process must continue forever. You'll always be able to find two more numbers between the last two numbers.

How do you know this? Easy: Suppose you get stuck at this point

where the superscript indicates prime marks, maybe a million billion trillion or so, but a finite number. Now, no matter how much you continue to search through the list of enumerated real numbers, you can't find another pair of numbers that falls between and . Then it's obvious that your list of real numbers is incomplete. The list is missing every number between and . For example, the number midway between and is the average of the two, or:

And that's just for starters. Your list is missing lots of numbers. That's how you know the process must continue forever. The alphas keep getting larger and the betas keep getting smaller, but the largest alpha can't get larger than the smallest beta. (When you find two new numbers that fall between the last alpha and beta, the smaller one is always the alpha and the larger one the beta.) Both the alphas and the betas have a boundary - a limit - that Cantor symbolizes using a superscripted infinity sign: and . Is it possible that is less than ? Take a look: No, that's not possible. If the alphas never get larger than and the betas never get smaller than , then the list of real numbers is missing every number between and , for starters:

It must be that is equal to . Cantor calls this limit (the Greek letter eta):

Because this has to be an infinite process (we've already established that it can't stop at some point), the alphas never reach and neither do the betas. Now, you know what that means, don't you? That means that is not in the original list of real numbers!

If were in the list, then it would turn up sometime when you were searching for the next alpha and beta, but consider the alpha and beta that turned up in the list right before :

We've run out of scenarios here. Nothing works, nothing makes sense, and it's all the fault of the original assumption - the assumption that we were able to enumerate the real numbers. It must be that we can't do that.

Integers are enumerable. Rational numbers are enumerable. Even algebraic numbers are enumerable. Real numbers, however, are not.

Cantor considered the non-enumerability of real numbers to be a new proof of the existence of transcendental numbers. (If transcendental numbers did not exist, real numbers would be the same as algebraic numbers and hence would be enumerable.) What Cantor eventually realized is that there are at least two kinds of infinity: There's an enumerable infinity and a non-enumerable infinity - an infinity of the natural numbers and an infinity of the continuum. Infinite sets of natural numbers, rational numbers, and even algebraic numbers are enumerable. When we throw in the transcendentals, suddenly we're in a whole different universe. We're looking at two different infinite cardinalities: One cardinality applies to natural numbers, rational numbers, and algebraic numbers. The other cardinality is that of the real numbers and the continuum.

Cantor's work was controversial in his day and has never entirely shed that controversy. Since Cantor, however, no mathematician has thought about infinity in quite the same way. Moreover, the distinction between enumerable and non-enumerable infinities has proved to be extremely useful, even if imagining just one simple type of infinity boggles the human mind.

In the popular mythology, Cantor himself went mad from contemplating infinity too much. It's true that Cantor spent the last twenty or so years of his life in and out of psychiatric hospitals, but it probably was a form of manic depression that would have manifested itself regardless of his occupation.  Still, the worst of Cantor's bouts with mental illness seem to have been triggered by fatigue and stress, and the stress may have been related to problems connected with the acceptance of his unconventional mathematical theories. In recuperation, Cantor pursued interests other than mathematics. He explored philosophy, theology, metaphysics, and the hypothesis that Francis Bacon wrote the plays attnbuted to William Shakespeare.

Finite sets and infinite sets have quite different characteristics. One big difference involves proper subsets, which are subsets that are not the same as the sets themselves. A proper subset of a finite set always has a smaller cardinality than the set itself. That much is obvious. A proper subset of an infinite set can also have a smaller cardinality than the set. (For example, the set of natural numbers is proper subset of the set of real numbers, and the two cardinalities are different. In some cases, however, a proper subset of an infinite set has the same cardinality as the set itself. This can only be true of infinite sets. The set of natural numbers is a proper subset of the set of integers, which is a proper subset of the set rational numbers, which is a proper subset of the set of algebraic numbers. Al these infinite sets have the same cardinality. They are equivalent.

It's also the case that various proper subsets of the real numbers are equivalent to each other. Consider the real numbers between 0 and 1 . These can be placed in a one-to-one correspondence with the real numbers greater than l. Just divide each number into 1 . For example, corresponds with corresponds with 4, corresponds with 10, and corresponds with 10,000 . This little fact proves to be very useful: It means that we can examine certain properties of real numbers restricted to the range between 0 and 1, and what we find will apply to all the real numbers. (Turing uses this concept in his paper, and Cantor used it as well.)

As Cantor explored infinite sets, he made other astonishing discoveries: He found that he could establish a one-to-one correspondence between the continuum - the real numbers on a line - and the two-dimensional points on a plane, and indeed the points in any -dimensional space.

For example, let's restrict ourselves to that segment of the plane with and coordinates between 0 and 1 . Each point on the plane can be expressed as a number pair , and each of the two numbers contains infinite digits following the decimal point. In the following expression, each digit of following the decimal point is symbolized by a subscripted :

Similarly for :

Now take these digits and interweave them into a single number:

That's one real number encapsulating two real numbers. Each two-dimensional point corresponds to a real number on the continuum. Hence, the collection of points on the plane has the same cardinality as the real numbers on a line. Cantor was so astonished by this discovery that German failed him. "Je le vois, mais je nele crois pas," he wrote to Dedekind.  I see it, but I don't believe it.

In 1891 , Cantor published another proof of the non-enumerability of real numbers,  and this proof has been blowing people's minds ever since. Cantor's proof involved sets rather than numbers and was more general than the example l'm going to show you, but the idea is the same. For reasons that will be very apparent, it's called the diagonal proof or the diagonal process or the diagonal argument or diagonalization. Whatever you call it, a diagonal is involved.

Let's restrict our attention to real numbers between 0 and 1 . Suppose we have devised some way to list all these real numbers. (As you may be anticipating. this is yet another reductio ad absurdum proof.) Suppose the list begins something like this:

We seem to be off to a good start. The list includes , that weird irrational number I showed earlier with the varying number of , and some others that aren't quite recognizable. Each number has an infinite number of decimal places (even if they're just ) and the list has an infinite number of numbers.

Even though this list is infinite, we can persuade ourselves that it's missing something. Let's look at the digits that form a diagonal through the list from upper-left to lower-right. These digits are shown here in bold face:

Now, use those bold-face digits to form a number:

Because the list of real numbers is infinite, and the number of digits in each number is infinite, this number has an infinite number of digits. Now increase each individual digit in this number by 1 . If the digit is 9 , make it 0 :

Is this new number in the original list? Let's be methodical about it: Is this new number the first number in the list? No, it's not, because the first digit of the first number in the list is 1 , and the first digit of the new number is 2 .

Is it the second number in the list? No again, because the second digit of the second number in the list is 5, and the second digit of the new number is

Is it the third number in the list? No, because the third digit of the third number in the list is 3 , and the third digit of the new number is 4 .

And so forth. The new number is not the -th number in the list because the -th digit of the -th number in the list is not equal to the -th digit of the new number.

Thus, the list is incomplete and our original premise is flawed. It's impossible to list the real numbers between 0 and 1 . Once again, we see that the real numbers are not enumerable.

What happens when you perform this same experiment on a list of algebraic numbers? We already know how to list algebraic numbers, so that's not a problem. When you construct a diagonal and change all the digits, the resultant number is not in the list. That means the resultant number is not an algebraic number. The resultant number is transcendental.

You could order your list of algebraic numbers in many different ways; you could create different rules for making the diagonal different from any number in the list; each time, you'll be creating another transcendental number.

In 1895, Cantor chose to represent the cardinality of the enumerable set of natural numbers (and thus, any enumerable infinite set) using the first letter of the Hebrew alphabet with a subscripted zero: , pronounced "aleph null." Cantor called this the first transfinite number. He combined this with other transfinite numbers , and so on) to create an entire mathematics of the transfinite. If the cardinality of enumerable sets is , what is the cardinality of the non-enumerable set of real numbers? Can we even represent that cardinality? Perhaps. Let's begin with an example involving finite sets. Here is a set of just three elements:

How many subsets of this set can you construct? (The set of all subsets of a set is called the power set.) You can try it manually, but just don't forget the empty set and the set with all three elements:

There are eight subsets of a set of three elements, and not coincidentally:

The exponent is the number of elements in the onginal set. The result is the number of subsets of that set. A set of 4 elements has to the power) subsets. A set of 5 elements has 32 subsets.

There's a more methodical way to enumerate these subsets that better reveals this relationship. Let's create a table with a column for each element in the original three-element set. Use 0s and ls to indicate whether that element is in each particular subset:

The successive combinations of and in the three columns are the same as the binary numbers from 0 through 7 . Three bits yield 8 binary numbers. The general rule is:

Cardinality of a power set

A set of 10 elements has a power set of 1,024 elements. A set of 100 elements has a power set of

The cardinality of this set is . How many subsets does it have? In other words, what is the cardinality of its power set? By analogy, it's

Perhaps further convincing is required. Let's construct a table similar to that for the finite set (except obviously not so complete). At the top of the columns we have all the elements of the set of natural numbers. Each column has a 0 or 1 indicating whether that number is included in each particular subset. The resultant subset is shown at the right:

What we are actually attempting here is a list of all possible infinite combinations of 0 and 1 . Let's put a little period before each of the sequences of numbers in the list:

These are binary numbers between 0 and 1, and (judging from the way we created these numbers) all the binary numbers between 0 and 1, and hence all the real numbers between 0 and 1. I showed earlier how the real numbers between 0 and 1 can be put into a correspondence with the totality of real numbers, which means that the real numbers can be put into a correspondence with the members of the power set of the natural numbers. This power set therefore has the same cardinality as the continuum.

The cardinality of the continuum is thus

where is the cardinality of the natural numbers.

Cantor proved that it is not possible for the members of any nonempty set to be put into a one-to-one correspondence with the members of its power set, a fact that's obvious for finite sets but not so obvious for infinite ones. This is now known as Cantor's Theorem, and it was the primary result of the 1891 paper that introduced the diagonalization technique. Just as a set can have a power set, a power set can have its own power set, and so on. All these sets have different cardinalities.

Cantor speculated that the cardinality of the continuum was the next higher transfinite number after , which is the transfinite number he called . This speculation is called Cantor's continuum hypothesis, and it can be expressed mathematically like this:

Cantor struggled to prove his hypothesis, but was never able to do so. The problem is that there could be some other transfinite number between and the cardinality of the continuum.

Regardless, the profound implication of all this is that the cardinality of enumerable sets is not only smaller than the cardinality of the continuum

but much, much, much, much, much smaller:

The only difference between the continuum and enumerable sets is the inclusion of transcendental numbers. We are compelled to conclude that transcendental numbers - which were not even proved to exist before 1844 - really account for the vast majority of all possible numbers - indeed, virtually all possible numbers.

For millennia, our ideas about numbers have been completely skewed and distorted. As humans we value neatness, order, and patterns, and we live in a world of compromise and approximation. We're interested only in numbers that have meaning to us. From counting farm animals, we have invented the natural numbers. From measurement, we have invented the rational numbers, and from higher mathematics, we have invented the algebraic numbers. We have plucked all these numbers from the continuum while ignoring the vast depths in which they swim like microscopic bacteria in the ocean. We live under the comforting illusion that rational numbers are more common than irrational numbers, and algebraic numbers are more numerous than transcendental numbers, and certainly they are in our manufactured lives. In the realm of the continuum, however, virtually every number is transcendental.

What are all these transcendental numbers? Most of them are just sequences of random digits, without rhyme, reason, or meaning. Indeed, any sequence of random digits is almost assuredly transcendental.

Toss a dart at a dart board. Now measure the distance between the dart and the exact center of the bull's eye using progressively higher magnification and finer rulers. First measure to the whole number of inches, and then to the whole number of tenths of an inch, and then to the whole number of hundredths of an inch, and you'll be going on forever. The probability that the distance is a rational number - inches exactly, for example - is negligible.

Of course, at some point when measuring the dart we're going to have to deal with the real world. It's not like the dart is going to split an atom! No, the dart will wedge between discrete molecules of cork, and as our magnification gets into the realm of these molecules, we see that they're vibrating too much for an accurate measurement, and there are visual distortions due to the finite wavelength of light, and at some point the Heisenberg Uncertainty Principle kicks in, and then we can't really be sure of anything any more.

At those magnifications, the whole idea of a "continuum" seems hopelessly quaint, and we may even be tempted to look outwards from the molecules to the universe at large, and speculate whether infinity exists at all in the real world - particularly considering that the Big Bang very likely unleashed only a finite amount of matter and energy at a point in time in a finite past to create a universe seemingly characterized by a discrete rather than continuous structure. We might wonder, too, if Cantor's exploration into enumerable and nonenumerable sets is just some highly abstract (and still somewhat suspect) area of speculative mathematics, or if there's actually some utility in this exercise.

Although it's hard to find infinity in the real world, there is still much usefulness in the mathematical concepts of infinity. It turns out that certain mathematical proofs that have actual real-life implications - including the one in Turing's paper - hinge on the difference between enumerable sets and non-enumerable sets, as illustrated by this diagram:

You see the problem?