### Cardinality

Definition: If there exists a 1-1 mapping of ${A}$ onto ${B}$, we say that ${A}$ and ${B}$ can be put in 1-1 correspondence , or that ${A}$ and ${B}$ have the same cardinal number , or briefly, that ${A}$ and ${B}$ are equivalent, and we write ${A\sim B}$. This relation clearly has the following three properties:

1. It is reflexive: ${A\sim A}$.
2. It is symmetric: if ${A\sim B}$, then ${B\sim A}$.
3. It is transitive: if ${A\sim B}$ and ${B\sim C}$, then ${A\sim C}$.

Definition: For any positive integer ${n}$, let ${J_{n}}$ be the set whose elements are the integers, ${1,2,...,n}$; let ${J}$ be the set of all positive integers. For any set ${A}$, we say:

1. (a) ${A}$ is finite if ${A\sim J_{n}}$ for some positive integer ${n}$.
2. (b) ${A}$ is infinite if ${A}$ is not finite.
3. (c) ${A}$ is countable if ${A\sim J}$.
4. (d) ${A}$ is uncountable if ${A}$ is neither finite nor countable.
5. (d) ${A}$ is at most countable if ${A}$ is finite or countable.

Remark: A finite set cannot be equivalent to one of its proper subsets. However, this is possible for infinite sets. In fact, we could restate the definition (b): ${A}$ is infinite if ${A\sim B}$ for some ${B\subset A}$.

Theorem 1 Every infinite subset of a countable set ${A}$ is countable.

Proof: Suppose ${B\subseteq A}$ and ${B}$ is infinite. Arrange the elements of ${A}$ which are all distinct in a sequence ${(a_{i})_{i=1}^{\infty}}$. Then we construct a sequence ${(n_{k})_{k=1}^{\infty}}$ as follows:

Let ${n_{1}\in J}$ be the smallest number such that ${a_{n_{1}}\in B}$. Note ${n_{1}}$ exists because ${\mathbb{N}}$ is well-ordered. After choosing ${n_{1},...,n_{k-1}}$, we let ${n_{k}}$ be the smallest number greater than ${n_{k-1}}$ such that ${a_{n_{k}}\in B}$.

Then consider the function ${f: J\rightarrow B}$ where ${f(k)=a_{n_{k}}}$. We then check ${f}$ is indeed a bijection. It is one-to-one because ${(a_{i})_{i=1}^{\infty}}$ is a distinct sequence; then for any ${i\neq j}$, we have ${a_{n_{i}}\neq a_{n_{j}}}$. ${f}$ must be surjective for otherwise, there exists ${b\in B}$ is not in the image of ${(a_{i})_{i=1}^{\infty}}$ contradicting the fact that ${B\subseteq A}$.

\hfill$\Box$

Corollary 2 Every subset of an at most countable set is at most countable.

Proof: Let ${A}$ be an at most countable set and ${B\subseteq A}$. If ${A}$ is finite, then ${B}$ is must also be finite. So let us assume ${A}$ is countable. Then ${B}$ cannot be uncountable by theorem 1.

\hfill$\Box$

Corollary 3 An at most countable set that contains a countable subset is countable.

Proof: Let ${A}$ be at most countable and ${B\subseteq A}$ is countable. If ${A}$ is countable then we are done. So we need to prove that ${A}$ cannot be finite. Suppose ${A}$ is finite then there exists a bijection ${f: A\rightarrow J_{n}}$. Let ${g: J\rightarrow B}$. Then the composition ${f\circ g:\mathbb{N}\rightarrow J_{n}}$ must be injective. However, by pigeonhole’s principle we know this cannot happen, thus a contradiction.

\hfill$\Box$

Theorem 4 Countable unions of countable sets is countable.

Corollary 5 At most countable unions of at most countable sets is at most countable.

Let ${\left\{X_{\alpha}|\alpha\in A\right\}}$ be an arbitrary family of sets. We define the Cartesian product ${\prod_{\alpha\in A}X_{\alpha}}$ to be all the functions ${\phi: A\rightarrow\bigcup_{\alpha\in A}X_{\alpha}}$ such that ${\phi(\alpha)\in X_{\alpha}}$. We can think of ${\phi(\alpha)}$ as an evaluation of ${\phi}$ at the ${\alpha}$-th entry. For example if ${A=\mathbb{N}}$, ${\phi(1)}$ is simply the first entry of the Cartesian product.

Theorem 6 Finitely many Cartesian products of countable sets is countable.

Theorem 7 Countable Cartesian products of countable sets is uncountable.

Proof: Let ${S:=\prod_{n=1}^{\infty} A_{n}}$ where ${A_{n}}$ is countable for each ${n\in J}$. Let ${(f_{i}: i\in J)}$ be an enumeration. For each ${n\in J}$ we pick two different element ${a_{n}, b_{n}\in A_{n}}$. Consider the following function:

$\displaystyle f(j) = \left\{ \begin{array}{lr} b_{j} & : \mathrm{if}\, f_{j}(j)=a_{j}\\ a_{j} & : \mathrm{otherwise} \end{array} \right.$

Note ${f\in S}$ obviously. However, note ${f\neq f_{i}}$ for all ${i\in J}$ because ${f}$ differs from every ${f_{i}}$ at least at ${f_{j}(j)}$. Thus ${S}$ in not countable.

\hfill$\Box$

Corollary 8 Let ${A}$ be the set of all sequences whose elements are the digis 0 and 1. Then ${A}$ is uncountable.

Proof: Remember the set ${A}$ is indeed identified with the Cartisian product ${\left\{0,1\right\}^{\mathbb{N}}}$. Although we cannot directly apply theorem 7 because ${\left\{0,1\right\}}$ is finite, we still can use the same Cantor trick. Let ${(f_{i}: i\in J)}$ be an enumeration of ${A}$. We define the following function

$\displaystyle f(j) = \left\{ \begin{array}{lr} 0 & : \mathrm{if}\, f_{j}(j)=1\\ 1 & : \mathrm{otherwise} \end{array} \right.$

Again ${f\in A}$ obviously, but ${f}$ differs from ${f_{i}}$ for every ${i\in J}$. Thus ${A}$ is uncountable.

$\Box$

Theorem 9 There exists no surjection from a set ${X}$ to ${\mathcal{P}(X)}$.

Proof: We prove by contradiction. Let ${\varphi: X\rightarrow\mathcal{P}(X)}$ be a surjection. By definition, for any ${A\in\mathcal{P}(X)}$ there exists ${a\in X}$ such that ${\varphi(x)=A}$. Consider the following set

$\displaystyle Y:=\left\{x\in X| x\notin\varphi(x)\right\}$

So ${Y}$ has an pre-image in ${X}$. Let ${y\in X}$ such that ${\varphi(y)=Y}$. It is either ${y\in Y}$ or ${y\notin Y}$. If it is the first case, then ${y\in X}$ and ${y\notin\varphi(y)=Y}$ by definition, but his contradicts the fact that ${y\in Y}$. If it is the second case, we have ${y\notin Y}$, so ${y\in X}$ and ${y\in\varphi(y)=Y}$, contradiction again. Hence ${\varphi}$ cannot be a surjection and the proof is complete.

\hfill$\Box$