# Gracious Living

Countability
November 2, 2010, 01:28
Filed under: Math, Set Theory | Tags: ,

(This is a follow-up to my post on cardinality. In it, I constructed a model of the natural numbers, which I also called $\mathbb{N}$, by $0=\emptyset,1=\{0\},2=\{0,1\}$, and so on [I used boldface for these sets last time, but it really isn’t necessary]. This set is “pure” and it exists by the Zermelo-Fraenkel axioms. Assuming the axiom of choice, it’s also the “smallest” infinite set up to bijection.   Below the jump, I talk about larger infinities.)

The cardinality of $\mathbb{N}$ is called $\aleph_0$ (that’s “aleph-null,” the aleph is the first letter of the Hebrew alphabet). I’d say this is the most important cardinality because it’s the largest one you can say anything definite about. Call a set countable if it bijects onto a subset of $\mathbb{N}$, so its cardinality is at most $\aleph_0$.1 Intuitively, what this means is that you can arrange the elements of a countable set in a list: the zeroth, first, second, third, and so on. As an example, $\mathbb{Z}$, the set of integers, is countable: order it $(0,1,-1,2,-2,\dotsc)$.

The set $\mathbb{Q}$ of rational numbers is also countable, surprisingly. First observe that $\mathbb{Z}\times\mathbb{Z}$ is countable: start with (0,0), then take all the ordered pairs that use only 1’s and 0’s, then add -1 to the mix, then 2, and so on. Then we write every rational in lowest terms as (numerator, denominator), so that $\mathbb{Q}$ corresponds to a subset of $\mathbb{Z}\times\mathbb{Z}$.  The listing of $\mathbb{Z}\times\mathbb{Z}$ then “shrinks” to one of $\mathbb{Q}$.  An example for the positive rationals is given at right; the red terms are the ones that get deleted.

The same argument shows that any product of two countable sets is countable.  Any easy extension of this shows that any finite product of countable sets is countable.  With a similar argument, show that a countable union of countable sets is countable.

So what isn’t countable?  The answer might be surprising to you, and many have chosen not to believe it, but with some care, it can be proved that $\mathbb{R}$ is not countable.  This is surprising because we can approximate any real number to arbitrary precision with a rational (for example, the first $n$ digits of its decimal representation) — in math terms, $\mathbb{Q}$ is dense in $\mathbb{R}$.  Here is how to prove it, and I will try to do this carefully to avoid common pitfalls.

The proof is by contradiction.  This means that we assume we already have a countable listing of $\mathbb{R}$ and derive a contradiction — in this case, that there were elements left out.  A true statement cannot imply a false one, so the assumption must have been false all along.  We begin with an intermediate step, called a lemma by mathematicians.

Lemma.  There is a bijection between $\mathbb{R}$ and the interval $(0,1)$ (the set of reals between 0 and 1).

Proof.  The proof is by picture, pretty much.  Put a unit circle tangent to the number line at 0.5.  The line from its center to any point of the line intersects the circle exactly once, so the function mapping points on the line to corresponding points on the circle (red lines) is an injection, and its range is the lower semicircle (not including the equator).  We then draw vertical (blue) lines down to the number line, giving a bijection between the lower semicircle and the interval $(0,1)$.  The composition of the two functions is a bijection from $\mathbb{R}$ to $(0,1)$.

So assume we have a bijection $\mathbb{N}\rightarrow (0,1)$, and use it to list the elements of $(0,1)$ in some order:

a1=0.14159...
a2=0.24623...
a3=0.95898...
a4=0.78128...
a5=0.33333...
.
.
.

(Note that decimals are ambiguous: $0.4999...=0.5000...$. To avoid ambiguity, we’ll always choose the representation with nines instead of zeros.) Now what we do is the following. Form a new number out of the first digit of the first number, the second digit of the second one, and so on. In the list above, this will be $0.14823...$. Now pick a number that differs from this one in every digit and has no zeros: say, by adding one to every digit but changing nines to eights. This new number can’t be a1, because it has a different first digit. It can’t be a2, because it has a different second digit. And so on. Oh, and since it doesn’t have zeros, it can’t be an alternate representation of a number ending in repeating nines. It follows that it isn’t on the list. But this is a contradiction, because we assumed the list was complete. (Adding to the list doesn’t help — it just gives a new number). In particular, there is no bijection between $[0,1]$ (or $\mathbb{R}$) and $\mathbb{N}$ — so there must be multiple sizes of infinity!

This argument, called diagonalization, was first proposed by Georg Cantor in the 19th century, and it was not met favorably by the mathematical community (his highly constructivist thesis advisor, Leopold Kronecker, was so against it that it essentially drove Cantor insane).

These days, Cantor’s ideas are essential to even very concrete fields like analysis, and diagonalization is a fairly common proof technique, especially in logic and computability theory. It’s important to us because it can be generalized significantly. For example, what if we drop the equality $0.\dotsm x999\dotsm=0.\dotsm (x+1)000\dotsm$, and consider the real numbers we used above to be just sequences of digits in $\{0,\dotsc,9\}$? Then the same argument shows that the set of these sequences is also uncountable. But a sequence is just a function whose domain is $\mathbb{N}$. In my post about relations, I gave a common notation for the set of such functions: $10^{\mathbb{N}}$. So $10^{\mathbb{N}}$ is uncountable. In fact (try this yourself), we can replace the 10 by any finite number other than 0 or 1 and get an uncountable set2. When we use 2, we have another interpretation: $2^A$ bijects naturally to $\mathcal{P}(A)$ by sending each function $f\in 2^A$ to $f^{-1}(\{1\})$, the set of elements of $A$ that get sent to 1 rather than 0. As a result, it’s common to use $2^A$ as an alternate notation for $\mathcal{P}(A)$. We now arrive at our main theorem:

Theorem (Cantor). For any set $A$, $\left|\mathcal{P}(A)\right|>|A|$.

Proof. Again, we employ a contradiction. This proof is just a generalization of the diagonalization proof given above; it’s also related to the Russell paradox! Suppose that we have a bijection $f:A\rightarrow\mathcal{P}(A)$. This sends elements of $A$ to subsets of $A$. Let $C$ be the set $\{x\in A:x\not\in f(x)\}$; that is, the set of elements that aren’t in the subset they get sent to. If $C$ is, say, $f(c)$ for $c\in A$, then either $c\in C$ or not; but by construction of $C$, both are contradictions. So $C$ is not in the image of $f$, contradicting its bijectivity.

Cantor’s Theorem has far-reaching implications. Immediately we can define an infinity of infinite cardinalities: $\beth_0=\aleph_0,\beth_i=2^{\beth_{i-1}}$ for all finite $i$ (this is the Hebrew letter “beth”, second in the alphabet)3. So $\beth_1=2^{\aleph_0}$ is the cardinality of the reals — it’s also called c, for “continuum”. These are the “beth numbers”; the chain of aleph numbers, meanwhile, are just defined by $\aleph_i$ being the smallest cardinality above $\aleph_{i-1}$.

Clearly, the beth numbers are a subset of the aleph numbers; the generalized continuum hypothesis says that every aleph number is a beth number. (And it has an important special case, the continuum hypothesis, which says that there is no cardinality between $\mathbb{R}$ and $\mathbb{N}$.) In the 1960’s, Paul Cohen proved that the continuum hypothesis (generalized and regular) was independent of the ZFC axioms — that is, you can’t prove it, but you can assume either “the continuum hypothesis is true” or “the continuum hypothesis is false” as a new axiom, and not arrive at a contradiction! Fortunately, most mathematicians don’t work with weird cardinalities, so I don’t think there’s a general mindset on which assumption is preferable.

Next time, more topology will probably be in the mix. Or the axiom of choice. We shall see!

1Some people don’t include finite sets in the definition of countable, saying “countable” to mean our “countably infinite” and “at most countable” to mean our “countable.” I like our definition better because of the duality: $\mathbb{N}$ (or sets of its cardinality) is the largest countable set and the smallest infinite one.

2In the post I linked to, I asked you to think about why this notation is used. If you still haven’t got it, here’s what you should prove: for finite sets $X$ and $Y$, the cardinality of $Y^X$ is just $|Y|^{|X|}$. In fact, we can construct a “cardinal arithmetic” for all cardinals, by defining the sum of cardinals $a+b$ to be $|A\cup B|$ with $A,B$ disjoint and $|A|=a,|B|=b$; likewise, $ab=|A\times B|$, and $a^b=|A^B|$. These work as you’d expect in the finite case (proofs), but for infinite cardinalities, both the sum and the product evaluate to the larger of the two. The exponent is slightly more interesting, as we show.

3…and in case you were wondering, we don’t have to stop at finite $i$. The beth numbers and aleph numbers can actually be indexed by the ordinals, which we’ll discuss soon. This is a story I don’t know much about, though, so it’ll be told at a later date.

[…] and now that you know about countability, we can define some new topologies.  I like building up a useful array of examples for the future, […]

[…] an example.  In the post on countability, we used a stereographic projection to shrink the real line down to a semicircle, then we projected […]

[…] off” the sets again, but in the same order.  None of the bijections with in the post on countability did this, and it’s pretty clear why: any order isomorphism has to preserve the type of […]

Pingback by Ordinals | Gracious Living and the Two Meat Meal

[…] fortunately, this doesn’t happen.  The reason why goes back all the way to our studies of cardinality: , and thus the set of points fixed by any rotation in , is countable, and the sphere is not.  If […]

Pingback by Banach-Tarski part 2 « Gracious Living

[…] by replacing variables like with ), there are only a countable number of such expressions , but an uncountable number of subsets of .  So not every set is definable, and this first-order axiom schema is weaker than […]

Pingback by A Couple Nuances « Gracious Living

[…] topology is at distinguishing disjoint sets), or the countability axioms (which measure, well, how countable the topology is).  In a sense, each one depends on the other two for examples and theorems, and in […]