(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 and . 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 .*

Now, a pairing off between a set and a set is really just a function from to . 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 and gives you a pairing off between and 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 is the equivalence class , which we’ll call “three.” We write the cardinality of as (other authors use or ). Note that cardinalities have an order on them: if has a bijection onto a subset of (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 and for each in the set. Specification lets us find the smallest such set, which we call . If you don’t see where I’m going with this, look at the elements of that set. They are

I will call them, respectively,

So , and in general, . In particular, each “number” is both an element and a subset of all larger “numbers,” and the cardinality of the set is the number . There is a total order on this set: if or, equivalently, . 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** . Induction says that *if a property holds for and if it holds for whenever it holds for , then it holds for .*

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

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

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

^{1}This 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 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**

Leave a comment

[…] Gracious Living and the Two Meat Meal Just another WordPress.com site Skip to content HomeAboutTo Do ← Cardinality […]

Pingback by Countability | Gracious Living and the Two Meat MealNovember 2, 2010 @ 01:28[…] we talked about cardinality, we defined “standardized” finite cardinal numbers as the set , which we modeled as […]

Pingback by Ordinals | Gracious Living and the Two Meat MealNovember 6, 2010 @ 08:17[…] get tricky! Unlike ordinal arithmetic, the arithmetic of cardinals isn’t really an extension of Peano arithmetic. Rather, it’s a consequence of the set […]

Pingback by Cardinal Arithmetic « Gracious LivingDecember 8, 2010 @ 03:23