## Set Theory Lemma

**Point of post:** In this post I will prove a lemma about set theory which is used many times, in many different subjects. In effect, it says that the set of all finite subsets of an infinite set is equipotent to the set itself. We will use this in the next post to answer an interesting question regarding the dimensionality of over .

*Remark:* I am aware that there are many alternative, and possibly more satisfying, proofs for this theorem. In fact, even my proof could be shortened considerably by the introduction of ordinals, but considering my (assumed) readership I think it prudent to go the mathematical low road and keep it understandable to the relative laymen (myself probably being among those counted).

**Prerequisites:** Before we do this proof we state some quick definitions and theorems from set theory.

For a set a *well-ordering *on is a total order such that for any we have that has a *least element*, namely an element ( lambda for least) such that for all . Clearly this least element is unique for if were another least element of we must have that and and so by the anti-symmetry of we may conclude that .

Thus, for any we may consider the set (where means ) , and if it were non-empty then there would be a least element called the *immediate successor *of , and it is denoted . Similarly, assuming that they exist we may define for inductively by

Next, we define the idea of a greatest element. For a totally ordered set (not necessarily well-ordered) an element (not the least ordinal, just a member of ) is a (soon to be the) *greatest element *of if for all . Phrase differently, is a greatest element of if . Clearly, if such an element exists it must be unique since if were another such greatest element then and so that .

With these definition a few things follow immediately

**Lemma(i):** Let be a partially ordered set, then assuming they exist,

**Proof**: Suppose that , then by the totality of the ordering we may assume without loss of generality that . Thus, and so by definition . But, since we may conclude that . It follows that and so taking the contrapositive .

Conversely, if then and so clearly .

So, now we move to the crux of the issue, namely the following:

**Lemma (ii):** Let be an infinite, well-ordered set. Then, there exists a finite (possibly empty) set such that every element of has at least immediate successors.

**Proof:** Suppose first that has no greatest element. Then, for any we have that are all non-empty (otherwise one of them would be a greatest element) and so exists.

Suppose then has a greatest element . Consider then . Then, for each we have that and so exists. If for every is non-empty for all then we’re done since if were such that for some (clearly since otherwise which is impossible) then we see that contrary to assumption. So assume not, then there exists some such that , namely one such that . Clearly such an element is unique since if then by **lemma(i)** we see that and so is not a greatest element and so . Consider then , then using an analgous argument as before we see that for every we have that exists. If there exists no such that is non-empty we can apply the same argument as before to show we’re done. So, if not there exists some such that and (just as before) it must be unique. Thus, every element of has the property that exists. As was said before, if the process terminates (in the sense that for all ) we’re done as was noted before. Otherwise, we may continue this process to arrive at the set which by construction has the property that every element has at least immediate successors.

In any case, we see that there exists a finite set such that every element of has successors.

With this lemma we are prepared to prove the seminal theorem.

*Remark:* A note on notation: I will use and interchangeably to mean “the cardinality of the set ” throughout this discussion. Also,

**Theorem:** Let be a set. Define

Then, with equality precisely when is infinite.

**Proof:** Note that if is finite that then by Cantor’s Theorem (more simple-mindedly one sees that if that ).

Suppose then that is infinite. We begin by showing that by showing that if is defined by

that . If this is trivial since the map

is evidently a bijection. So, we need only consider the case when .

We shall do this by showing that and and appeal to the Schroeder-Bernstein Theorem.

To show that first consider the set and the map

It’s not immediate that this map is well-defined (in a certain sense), namely is this really a mapping “into” . To see that for all we merely note that since are all distinct that really has cardinality and so is, in fact, an element of . Thus, since clearly is a bijection we may conclude that and since we may finally conclude that

To show that we start by well-ordering , call the ordering . By **lemma(ii)** we know there exists a finite set such that every element of has at least successors. So, consider

To see that this map is injective suppose that

Then, and so for some . It follows that and thus

Thus, thus for some . Clearly though it follows that otherwise and so . So, injectivity follows.

With this (and remembering that is an infinite set) we see that

Thus, for all . So, finally we may conclude that

.

**References:**

1. Jech, Thomas J. *Set Theory*. Berlin: Springer, 2003. Print.

[…] though, that by inspecting this post we can see that we may rephrase this […]

Pingback by The Dimension of R over Q « Abstract Nonsense | October 22, 2010 |

[…] follows. To see the central inequality we let we note then, using basic cardinal arithmetic and a common set theoretic fact, […]

Pingback by Dual Modules « Abstract Nonsense | November 12, 2011 |

[…] us a set which is equipotent to (since is infinite) and injects . But, since is infinite it is basic set theory that and so by the above analysis we may conclude that . But, by symmetry we may also conclude […]

Pingback by Rank and the IBN Property « Abstract Nonsense | November 17, 2011 |