Abstract Nonsense

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.

October 20, 2010 -