Abstract Nonsense

Crushing one theorem at a time

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 \mathbb{R} over \mathbb{Q}.

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 U a well-ordering on U is a total order \preceq such that for any \varnothing\subsetneq J\subseteq U we have that J has a least element, namely an element \lambda\in J ( lambda for least) such that \lambda\preceq \kappa for all \kappa\in J. Clearly this least element is unique for if \gamma were another least element of J we must have that \lambda\preceq\gamma and \gamma\preceq\lambda and so by the anti-symmetry of \preceq we may conclude that \gamma=\lambda.

Thus, for any \alpha\in U we may consider the set (\alpha,\infty)\overset{\text{def.}}{=}\left\{\beta\in U:\alpha\prec\beta\right\} (where \prec means \preceq\text{ and }\ne) , and if it were non-empty then there would be a least element  called the immediate successor of \alpha, and it is denoted \alpha+1. Similarly, assuming that they exist we may define \alpha+m for m\in\mathbb{N} inductively by

\alpha+0=0\text{ and }\alpha+m=(\alpha+(m-1))+1

Next, we define the idea of a greatest element. For a totally ordered set (not necessarily well-ordered) \left(U,\preceq\right) an element \omega\in U (not the least ordinal, just a member of U) is a (soon to be the)  greatest element of U if \alpha\preceq \omega for all \alpha\in U. Phrase differently, \omega is a greatest element of U if (\omega,\infty)=\varnothing. Clearly, if such an element exists it must be unique since if \gamma were another such greatest element then \gamma\preceq\omega and \omega\preceq\gamma so that \gamma=\omega.

With these definition a few things follow immediately

Lemma(i): Let \left(U,\preceq\right) be a partially ordered set, then assuming they exist, \alpha=\beta\Leftrightarrow \alpha+1=\beta+1

Proof: Suppose that \alpha\ne\beta, then by the totality of the ordering we may assume without loss of generality that \alpha\prec\beta. Thus, \beta\in(\alpha,\infty) and so by definition \alpha+1\preceq\beta. But, since \beta\prec\beta+1 we may conclude that \alpha+1\prec\beta+1. It follows that \alpha\ne\beta\implies \alpha+1\ne\beta+1 and so taking the contrapositive \alpha+1=\beta+1\implies \alpha=\beta.

Conversely, if \alpha=\beta then (\alpha,\infty)=(\beta,\infty) and so clearly \alpha+1=\beta+1. \blacksquare

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

Lemma (ii): Let \left(U,\preceq\right) be an infinite, well-ordered set. Then, there exists a finite (possibly empty) set V\subseteq U such that every element of U-V has at least n-1,\text{ }n\geqslant2 immediate successors.

Proof: Suppose first that U has no greatest element. Then, for any \alpha\in U we have that (\alpha,\infty),\cdots,(\alpha+(n-2),\infty) are all non-empty (otherwise one of them would be a greatest element) and so \alpha+1,\cdots,\alpha+(n-1) exists.

Suppose then U has a greatest element \omega_1. Consider then U-\{\omega_1\}. Then, for each \alpha\in U-\{\omega_1\} we have that (\alpha,\infty)\ne\varnothing and so \alpha+1 exists. If for every (\alpha+1,\infty) is non-empty for all \alpha\in U then we’re done since if \beta\in U were such that (\beta+k,\infty)=\varnothing for some k\in\{1,\cdots,n-2\} (clearly k\ne0 since otherwise \beta=\omega_1 which is impossible) then we see that ((\beta+(k-1))+1,\infty)=\varnothing contrary to assumption. So assume not, then there exists some \omega_2\in U such that (\omega_2+1,\infty)=\varnothing, namely one such that \omega_2+1=\omega_1. Clearly such an element is unique since if \alpha\ne\omega_2 then by lemma(i) we see that \alpha+1\ne\omega_2+1=\omega_1 and so \alpha+1 is not a greatest element and so (\alpha+1,\infty)\ne\varnothing. Consider then U-\{\omega_1,\omega_2\}, then using an analgous argument as before we see that  for every \alpha\in U we have that \alpha+1,\alpha+2 exists. If there exists no \alpha\in U such that (\alpha+2,\infty) is non-empty we can apply the same argument as before to show we’re done. So, if not there exists some \omega_3\in U such that (\omega+2,\infty)=\varnothing and (just as before) it must be unique. Thus, every element of \alpha\in U-\{\omega_1,\omega_2,\omega_3\} has the property that \alpha+1,\alpha+2,\alpha+3 exists. As was said before, if the process terminates (in the sense that (\alpha+k,\infty)\ne\varnothing for all \alpha\in U) we’re done as was noted before. Otherwise, we may continue this process to arrive at the set U-\{\omega_1,\cdots,\omega_{n-1}\} which by construction has the property that every element has at least n-1 immediate successors.

In any case, we see that there exists a finite set V such that every element of U-V has n-1 successors. \blacksquare

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

Remark: A note on notation: I will use \text{card }A and |A| interchangeably to mean “the cardinality of the set A” throughout this discussion. Also, A\simeq B\text{ }\Leftrightarrow\text{ }|A|=|B|

Theorem: Let U be a set. Define

\mathscr{P}_0\left(U\right)=\left\{S\subseteq U:|S|<\infty\right\}

Then, |U|\leqslant\left|\mathscr{P}_0\left(U\right)\right| with equality precisely when U is infinite.

Proof: Note that if U is finite that \mathscr{P}_0\left(U\right)=\mathscr{P}\left(U\right) then |U|<\left|\mathscr{P}_0\left(U\right)\right| by Cantor’s Theorem (more simple-mindedly one sees that if |U|=n that \left|\mathscr{P}\left(U\right)\right|=2^n).

Suppose then that U is infinite. We begin by showing that |U|=\left|\mathscr{P}_0\left(U\right)\right| by showing that if  \mathcal{S}_n,\text{ }n\geqslant 1 is defined by

\mathcal{S}_n=\left\{S\subseteq U:|S|=n\right\}

that \mathcal{S}_n\simeq U. If n=1 this is trivial since the map

h:U\to\mathcal{S}_n:x\mapsto\{x\}

is evidently a bijection. So, we need only consider the case when n\geqslant 2.

We shall do this by showing that |\mathcal{S}_n|\leqslant |U| and |U|\leqslant |\mathcal{S}_n| and appeal to the Schroeder-Bernstein Theorem.

To show that |\mathcal{S}_n|\leqslant |U| first consider the set  C_n=\left\{(a_1,\cdots,a_n):a_i\ne a_j\text{ }i\ne j\right\} and the map

f:C_n\to\mathcal{S}_n:(a_1,\cdots,a_n)\mapsto\{a_1,\cdots,a_n\}

It’s not immediate that this map is well-defined (in a certain sense), namely is this really a mapping “into” \mathcal{S}_n. To see that f(x)\in\mathcal{S}_n for all x\in\ C_n we merely note that since a_1,\cdots,a_n are all distinct that \{a_1,\cdots,a_n\} really has cardinality n and so is, in fact, an element of \mathcal{S}_n. Thus, since clearly f is a bijection we may conclude that |C_n|=|\mathcal{S}_n| and since C_n\subseteq U^n we may finally conclude that

|\mathcal{S}_n|=|C_n|\leqslant \left|U^n\right|=|U|

 

To show that |U|\leqslant\left|\mathcal{S}_n\right| we start by well-ordering U, call the ordering \preceq. By lemma(ii) we know there exists a finite set V\subseteq U such that every element of U-V has at least n-1 successors. So, consider

g:U-V\to\mathcal{S}_n:x\mapsto\{x,x+1,\cdots,x+(n-1)\}

To see that this map is injective suppose that

\{x,x+1,\cdots,x+(n-1)\}=\{y,y+1,\cdots,y+(n-1)\}

Then, x\in\{y,y+1,\cdots,y+(n-1)\} and so x=y+k for some k\in\{0,\cdots,n-1\}. It follows that x+1=y+(k+1),\cdots,x+(n-1)=y+(k+(n-1)) and thus

\begin{aligned}\{x,x+1,\cdots,x+(n-1)\} &=\{y,y+1,\cdots,y+(n-1)\}\\ &=\{y+k,y+(k+1),\cdots,y+(k+n-1)\}\end{aligned}

 

Thus, y\in\{y+k,y+(k+1),\cdots,y+(k+n-1)\} thus y=y+(k+\ell) for some \ell\in\{0,\cdots,n-1\}. Clearly though it follows that \ell=0 otherwise y\prec y+\ell \preceq y+(k+\ell) and so y=y+k=x. So, injectivity follows.

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

|U|=\left|U-V\right|\leqslant\left|\mathcal{S}_n\right|

Thus,  |U|=\left|\mathcal{S}_n\right| for all n\in\mathbb{N}. So, finally we may conclude that

\displaystyle \left|\mathscr{P}_0\left(U\right)\right|=\text{card }\bigcup_{n\in\mathbb{N}}\mathcal{S}_n=\aleph_0\cdot|U|=|U|.

References:

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

Advertisements

October 20, 2010 - Posted by | Set Theory | , , ,

3 Comments »

  1. […] 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 | Reply

  2. […] 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 | Reply

  3. […] 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: