## Real Analysis Review Day 5: Cardinality (Part II)

Definition. A set $X$ is called countable (or denumerable) if $card(X)\le card(\mathbb N)$. In particular, all finite sets are countable. If $X$ is countable but not finite, then $X$ is countably infinite.

Proposition. a. If $X$ and $Y$ are countable, so is $X\times Y$.

b. If $A$ is countable and $X_\alpha$ is countable for every $\alpha\in A$, then $\cup_{\alpha\in A}X_\alpha$ is countable.

c. If $X$ is countably infinite, then $card(X)=card(\mathbb N)$.

Proof. a. If suffices to prove that $\mathbb N^2$ is countable. Define a bijection from $\mathbb N$ to $\mathbb N^2$ by listing, for $n$ successively equal to 2, 3, 4, …, those elements $(j, k)\in\mathbb N^2$ such that $j+k=n$ in order of increasing $j$, thus:

(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1), …

b. For each $\alpha\in A$ $\exists$ a surjective $f_\alpha: \mathbb N\to X_\alpha$, and then the map $f: \mathbb N\times A\to\cup_{\alpha\in A}X_\alpha$ defined by $f(n, \alpha)=f_\alpha(n)$ is surjective.

c. $X$ is an infinite subset of $\mathbb N$. Lef $f(1)$ be the smallest element of $X$, and define $f(n)$ inductively to be the smallest element of $X\setminus\{f(1), ..., f(n-1)\}$. Then $f$ is a bijection from $\mathbb N$ to $X$. $\Box$

Corollary. $\mathbb Z$ and $\mathbb Q$ are countable.

Proof. $\mathbb Z$ is the union of the countable sets $\mathbb N$, $\{-n: n\in\mathbb N\}$, and $\{0\}$, and one can define a surjection $f: \mathbb Z^2\to\mathbb Q$ by $f(m, n)=m/n$ if $n\not=0$ and $f(m, 0)=0$. $\Box$

Definition. A set $X$ is said to have the cardinality of the continuum if $card(X)=card(\mathbb R)$. We use letter $latex\mathfrak c$ as an abbreviation for $card(\mathbb R)$:

$card(X)=\mathfrak c$ iff $card(X)=card(\mathbb R)$

Proposition. $card(\mathcal P(\mathbb N))=\mathfrak c$.

Proof. If $A\subset \mathbb N$, define $f(A)\in\mathbb R$ to be $\sum_{n\in A}2^{-n}$ if $\mathbb N\setminus A$ is infinite and $1+\sum_{n\in A}2^{-n}$ if $\mathbb N\setminus A$ is finite. Then $f: \mathcal P(\mathbb N)\to\mathbb R$ is injective. On the other hand, define $g: \mathcal P(\mathbb Z)\to\mathbb R$ by $g(A)=log(\sum_{n\in A}2^{-n})$ if $A$ is bounded below and $g(A)=0$ otherwise. Then $g$ is surjective since every positive real number has a base-2 decimal expansion. Since $card(P(\mathbb Z))=card(\mathcal P(\mathbb N))$, the result follows from the Schroder-Bernstein Theorem. $\Box$

Corollary. If $card(X)\ge\mathfrak c$, then $X$ is uncountable.

Proposition. a. If $card(X)\le\mathfrak c$ and $card(Y)\le\mathfrak c$, then $card(X\times Y)\le\mathfrak c$.

b. If $card(A)\le\mathfrak c$ and $card(X_\alpha)\le\mathfrak c$ for all $\alpha\in A$, then $card(\cup_{\alpha\in A}X_\alpha)\le\mathfrak c$.

Proof. It suffices to take $X=latex Y=\mathcal P(\mathbb N)$. Define $\phi, \psi: \mathbb N\to\mathbb N$ by $\phi(n)=2n$ and $\psi(n)=2n-1$. Then $f: \mathcal P(\mathbb N)^2\to\mathcal P(\mathbb N)$ defined by $f(A, B)=\psi(A)\cup\phi(B)$ is bijective.  $\Box$

” Gratitude makes sense of our past, brings peace for today, and creates a vision for tomorrow.” ~ Melody Beattie

To be continued tomorrow 🙂

References

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 8-9.

[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.

## 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.