Published in the St. John's Review, XLIV, 2 (1998) 35-59. Copyright © 1998, Peter Suber.

This crash course is designed to stand alone. But it also functions as the appendix to my essay, Infinite Reflections.

A Crash Course in the Mathematics
Of Infinite Sets Peter Suber, Philosophy Department, Earlham College

Don't be surprised if this is easier than you thought. Set theory requires no algebra or calculus. It is much more primitive than those branches of mathematics, and rests on very simple notions. Moreover, the proofs will be unusually short and uncomplicated.

What will be difficult? Most of the results we will prove depend critically on those that came before; but I cite the needed prior theorems by number to make this kind of back-tracking easier. The notation may be new, and for many people unfamiliar notation raises the hair on the back of the neck. But most of the notation may be ignored. I include it mainly so that if you read further on this subject, you will be equipped. I honestly don't think the compressed exposition needed for a crash course increases the difficulty —in part because I've been more long-winded than most mathematicians, and in part because some compression and conciseness helps keep all the relevant ideas in the head at the same time, which aids comprehension. Some of the proofs, short and simple as they are, will make you dizzy. But that's part of the amazing phenomenon to be savored, not a difficulty to lament.

To begin:

Almost a definition. Intuitively, a set is a collection of elements.

• The intuitive notion of a set leads to paradoxes, and there is considerable mathematical and philosophical disagreement about how best to refine the intuitive notion. Fortunately, none of the disagreements or refinements matters for our purposes here. I only bring up this complexity so that you'll accept the intuitive notion in place of a refined definition for the purposes of this crash course.
• Notation. When we want to list the members of a set, we use curly brackets. So if set S contains elements A, B, and C, then we say S = {A, B, C}.
• The null set is the empty set or the set with no members. Notation: Ø. Hence, Ø = {}.

Abbreviation. For if and only if I will sometimes write simply iff.

Definition. Set A is a subset of set B iff all the members of A are also members of B.

• Notation. A B.
• It follows from this definition that every set is a subset of itself.

Definition. Set A is a proper subset of set B iff all the members of A are also members of B, but not all the members of B are members of A.

• Notation. A B.
• It follows from this definition that no set is a proper subset of itself.

Definition. The cardinality of a set is the number of members it contains.

• Notation. The cardinality of set S is |S|. For example, if S = {A, B, C}, then |S|=3.
• Hence while S is a set, |S| is a number. When S is an infinite set, |S| will be an infinite number.
• Technically, |S| is a cardinal number, as opposed to an ordinal number. This doesn't matter for what follows, but it might help you remember the term cardinality. A cardinal number answers the question how many? An ordinal number answers the question which one? Natural numbers are used both ways in different contexts. For example, 3 is used as a cardinal number when we say there are "three blind mice" or "three bags full", but it is used as an ordinal number when we say "the third pig built with brick" or "curtain number three". Sets have cardinality, that is, size or magnitude: they have some definite number of members. But they do not have ordinality: their members are not in any particular order; for example, {A, B, C} = {B, A, C}. In this brief exposition, I introduce the mathematics of infinite cardinal numbers and ignore the infinite ordinals.

Definition. Two sets can be put into one-to-one correspondence iff their members can be paired off such that each member of the first set has exactly one counterpart in the second set, and each member of the second set has exactly one counterpart in the first set.

• Notation. If sets A and B can be put into one-to-one correspondence, then we say A B.

Putting two infinite sets into one-to-one correspondence is an infinite task, and we don't pretend that we can do it (that is, finish it) in finite time. To show that an infinite set, like the even numbers, can be put into one-to-one correspondence with another, like the odd numbers, we need only produce a rule-governed sequence for each set which runs through the members without omission or repetition, for example, 2, 4, 6... and 1, 3, 5.... If we can do so, then we know that the nth term of one sequence will have a counterpart in the nth term of the other, and vice versa, guaranteeing one-to-one correspondence all the way out.

We will soon see that there are infinite sets larger than the set of natural numbers (Theorem 3 below), and for them no such sequences can be constructed. However, for cardinalities of that magnitude, most of our proofs will show the absence or failure, rather than the presence, of one-to-one correspondence.

Definition. Two sets have the same cardinality iff they can be put into one-to-one correspondence; or, A B iff |A| = |B|.

• This definition applies to infinite as well as to finite sets.
• It follows from the last three definitions that set A has a larger cardinality than set B iff both (1) a proper subset of A and the whole of B can be put into one-to-one correspondence, and (2) the whole of A cannot be put into one-to-one correspondence with any proper subset of B.

Definition. The power set of a set S is the set of all the subsets of S.

• Notation. The power set of S is *S.
• For example, if S = {A, B, C}, then *S = {{A,B,C}, {A,B}, {A,C}, {B,C}, {A}, {B}, {C}, Ø}.
• The power set of a given set always contains the given set itself and the null set.
• Note that while the members of S may be any sort of things (bugles, baseball teams, Byronic poems), the members of *S are other sets.
• |*S| is the cardinality of the power set of S. As you can see from the example above, when S has 3 members, then *S has 2³ or 8 members. In general, when S is finite, then |*S| = 2 ^{| S |}.
• We will assume the power set axiom, i.e. that all sets have power sets.

Reminder. The natural numbers are the whole positive numbers (sometimes called the "counting numbers"), including zero: 0, 1, 2, 3 ....

• This is really a definition, but by calling it a "reminder" I'm hoping to get on your good side.
• Notation. The set of natural numbers is designated by N.
• Notation. The number of natural numbers is designated by À₀. "À" is the first letter of the Hebrew alphabet, pronounced Aleph. "À₀" is pronounced Aleph-null or Aleph-nought. We will justify the zero subscript when we prove that no infinite set has a smaller cardinality than the set of natural numbers (Theorem 6).
• Hence À₀ = |N|, by definition.
• Now you know how many natural numbers there are: À₀. But this is not profound. So far we've only invented a name (numeral) for the number of natural numbers.

Definition. A set is countable iff its cardinality is either finite or equal to À₀. A set is denumerable iff its cardinality is exactly À₀. A set is uncountable iff its cardinality is greater than À₀.

• The null set is countable. The finite set, {A, B, C}, is countable. The infinite set, N, is countable and denumerable. Sets with a larger cardinality than N are uncountable.

Definition. A transfinite number or transfinite cardinal is the cardinality of some infinite set.

• If we use the term "infinite" in a restricted and precise way, then "transfinite" is just a synonym for it. We could avoid fancy new terms to prevent confusion. However, "infinite" has many imprecise and non-technical uses —for example, the infinite setting on a camera's range-finder— so it often helps to use a technical term to avoid ambiguity.

Reminder. The integers are the natural numbers plus their negative counterparts, ...-3, -2, -1, 0, 1, 2, 3....

• Notation. The set of integers is designated by Z.

Reminder. The rational numbers are the integers plus the rational fractions (those that can be expressed as the ratio of two integers).

• Notation. The set of rational numbers is designated by Q.
• For example, 0.75 is a rational fraction because we can express it as the ratio of two integers, namely, 3/4. Therefore it is a rational number.
• The irrational numbers are the fractions that are not rational numbers, both positive and negative. For example, we can prove that pi (3.14159...) cannot be expressed as the ratio of two integers. Therefore it is an irrational number.

Reminder. The real numbers are the rational numbers plus the irrational numbers.

• Notation. The set of real numbers is designated by R.

We started with the natural numbers (N), then added infinitely many negative whole numbers to get the integers (Z), then added infinitely many rational fractions to get the rationals (Q), and then added infinitely many irrational fractions to get the reals (R). It's tempting to conclude that with each infinite addition we increased cardinality, or in short:

|N| < |Z| < |Q| < |R|

But is this true? Here we encounter one of the first points at which the mathematics of the infinite violates our intuitions. If each addition did increase cardinality, that would violate our sense that "infinity is infinity" —or that all infinite sets are equal in cardinality. But if any of these additions did not increase cardinality, that would violate our sense that the cardinality of a set grows when we add members. Before we learn the truth, and see how it violates our intuitions, it's wise to remember that its negation would also have violated our intuitions. At the very beginning, therefore, we should not demand conformity with our intuitions so much as clear definitions and rigorous proofs.

Foreshadowing. Both the intuitions mentioned in the preceding paragraph are false. (1) Not all infinities are equal in cardinality, and (2) some additions, even infinite additions, do not increase cardinality. The string of inequalities, |N| < |Z| < |Q| < |R|, is also false.

Theorem 1. The set of integers has the same cardinality as the set of natural numbers, or |N| = |Z|.

• Proof. If we try to list the integers, we note that they trail off with three dots in two directions: ...3, 2, 1, 0, 1, 2, 3.... Left in that form they would be hard to put into one-to-one correspondence with the natural numbers. But if we alternate one positive and one negative integer, then they form a single infinite sequence, 0, 1, -1, 2, -2, 3, -3..., and we can easily put them into one-to-one correspondence with the natural numbers, 0, 1, 2, 3, 4, 5, 6, 7....

This method of alternating the members of two infinite sequences in order to make a single sequence is called interlacing. Cantor used it often and so will we.

Theorem 2. The set of rational numbers has the same cardinality as the set of natural numbers, or |N| = |Q|.

• It's much harder to find a method for putting the rational numbers into one-to-one correspondence with the natural numbers than it was for the integers. The reason is that the rational numbers are dense, that is, between any two of them there is a third. For example, between 123/987 and 124/987 there is 123.5/987, which resolves into 247/1974. This means, in fact, that between any two there are infinitely many others. It also means that for any given rational number, there is no such thing as the next greater, or the next lesser, rational number. But Cantor found a very clever method for laying out the rational numbers so that they can be put into one-to-one correspondence with the naturals.
• Proof. The following table shows Cantor's method for putting the rationals and naturals into one-to-one correspondence:

		Numerators
		1	2	3	4...
Denominators	1	1/1	2/1	3/1	4/1...
	2	1/2	2/2	3/2	4/2...
	3	1/3	2/3	3/3	4/3...
	4...	1/4	2/4	3/4	4/4...

The two shaded axes list all the possible natural number numerators, and all the possible natural number denominators. The interior part of the table uses the axes to compose all the rational fractions, which are all the rational numbers. Now we read off the rationals in this order: starting with the 1/1 in the upper left corner, we move right to 2/1, then diagonally down and to the left, then down, then diagonally up and to the right, and so on, eventually passing through every cell in the grid. The first 10 numbers in our journey are: 1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4.... But as the following table shows, this sequence can be put into one-to-one correspondence with the natural numbers:

Rationals	1/1	2/1	1/2	1/3	2/2	3/1	4/1	3/2	2/3	1/4...
Naturals	0	1	2	3	4	5	6	7	8	9...

This method of enumerating the rationals includes each rational number more than once. For example, it will include 1/1, 2/2, 3/3..., each of which is equal to 1. In fact, every rational number will be represented infinitely many times. Technically, this violates the conditions of strict one-to-one correspondence. But in fact we can leave the duplicates in the enumeration without harming the proof, for we are then proving that the rationals plus the duplicates is still no greater in cardinality than the naturals. This means that the rationals are at most as numerous as the naturals. We already know that the rationals are at least numerous as the naturals (because the naturals are a proper subset of the rationals). Therefore, the rationals are exactly as numerous as the naturals.

(Can you see why if some set A is at least as numerous as another set B, and at most as numerous as B, then it must be exactly as numerous as B?)

In Theorems 1 and 2 we saw that two kinds of infinite addition to an infinite set did not increase the cardinality of the original set. But we cannot generalize too quickly and say that such additions will never increase the cardinality of the original set. Our next theorem shows that some sets can indeed be larger than the natural numbers, and in Theorem 16 we will see that the additions to the naturals required to generate the real numbers do indeed create an uncountable set.

Theorem 3. The power set of the set of natural numbers has a greater cardinality than the set of natural numbers, i.e. it is uncountable; or |*N| > |N|.

• Proof. We give a negative proof, and assume that the natural numbers can be put into one-to-one correspondence with the sets of natural numbers. Let this hypothetical pairing off be represented by the leftmost columns of the following table.

  The nat. nos. in 1-1 correspondence with the sets thereof (hypothetically)			Are these nos. members of the set listed at left?
  			0	1	2	3...
  0		evens	yes	no	yes	no...
  1		odds	no	yes	no	yes...
  2		squares	yes	yes	no	no...
  ...		...	...	...	...	...

  In the shaded row of the table we again enumerate the natural numbers. The "yeses" and "noes" in the body of the table below them tell us whether the natural numbers in the shaded row above them are members of the sets to the left of them. For example, take the "yes" written in red. It is in the column of natural number 1, and in the row of the set of odd numbers; it says "yes" because 1 is indeed a member of the set of odd numbers. In this way, we represent every set of natural numbers (down the left column) as an infinite string of "yeses" and "noes". Conversely, we can read any string of "yeses" and "noes" as code for a particular set of natural numbers.

  From the "yes" in the upper left corner of the block of "yeses" and "noes", move diagonally downward and to the right, following the yellow cells. Toggle each "yes" we encounter to a "no" and vice versa. The resulting infinite string of "yeses" and "noes" is demonstrably different from every row of the infinite table, for it differs from the first row in the first term, from the second row in the second term, and so on. When we read it as set of natural numbers, the set it represents is for the same reason demonstrably different from every set yet listed on the table. But this contradicts our assumption that we had exhaustively listed and paired off all the sets of natural numbers. Therefore our assumption is false, and the natural numbers cannot be put into one-to-one correspondence with the sets of natural numbers.

  We're almost done. If the naturals and the sets of naturals cannot be put into one-to-one correspondence, then one has a larger cardinality than the other. The power set of the naturals must have the greater cardinality, for one of its proper subsets, {{0}, {1}, {2}, {3}...}, can be put into one-to-one correspondence with the naturals, 0, 1, 2, 3.... Therefore there are more sets of natural numbers than natural numbers.

This technique of moving down the diagonal of a table, changing every row in some way, and thereby constructing a new item that differs from every row in some definite respect, is called diagonalization. It is one of Cantor's most ingenious methods for gaining leverage on infinite sets. We'll use diagonalization often.

To establish Theorem 3, we used a negative proof. In a negative proof we assume the negation of the desired conclusion and show that that assumption leads to a contradiction; then we conclude that assumptions is false, which is the same thing as to conclude that the desired conclusion is true. It is a special case of the rule of inference, called modus tollens, by which we infer that any statement that implies a falsehood is false. Since it is so hard to grapple with infinite sets directly, negative proofs are common in this branch of mathematics. However, the most important skeptics of Cantor's results, called intuitionists, refuse to use negative proofs in dealing with infinite sets —although they are willing to use negative proofs in other areas of mathematics. The issue between Cantor and the intuitionists is whether this refusal is arbitrary, or whether we should distrust negative proofs in those domains where there is no possibility of verifying our results through intuition.

Theorem 4. The cardinality of the power set of an arbitrary set has a greater cardinality than the original arbitrary set, or |*A| > |A|.

• This is called simply Cantor's Theorem. It generalizes the previous theorem, in which we proved that the power set of a particular set, N, had a greater cardinality than the original. The present theorem is trivial for finite sets, but is fundamental for infinite sets.
• Proof. Let A be an arbitrary set of any cardinality, finite or infinite. Again we supply a negative proof, and assume that the members of A can be put into one-to-one correspondence with the subsets of A. Take any one of the supposed ways of pairing off the members of A with the subsets of A. Let us say that if a member of A is paired with a subset of A of which it happens to be a member, then it is happy; otherwise it is sad. Let S be the set of sad members of A. Clearly S is one of the subsets of A. Therefore S is paired off with one of the members of A, say, x. Is x happy or sad? If x is happy, then x is a member of the set to which it is paired, which is S, but that would make it sad. If x is sad, then x is not a member of the set to which it is paired, which is S, but that would make it happy. So if x is happy, then it is sad, and if it is sad, then it is happy. Our assumption implies a contradiction and is therefore false. So the members of A cannot be put into one-to-one correspondence with the subsets of A.

But if A and *A cannot be put into one-to-one correspondence, then they cannot have the same cardinality. If so, then the larger one must be *A, for A can be put into one-to-one correspondence with a proper subset *A. For example, if the members of A are A1, A2, A3..., then they can be put into one-to-one correspondence with this subset of *A: {{A1}, {A2}, {A3}...}.

Many profound consequences follow directly from Cantor's theorem. But we make the most important of them explicit in the next theorem.

Theorem 5. If S is a set of any infinite cardinality, then its power set has a greater infinite cardinality, or |*S| > |S|.

• This follows directly from Cantor's Theorem (Theorem 4). Cantor's theorem applies equally to finite and infinite sets; this corollary focuses on the important consequence for infinite sets.
• If we follow the notation for finite sets, and say that a set of cardinality a has a power set of cardinality 2^a, then this theorem asserts that 2^a > a, for each transfinite cardinal a.
• This theorem asserts that for any infinite cardinality, there is a larger infinite cardinality, namely, the cardinality of its power set. Hence, there is an infinite series of infinite cardinal numbers. We will meet some of the infinite cardinals larger than N shortly.
• This theorem also implies that, for every set, there is a greater set. It follows that there is no set of all sets, or no set of everything.

It follows from Theorem 5 that "infinity" is not synonymous with "totality", a clarification which alone dispells many of the ancient conundrums and paradoxes surrounding the infinite.

Speaking of the infinite series of infinite numbers which Cantor proved to exist, David Hilbert said (in 1910) that, "No one shall drive us from the paradise which Cantor created for us," and (in 1926), "This appears to me to be the most admirable flower of the mathematical intellect and one of the highest achievements of purely rational human activity."

Now that we have proved there is an infinite series of infinite cardinals, it is well to prove that À₀ truly designates the smallest of them.

Theorem 6. No infinite set has a smaller cardinality than a denumerable set (or, none is smaller than the set of natural numbers).

• Proof. Let S be a set of any infinite cardinality. Clearly we may take away one of its members, call it S₁, without emptying S. We may take another, S₂, and another, S₃, and so on, each time without emptying S. In this way we may carve out a denumerable proper subset from S, namely, {S₁, S₂, S₃...}. But S had any infinite cardinality. Hence all infinite sets have at least one denumerable proper subset. Hence the cardinality of a denumerable set is not greater than any transfinite cardinality; or, it is the smallest transfinite cardinality.

We know from the proof of Theorem 6 that every infinite set has an infinite proper subset which consists of the original set minus denumerably many members. This fact has a beautiful implication. If the "largeness" of an infinite set is measured by its cardinality, then the smallest infinite set is a denumerable set or one with a cardinality of À₀. But if the largeness of an infinite set is measured by the largeness of its proper subsets, then there is no smallest infinite set: they nest downward ad infinitum without ever losing infinite cardinality.

À₀ designates the cardinality of the natural numbers by definition, which is demonstrably the smallest infinite cardinality (Theorem 6). This justifies the zero subscript. À₁ is by definition the next greater infinite cardinality after À₀, just as À₂ is by definition the next greater cardinal after À₁, and so on. As we will see in the section on the continuum hypothesis below, even though there is an infinite series of infinite cardinals (Theorem 5), it is impossible to say, in standard set theory, which one of them is À₁, which one is À₂, and so on.

Theorem 7. A denumerable set plus a new member is still denumerable, or À₀ + 1 = À₀.

• Proof. If we add element A to the set of natural numbers, giving us {A, 0, 1, 2, 3...}, then the resulting set can still be put into one-to-one correspondence with the natural numbers. A would be paired with 0, 0 with 1, 1 with 2, and so on.
• As a corollary it follows that we may add a second member, and a third, and so on. À₀ + 2 = À₀, À₀ + 3 = À₀, À₀ + n = À₀ for every positive integer n.
• In fact we may add denumerably many new members, A, B, C... to the original denumerable set without increasing its cardinality. The enlarged set, {A, B, C..., 0, 1, 2...}, can be put into one-to-one correspondence with the natural numbers if we interlace its members thus: A, 0, B, 1, C, 2.... (See Theorem 1.) Therefore, À₀ + À₀ = À₀.

Theorem 8. A denumerable set may have denumerably many members removed (in certain ways) without reducing the cardinality of the original set.

• Proof. We need only regard the given denumerable set as two denumerable sets interlaced, then 'unlace' them, then discard one of them. If {A₁, A₂, A₃...} is the original denumerable set, then we can separate out the set of even-numbered members, {A₂, A₄, A₆...}, from the set of odd-numbered members, {A₁, A₃, A₅...}, each of which is denumerable. If we discard one of the resulting sets, the other one has the same cardinality as the original.
• Note that this theorem only applies to the removal of certain denumerable subsets from a given denumerable set. For if the denumerably many members we subtracted happened to comprise the entire membership of the original denumerable set, then clearly the result would not be a denumerable set. So we cannot conclude in general that À₀ - À₀ = À₀.

Theorem 9. If we remove denumerably many members from an uncountably large set, the result will have the same cardinality as the original.

• Proof. Let U be any uncountably large set. We know from Theorem 6 that U has at least one denumerable proper subset, say D. And we know from Theorem 8 that we can remove denumerably many members from D, in certain ways, without reducing the cardinality of D. If we do so, then we thereby remove denumerably many members from U without reducing the cardinality of U.

Theorem 10. Every infinite set can be be put into one-to-one correspondence with at least one of its proper subsets.

• Proof. Let S be a set of any infinite cardinality. If S is countable, then Theorem 8 tells us that we may produce a proper subset of S without reducing S's cardinality. But if S and that proper subset have the same cardinality, then they can be put into one-to-one correspondence. If S is uncountable, then we have the same result using Theorem 9 instead of Theorem 8.
• Together with the trivial truth that no finite set can be put into one-to-one correspondence with any of its proper subsets, this theorem establishes the important result that all and only infinite sets possess the property that they can be put into one-to-one correspondence with at least one of their proper subsets. It follows that this property is a necessary and sufficient condition for being an infinite set. It may therefore be taken as the defining condition of infinite magnitude, and its absence as the defining condition of finitude.

Definition. Let us say that a text is a finitely long string of symbols, whose symbols are chosen from a finite set (or alphabet).

• For our purposes here we needn't even say that the string conforms to the rules of some grammar. When interpreted, the text may be a name, a sentence, a paragraph, a chapter, a book, or a library.

Theorem 11. There are only countably many texts.

• Proof. By definition there are only finitely many symbols in the "alphabet" from which we may compose texts. List them exhaustively in any order. To the first symbol, assign the numeral "10". To the second, assign the numeral "100". To the third, assign "1000" and so on. In general, to the nth symbol in the alphabet we assign the numeral in which "1" is followed by n zeroes. Now in each text, replace the symbols with their corresponding numerals. Concatenate the numerals so that, for example, "10 100 1000 10" becomes "10100100010". We now have a method for converting every distinct text into a distinct natural number. But there are only À₀ natural numbers. Therefore there are at most À₀ texts.

This theorem has deep consequences. We will soon prove (Theorem 16) that there are uncountably many real numbers. But by the present theorem, there are only countably many names for anything. Hence, only a countable subset of the real numbers can be named. Or conversely (by Theorem 9), uncountably many real numbers cannot be named.

This theorem also means that there are at most countably many theorems in any axiom system (in which theorems are finitely long). But we know from Theorem 3 that there are uncountably many sets of natural numbers. If there is at least one truth of number theory for each set of natural numbers (e.g. that some number n belongs to that set), then there will be uncountably many truths of number theory. Therefore, there are uncountably many more truths of number theory than there are texts. It follows that every axiom system intended to capture number theory is doomed to incompleteness.

Theorem 12. The number of points on a finite line segment is the same as the number of points on an infinite ray.

Until I can draw a GIF for this theorem, imagine a large letter "Z". Label the point at the upper left, C, that at the upper right, D, that at the lower left A. Imagine that the bottom bar continues infinitely to the right, and that point B is somewhere along it to the right of A.

• Proof. Let segment CD be parallel to ray AB. From point C we can draw a line through any point of AD, except D itself, and the line we draw will intersect AB somewhere; in this way we can pair any point on AD with exactly one point on AB. Conversely, from point C we can draw a line through any point of the ray AB, and the line we draw will intersect AD somewhere; in this way, we can pair any point on AB with exactly one point on AD. But this means the points on AD, minus D itself, and those on AB can be put into one-to-one correspondence. Hence they contain the same number of points.

We have yet to say how many points are on AD (minus D itself) or the infinite ray AB, but we know it will be some infinite cardinality. Now since any infinite cardinal plus one equals the original infinite cardinal (Theorem 7), we may add back the point D, which we omitted above, without changing the cardinality of the set of points on the segment.

Theorem 13. The number of points on a finite line segment is the same as the number of points on an infinite line.

• The proof is a simple variation on the proof for Theorem 12. Imagine the mirror image of the figure used in Theorem 12 (a "backward Z"), with a new point, D', to the left of C, and a new point, B', to the left of A. We would then prove that two line segments (AD and AD') together contain the same number of points as the infinite line. But the two line segments together make one longer, though still finite segment. Therefore, the number of points in a finite segment equals the number of points on an infinite line.

Definition. The number of real numbers is the same as the number of points on an infinite line; or in the jargon, the numerical continuum has the same cardinality as the linear continuum.

• Notation. Let c (lower-case "c" for "continuum") designate the cardinality of the continuum —or equivalently, the cardinality of the set of real numbers. Hence c = |R| by definition.

Theorem 14. c + c = c.

• Proof. One finite line segment of arbitrary length has c points (Theorems 12 and 13). A second of arbitrary length has c points. Together they make a longer, though still finite line segment, hence one which has c points.
• Therefore we have as corollaries, 2c = c, 3c = c, and nc = c for every positive integer n.

Theorem 15. À₀ · c = c.

• Proof. Think of an infinite line as marked off into unit segments, like a ruler. Clearly the segments could be put into one-to-one correspondence with the natural numbers. Hence there are denumerably many, or À₀, such segments. But from Theorem 13 we know that each segment has c points. But the whole line also has c points (by definition of c). Hence the whole line has as many points, c, as the number of segments, À₀, times the number of points per segment, c.

Theorem 16. The set of real numbers is uncountable, or |R| > À₀.

• Equivalently, this theorem asserts that c > À₀.
• Proof. Again we use a negative proof. Assume that the real numbers can be put into one-to-one correspondence with the natural numbers. Take the set of real numbers between 0 and 1. Express terminating decimal fractions as non-terminating decimal fractions; for example, 0.5 becomes 0.4999.... Now under our assumption pair off the natural numbers with the reals between 0 and 1, thus:

  0		0.	d	d	d	d	...
  1		0.	d	d	d	d	...
  2		0.	d	d	d	d	...
  ...		...

  where d is some digit.

  Now starting with the upper left d, move diagonally down and to the right, following the yellow highlights. Change each d we encounter to some other digit, for example, incrementing it by one, and changing 9 to 0. In this way we construct a new decimal fraction that is demonstrably nowhere on our list, for it differs from the first one in the first decimal place, from the second in the second place, and so on. But this contradicts our assumption that we have exhaustively listed all the real numbers between 0 and 1. Therefore the assumption is false and the reals cannot be put into one-to-one correspondence with the naturals. But the reals are at least as numerous as the naturals and cannot have the smaller cardinality. Therefore, the cardinality of the set of real numbers is greater than the cardinality of the set of natural numbers.

Now we have only to prove that the number of reals between 0 and 1 is the same as the number of all the reals. But this follows directly from Theorem 13.

Theorem 17. The power set of the set of natural numbers has the same cardinality as the set of real numbers, or |*N| = |R| = c.

• Proof. We know from the proof of Theorem 3 above that every set of natural numbers can be represented as a denumerable string of "yeses" and "noes". These denumerable strings, in turn, can be put into one-to-one correspondence with the denumerable strings of "1's" and "0's". These strings, in turn, can be put into one-to-one correspondence with the real numbers between 0 and 1 if we put a decimal point at the left end each denumerable string of 1's and 0's, and regard the result as a fraction in base two. (We can purge this set of numeral strings of repetitions without reducing the cardinality of the set; if you don't believe me, see the postscript below.) Finally, these real numbers between 0 and 1 can be put into one-to-one correspondence with all the reals, as we saw in Theorem 13.
• Postscript. To convert a string of 1's and 0's into a binary fraction, just tack a decimal point (or a zero and then a decimal point) onto the left end. For example, 111000... becomes 0.111000..., which equals 1/2 + 1/4 + 1/8 + 0/16 + 0/32.... Some of these fractions will equal others, for example, 0.1000... = 0.0111.... (For clarity, remember that in base 10, 0.5000... = 0.4999..., as we saw in Theorem 16.) There are at most countably many such repetitions. We know this because if we take all the fractions that consist of "000..." at some point in their expansions, and cut off the trailing zeroes, we will produce distinct, finite strings of 1's and 0's. But there are at most countably many such finite strings, according to Theorem 11. Now we know from Theorem 16 that there are uncountably many real numbers between 0 and 1. Hence to delete the countably many repetitions would leave us with the same uncountable cardinality we started with, according to Theorem 9.
• Remembering that |N| = À₀ (by definition), we may use the notation introduced in Theorem 5 to restate this theorem thus: c = 2^À₀ (2 to the power of À₀, in case your browser choked on this expression).

Theorem 18. The set of points in a square has the same cardinality as the set of points on one of its edges (namely, c).

• Proof. We know from Theorems 12 and 13 that the number of points in a finite line segment is c. Now we need only show that the number of points inside a square is also c. First, think of left and bottom edges of the square as collinear with the x and y axes of a Cartesian coordinate system. Every distinct point inside the square, therefore, has a distinct pair of real numbers to identify it; one is its position on the x axis, the other its position on the y axis. Now interlace these two numbers as we did in Theorems 1 and 7. For example, if the x axis position is 0.125000... and the y axis position is 0.333..., then interlace these two decimal fractions digit by digit to make 0.1323530303030.... We now have a single real number, rather than a pair of real numbers, to correspond to each point inside the square. Each of these new, interlaced numbers is a real number between 0 and 1. We know from Theorem 16 that there are at most c of these. But since they correspond to the points inside a square we also know that there are at least c of them. Therefore, there are exactly c of them.
• Intensively for the three years from 1871 to 1874 Cantor labored to prove this theorem false. Then he surprised himself by proving it true. "I see it, but I don't believe it," he wrote to Dedekind.

Theorem 19. c · c = c.

• This theorem follows directly from Theorem 18.
• As corollaries of this theorem, we have c · c · c = c, and c · c · c · ... · c = c, or in short, cn = c when n is any positive integer.

Theorem 20. The set of all points in a cube has the same cardinality as the set of all points in one of its edges, namely, c.

• The proof is a simple variation of that for Theorem 18. In fact, it is equivalent to one of the corollaries of Theorem 19. Each point inside the cube will have three coordinates, not two. Hence we interlace three decimal fractions, not two. The rest of the proof is the same as for Theorem 18.

Theorem 21. The set of all points in an infinite plane has the same cardinality as the set of all points in a finite line segment, namely, c.

• Proof. Think of the plane as marked off into an infinite number of square cells, like graph paper. First we show that there will be denumerably many, or À₀, such square cells. Pick one cell arbitrarily, and number it 0. Go to the cell above it and number that cell 1. Go one cell to the right and number it 2. Continue in this way to circle the "0" cell. The result will be a spiral that would eventually cover the plane. Yet each cell contains a natural number. Hence the cells and the natural numbers can be put into one-to-one correspondence. Second we note that each cell contains c points, under Theorem 18. Therefore, the number of points in the infinite plane is the number of cells, À₀, times the number of points in a cell, c (by Theorem 18), which we know is equal to c (by Theorem 15).

Theorem 22. À₀ · À₀ = À₀.

• The proof of this theorem was already encapsulated in the proof of Theorem 21 when we showed that there were denumerably many, or À₀, cells in the infinite graph paper of the Euclidean plane. But another way to ascertain the number of such cells is to take the product of the 'length' of the plane (in cells) and the 'width' of the plane (in cells). But the plane is À₀ cells 'high', and À₀ cells 'wide'. Hence the number of cells is À₀ · À₀. However, we already know the number of cells (from Theorem 21) to equal À₀.

Theorem 23. The set of all points in infinite, 3-dimensional, Euclidean space has the same cardinality as the set of all points in a finite line segment, namely, c.

• The proof is a variation on that of Theorem 21. We divide the space into cubes, rather than the plane into squares. Our spiraling path which puts the natural numbers into one-to-one correspondence with the cubes will be more complex, but perhaps you can visualize it. The rest of the proof is the same, except that we use Theorem 20 rather than Theorem 18.

Theorem 24. The set of all points in À₀-dimensional space has the same cardinality as the set of all points in a finite line segment, namely, c).

• Proof. If the set of all points in 3-dimensional space is c³, then the set of all points in À₀-dimensional space is c^À₀. But under Theorem 17, the latter number equals (2^À₀)^À₀, which in turn equals 2^{(À₀ · À₀)}, which (by Theorem 22) equals 2^À₀, which (by Theorem 17) equals c.

Definition. The continuum hypothesis (CH) asserts that there is no cardinal number a such that À₀ < a < c.

• Since by Theorem 17, c = |*N| = |R|, we could use any of the latter two expressions in place of c in stating CH.
• From CH it follows that the next largest transfinite cardinal after À₀ is c. Hence it also follows that c = À₁. Since we already know (from Theorem 17) that 2^À₀ = c, CH allows us to say that 2^À₀ = À₁.
• The commonly heard assertion that c = À₁ assumes CH. The widespread acceptance of the assertion by mathematicians therefore attests to the general acceptance of CH in the profession. (Without CH we have essentially no idea which Aleph corresponds to c, and we would know the cardinality of the naturals, integers, and rationals, but not the cardinality of the reals.)
• Cantor formulated CH, and spent the last years of his career unsuccessfully trying to prove it. His failure obsessed him and caused recurring bouts of serious depression. To prove or disprove CH was the first problem on David Hilbert's famous 1900 list of important unsolved problems in mathematics.
• Similarly, attempts to prove or disprove CH, or to prove it undecidable, consumed most of Kurt Gödel's 36 years at the Institute for Advanced Study. But he did produce an important partial proof. In 1938, Gödel showed that CH cannot be disproved from the axioms of Zermelo-Fraenkel (ZF) set theory, the closest thing we have to "standard" set theory. This meant that the negation of CH (notation: ~CH) could not be derived from the ZF axioms. And this in turn entailed that CH could be assumed and used in standard set theory without introducing any inconsistencies that were not already there. Gödel in effect proved that CH was as harmless as the less exotic propositions that already comprised set theory. That is the main reason why most mathematicians accept CH today.
• In 1963 Paul Cohen showed that CH cannot be proved from the ZF axioms. Together, Gödel and Cohen's results show that CH is independent of the ZF axioms: neither it nor its negation can be derived from them. Among other things, this means that CH is undecidable in ZF. After Euclid's parallel postulate, CH was the first major conjecture to be proved undecidable by standard mathematics. Its independence also means that ~CH is just as consistent with standard set theory as CH itself. This has allowed set theorists to develop set theories with and without it, just as geometers can develop geometries with or without Euclid's parallel postulate. Set theory with ~CH rather than CH is usually called Non-Cantorian set theory.

Definition. The generalized continuum hypothesis (GCH) asserts that 2^À_a = À_a+1 for every positive integer a.

• When a=0, GCH yields the ordinary CH.
• GCH implies that, starting with À₀, we can march through the transfinite cardinals with the power set operation, and will not skip any. It follows that for every infinite set S, if |S| = À_n, then |*S| = À_n+1, or that the only transfinite cardinals are |N|, |*N|, |**N|, |***N|, ....

Bibliographic note. Most of the theorems and proofs in this crash course were discovered by Georg Cantor (1845-1918) and published in a series of monographs starting in 1870. He published two summary statements of his results in 1895 and 1897, which have been translated into English by Philip E. B. Jourdain as Contributions to the Founding of the Theory of Transfinite Numbers, Dover Publications, 1955. My exposition of Cantor's results is indebted to three more recent authors: Stephen Cole Kleene, Introduction to Metamathematics, North-Holland Pub. Co., 1952; Abraham Fraenkel, Abstract Set Theory, North-Holland Pub. Co., 1953; and Geoffrey Hunter, Metalogic, University of California Press, 1971.

Some of the logic symbols in this file are GIFs; see my Notes on Logic Notation on the Web. Some are HTML characters using the Symbol Font; see Alan Wood's guide to its symbols.

Thanks to Emil William Kirkegaard for correcting a minor error in the exposition (February 2010).