## Real Analysis Review Day 4: Cardinality (Part I)

If $X$ and $Y$ are nonempty sets, then

$card(X)\le card(Y)$, $card(X)=card(Y)$, $card(X)\ge card(Y)$

mean $\exists f: X\to Y$ which is injective, bijective, or surjective, respectively. We also define

$card(X), $card(Y)

to mean that $\exists$ an injection but no bijection, or a surjection but no bijection, from $X$ to $Y$. These relationships can be extended to the empty set by declaring that

$card(\emptyset) and $card(X)>card(\emptyset)$ for all $X\not=\emptyset$.

Proposition. $card(X)\le card(Y)$ iff $card(Y)\le card(X)$.

Proof. $\Rightarrow$: If $f: X\to Y$ is injective, pick an arbitrary $x_0\in X$ and define $g: Y\to X$ by $g(y)=f^{-1}(y)$ if $y\in f(X)$, $g(y)=x_0$ otherwise. Then $g$ is surjective.

$\Leftarrow$: If $g: Y\to X$ is surjective, the sets $g^{-1}(\{x\})(x\in X)$ are nonempty and disjoint, so any $f\in\prod_{x\in X} g^{-1}(\{x\})$ is an injection from $X$ to $Y$. $\Box$

Proposition. For any sets $X$ and $Y$, either $card(X)\le card(Y)$ or $card(Y)\le card(X)$.

Proof. Consider the set $\mathcal J$ of all injections from subsets of $X$ to $Y$. The members of $J$ can be regarded as subsets of $X\times Y$, so $\mathcal J$ is partially ordered by inclusion. Applying Zorn’s Lemma, then $\mathcal J$ has a maximal element $f$, with domain $A$ and range $B$. If $x_0\in X\setminus A$ and $y_0\in Y\setminus B$, then $f$ can be extended to an injection from $A\cup\{x_0\}$ to $B\cup\{y_0\}$ by setting $f(x_0)=y_0$, contradicting maximality. Hence either $A=X$, in which case $card(X)\le card(Y)$, or $B=Y$, in which case $f^{-1}$ is an injection from $Y$ to $X$ and $card(Y)\le card(X)$. $\Box$

Proposition. The Schroder-Bernstein Theorem. If $card(X)\le card(Y)$ and $card(Y)\le card(X)$, then $card(X)=card(Y)$.

Proof. Let $f: X\to Y$ and $g: Y\to X$ be injections. Consider a point $x\in X:$ If $x\in g(Y)$, we form $g^{-1}(x)\in Y$;  if $g^{-1}(x)\in f(X)$, we form $f^{-1}(g^{-1}(x))$; and so forth. Either this process can be continued indefinitely, or it terminates with an element of $X\setminus g(Y)$ (perhaps $x$ itself), or it terminates with an element of $Y\setminus f(X)$. In these three cases we say that $x$ is in $X_\infty$, $X_X$, or $X_Y$; thus $X$ is the disjoint union of $X_\infty$, $X_X$, and $X_Y$. In the same way, $Y$ is the disjoint union of three sets $Y_\infty$, $Y_X$, and $Y_Y$. Clearly $f$ maps $X_\infty$ onto $Y_\infty$ and $X_X$, whereas $g$ maps $Y_Y$ onto $X_Y$. Therefore, if we define $h: X\to Y$ by $h(x)=f(x)$ if $x\in X_\infty\cup X_X$ and $h(x)=g^{-1}(x)$ if $x\in X_Y$, then $h$ is bijective. $\Box$

Proposition. For any set $X$, $card(X).

Proof. On the one hand, the map $f(x)=\{x\}$ is an injection from $X$ to $\mathcal P(X)$. On the other, if $g: X\to\mathcal P(X)$, let $Y=\{x\in X: x\notin g(x)\}$. Then $Y\notin g(X)$, for if $Y=g(x_0)$ for some $x_0\in X$, any attempt to answer the question “Is $x_0\in Y$?” quickly leads to contradiction. Therefore $g$ cannot be surjective. $\Box$

“Friendship with one’s self is all important, because without it one cannot be friends with anyone else in the world.” ~ Eleanor Roosevelt

To be continued tomorrow 🙂

References

1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 6-7.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.