#equinumerous

Anyway, following that long preamble, here is my relatively unimpressive first post on cardinals. We've already kind of encountered the concept in my post about countability under real analysis (toc). I guess what set theory is kind of doing for us now is fleshing out the whole concept.

Let's start with an easy definition. Two sets, A and B, are equinumerous (notationally, A ≈ B) if there is a one-to-one onto function f: A → B, i.e. there is a bijection between the two. The book calls such a function a one-to-one correspondence...but I prefer bijection since it's easier.

There are a few different formulations of equinumerosity. If we want to show that A and B are equinumerous, then obviously we could try to construct a bijection between the two. Alternatively, you could show that there is a map from A onto B and a map from B onto A. Similarly, you could show there is a one-to-one map from A into B and a one-to-one map from B into A. Yet another way of showing A and B are equinumerous is to start with a one to one map from A into B, and then show that it must be onto. Likewise, you could start with a map from A onto B, and show it must be one-to-one.

One last note about equinumerosity before we move on: it has the flavour of an equivalence relation (only equivalence relations are defined on sets, and the collection of all sets is not a set). In other words,

A ≈ A;

A ≈ B → B ≈ A;

A ≈ B, B ≈ C → A ≈ C.

These properties are pretty easy to prove using the identity, inverse, and composition of appropriate bijections, respectively. Okay. Onto the real meat of the discussion.

Intuitively, we'd like to say that sets that are equinumerous have "the same number of elements", or that they are "the same size" in some way. Cardinal numbers help us formalise this idea. Basically, we pick out a few special sets (how we pick these sets comes later). We declare these sets "cardinal numbers", so each special set is a cardinal number. Then, if any set A is equinumerous to a specific cardinal number κ (since, remember, cardinal numbers were sets themselves), then the cardinality of A is κ; cardA = κ.

The basic hope is to define the cardinal numbers so that cardA = cardB iff A ≈ B. We can start by allowing all elements of ω (the natural numbers) to be cardinal numbers. Then, cardn = n ∀n ∈ ω. Defining the particular sets which will be infinite cardinal numbers is a bit trickier, so we save that for later. But we're off to a good start--we have all the finite cardinal numbers! In order to make sure that each finite set gets associated with one unique cardinal number, we need to pull in the our good dude, the pigeonhole principle.

I'm sure you've seen the pigeonhole principle before--I first wrote about it in my discrete math post set. We're going to rework it a little bit for this content, but the pigeonhole principle by any other name is still the pigeonhole principle. Here we go.

The Pigeonhole Principle asserts that no natural number n is equinumerous to a proper subset of itself (including, of course, any natural number less than n). For the proof, we use induction. Of course, everything in set theory must be reformulated for set theory, so let's reformulate induction first.

From before, we saw that any inductive set must contain the natural numbers; i.e. the natural numbers are the smallest inductive set. Then, if we prove a property for any inductive set, it most certainly holds for the natural numbers. Thus, say we want to use induction to prove some property xyz. We first show that xyz holds for 0, or the empty set. Then, we show that, given xyz holds for some a, it holds for the successor of a, a+. Now, we've shown that the "class" (might not even be a set) of all elements with the property xyz is inductive; so this class must contain the natural numbers, ω. Then, xyz holds for every element in ω. Alternatively, ω is the smallest inductive set, so if a subset of ω is inductive, it must be ω itself. We can then define some subset T ⊆ ω consisting of all natural numbers for which xyz holds. If we prove that it is inductive, we can conclude T must equal ω, so every element in ω has the property xyz.

Let's do a test drive on the pigeonhole principle. We'll define the set T = {n ∈ ω | n is not equinumerous to a proper subset of itself}. 0 ∈ T because there are no proper subsets of 0, and the property holds vacuously. Now, let's suppose n ∈ T. How do we show n+ ∈ T?

Let's start with some map f: n+ → n+ that is one-to-one. We show it's onto.

case 1: f is closed under n, i.e. f[n] ⊆ n. Then, considering the map f restricted to n, it is a one to one map from n into n. From the inductive assumption, it must be onto. Finally, f({n}) must go to {n}, because f is one-to-one. Then, the range of f is n ∪ {n} = n+.

case 2: f is NOT closed under n, i.e. {n} ∈ f[n]. f is one to one, so there is a particular k ∈ n with f(k) = {n}. Similarly, f is one to one, so f({n}) cannot be {n}, and thus f({n}) = m where m ∈ n. We can simply define a new function, g, with all the old values of f, except we interchange f(k) and f({n}) so that g(k) = m and f({n}) = {n}. Now, g has the same range as f, but g is closed under n. From case 1, g is onto n+. g has the same range as f, so f is also onto n+.

Now, we have n+ ∈ T, so T is inductive and we have T = ω. Thank god, I was starting to sweat a little.

We have that every natural number cannot be equinumerous to a proper subset of itself. And obviously a natural number can't be equinumerous to a natural number bigger than itself, because then the bigger natural number would be equinumerous to a proper subset of itself. Of course, every natural number is equinumerous to itself, with the identity function. So we conclude that cardn = n is well defined and unambiguous.

Now, we can define the concept of a finite set really easily, by just saying A is finite if cardA ∈ ω. It's pretty peanuts to have as a side effect of the pigeonhole principle that all finite sets cannot be equinumerous to proper subsets of itself. Let's take some finite set, A, and a proper subset B ⊂ A. There's an n ∈ ω with cardA = n, so n ≈ A. Let's just choose a bijection f: A → n. Then, f[B] ⊂ f[A] = n. If A ≈ B, then let the bijection be g: A → B. Then, using composition, we'd have a bijection n → A → B → f[B] where f[B] is a proper subset of n. Of course, we just showed that cannot be the case, so A cannot be equinumerous to B. Then, each finite set is equinumerous to a unique cardinal number, so the cardinal numbers are well defined (for finite ones, at least).

In fact, generally speaking, that's how you show something related to cardinality when it comes to finite sets. Show it for ω first (usually using induction); then kind of "copy-paste" the property back to the original sets.