Real Analysis Review Day 4: Cardinality (Part I)

Filed under: Interdisciplinary, Mathematics — Leave a comment

May 10, 2015

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)$ , $card(Y)<card(X)$

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)<card(X)$ 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)<card(\mathcal P(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.

Tags: cardinality, real analysis

Comments RSS feed

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Yuqing Hu's Blog 胡雨青博客

Follow Blog via Email