# Gracious Living

Cardinality
November 1, 2010, 04:45
Filed under: Math, Set Theory | Tags: , ,

(This was originally a longer post that went through to countability and the continuum hypothesis. I’ve broken it in half, ending at the definition of infinite sets, in the interest of keeping things short, and also possibly of MaBloWriMo. The next half will be up soon!)

What we’re going to do today is measure sets.  I said that sets have no structure back in the first couple of posts, but this isn’t entirely true.  Finite sets, for example, have a definite number of elements.  Today, I show that you can extend this idea of number to infinite sets by considering a special class of function between sets that preserves number.  The strange properties of this will end up making topology and set theory a lot more interesting.

Let’s examine the sets $\{a,b,c\}$ and $\{1,2,3\}$.  What do they have in common?  The obvious answer is that they both have three elements, but I contend that this isn’t the deepest you can go.  For instance, what does “three” mean — and can’t you recognize the similarity without counting?  Instead, what we can do is “pair off” their elements:

1 2 3
| | |
a b c

If we tried to do this between two sets with different numbers of elements, we would have to pair several elements to a single element at some point. So really, what we’ve done is define “three”. The sets of three things are exactly those sets that can be paired off with the set $\{1,2,3\}$.

Now, a pairing off between a set $A$ and a set $B$ is really just a function from $A$ to $B$.  If you recall the post about relations, you’ll realize that it is actually a one-to-one and onto function, or bijection.  As I mentioned back there, bijections are pretty much the nicest functions you could ask for because they’re guaranteed inverses.  This means that a pairing off between $A$ and $B$ gives you a pairing off between $B$ and $A$ such that if you apply one and then the other, you always get back to where you started.

So it appears that bijection is the isomorphism we want!  Now, a bijection is a kind of function, which is a kind of relation.  If you think about it, you’ll realize that a bijection is also an equivalence relation!  (This is true of any isomorphism, but we can’t prove this because we haven’t actually defined isomorphism.)  So we can form its equivalence classes, which we’ll call cardinalities.  Thus the cardinality of $\{a,b,c\}$ is the equivalence class $[\{1,2,3\}]$, which we’ll call “three.”  We write the cardinality of $A$ as $|A|$ (other authors use $\#(A)$ or $n(A)$).  Note that cardinalities have an order on them: $n(A)\le n(B)$ if $A$ has a bijection onto a subset of $B$ (it’s a total order, but why isn’t obvious for now).  Now, if possible, it would be nice to have a single representative of each cardinality that we can construct and always rely on (the math word for this is “canonical”), so we no longer think of equivalence classes but instead of actual “numbers.”  I’ll give a construction for finite cardinalities now, and we’ll see the infinite ones when we study the more general ordinal numbers.

The axiom of infinity gives us a set that contains $\emptyset$ and $x\cup\{x\}$ for each $x$ in the set.  Specification lets us find the smallest such set, which we call $\mathbb{N}$.  If you don’t see where I’m going with this, look at the elements of that set.  They are

$\emptyset,\quad\{\emptyset\},\quad\{\emptyset,\{\emptyset\}\},\quad\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\},\quad\dotsc$

I will call them, respectively,

$\mathbf{0,1,2,3}\dotsc$

So $\mathbf{1=\{0\},2=\{0,1\}}$, and in general, $\mathbf{n=\{0,1,\dotsc,n-1\}}$.  In particular, each “number” is both an element and a subset of all larger “numbers,” and the cardinality of the set $\mathbf{n}$ is the number $n$.  There is a total order on this set: $\mathbf{n}<\mathbf{n}$ if $\mathbf{n}\subset\mathbf{m}$ or, equivalently, $\mathbf{n}\in\mathbf{m}$.  We can and probably will define addition and multiplication of these guys, at which point we’ll have ourselves a pretty good model of the natural numbers.  Their most important property, though, is induction.  This is a theorem of set theory that I’ll prove later, and that’s usually taken as an axiom of arithmetic.  We define the successor function $S(\mathbf{n})=\mathbf{n\cup\{n\}}=\mathbf{n+1}$.  Induction says that if a property holds for $\mathbf{0}$ and if it holds for $S(\mathbf{n})$ whenever it holds for $\mathbf{n}$, then it holds for $\mathbb{N}$.

Call a set finite if it has a bijection to an element of $\mathbb{N}$.  By induction, all elements of $\mathbb{N}$ have different cardinalities, and the order of the cardinalities matches the ordering on $\mathbb{N}$.  So our intuition is correct: finite sets really do have numbers for their cardinalities. We’re going to consider elements of $\mathbb{N}$ to be the standard representatives for their cardinalities, which we’ll call cardinality numbers.

Now take a set $A$.  Using the axiom of choice (which, remember, lets us choose elements from subsets of $A$), we can pick an element $a_0$, then a different one $a_1$, and so on; the set $a_0,\dotsc,a_n$ defines a function from $\mathbf{n}\rightarrow A$, and if $A$ is ever exhausted, this is a bijection, so $A$ is finite. This also means that if $A$ is not finite, then it contains a copy of (read: an injection from) $\mathbb{N}$. So $\mathbb{N}$ is really the smallest infinite set. One weird property of $\mathbb{N}$ is that it admits a bijection to a proper subset of itself: just send $\mathbf{n}\mapsto\mathbf{n+1}$, and the range does not contain $\mathbf{0}$1. By choosing a copy of $\mathbb{N}$ in every infinite set, we can do the same to any infinite set. The converse also applies: if we have a bijection $f$ from $A$ to a proper subset of $A$, then for any $x\in A$, the elements $x,f(x),f(f(x)),\dotsc$ must all be different, so they give you a copy of $\mathbb{N}$.

So an infinite set is one that can be mapped either surjectively onto $\mathbb{N}$, or bijectively onto a proper subset of itself. What do you think about this definition? To add to the intrigue, the cardinality of $\mathbb{N}$ is not the only infinite one — it’s just the lowest one in an infinite chain. We’ll explore these larger cardinalities tomorrow.

1This is often known as the “parable of Hilbert’s Hotel,” based on the story of an infinitely large hotel that could admit guests even when it was completely full. In fact, we can instead use the map $\mathbf{n}\mapsto\mathbf{2n}$ and create an infinite number of vacancies! A very well-written story based on this was one of the things that attracted me to math as a kid. Also, it looks like this idea is being used to prove the existence of God. I think Craig’s argument is fallacious — what do you think?

3 Comments so far