Cardinality

# Functions

Recall a function $$f : A \rightarrow B$$ maps $$x \in A$$ to $$f(x) \in B$$. $$A$$ is the domain of $$f$$. $$B$$ is the codomain of $$f$$.

If $$C \subset A$$ and $$D \subset B$$, define $$f(C) = \{f(x) : x \in C\}$$ as the image of $$C$$, and $$f^{-1}(D) = \{x : f(x) \in D\}$$ as the inverse image of $$D$$.

When $$f(A) = B$$, i.e. the range of $$A$$ is the same as its codomain, $$f$$ is onto, or a surjection, denoted $$f : A \twoheadrightarrow B$$.

When $$f(x) = f(y)$$ implies $$x = y$$, $$f$$ is one-to-one, or an injection, denoted $$f : A \hookrightarrow B$$, or $$f : A \rightarrowtail B$$.

When $$f$$ is one-to-one and onto, $$f$$ is a bijection ($$f$$ is denoted by an arrow with a hook on its tail and two heads pointing to the right), and $$A$$ and $$B$$ are in one-to-one correspondence, denoted $$A \sim B$$.

# Cardinality

Let $$J_n := \{1, 2, \dots, n\}$$, and $$J_0 := \emptyset$$.

A set $$A$$ is finite if $$A \sim J_n$$. Otherwise, $$A$$ is infinite. $$A$$ is countable if $$A \sim \mathbb{N}$$.

For example,

1. $$\mathbb{N}$$ is countable: use $$f : \mathbb{N} \rightarrow \mathbb{N}$$ where $$f(x) = x$$.
2. A sequence $$x_1, x_2, x_3, \dots$$ of distinct terms is countable: use $$f(n) = x_n$$.

A set that can be listed in a sequence is countable.

For example,

1. $$\{2, 3, 4, \dots \}$$ is countable: use $$f(n) = n + 1$$.
2. $$\{1, 2, 3, \dots, k - 1, k + 1, k + 2, \dots \}$$ is countable: use \begin{align*} f(n) = \begin{cases} n & \text{if } n < k \\ n + 1 & \text{otherwise.} \end{cases} \end{align*}

Theorem. $$\mathbb{N}$$ is infinite.

Proof sketch (by induction on $$n$$). Show that $$\mathbb{N} \nsim J_n$$.

Base case ($$\mathbb{N} \xleftarrow{g} \{1\}$$): Consider $$\mathbb{N} \setminus J_1 \neq \emptyset$$. So $$g$$ is not onto.

Inductive step: Show if $$J_n \nsim \mathbb{N}$$ then $$J_{n+1} \nsim \mathbb{N}$$. If there were a bijection $$h$$ such that $$\mathbb{N} \xleftarrow{h} J_{n+1} = \{1, \dots, n, n+1\}$$, then there would be a bijection $$\widehat{h}$$ such that $$\mathbb{N} \setminus \{\widehat{h}(n+1)\} \xleftarrow{\widehat{h}} J_n = \{1, \dots, n\}$$. By a previous example, there is a bijection $$f$$ such that $$\mathbb{N} \xleftarrow{f} \mathbb{N} \setminus \{\widehat{h}(n+1)\}$$. Thus, there exists a bijection $$\mathbb{N} \leftarrow J_n = \{1, \dots, n\}$$. QED.

For example,

1. $$\mathbb{N} \sim 2\mathbb{N} = \{2, 4, 6, 8, \dots\}$$. $$\mathbb{N}$$ and $$2\mathbb{N}$$ have the same cardinality.
2. $$\mathbb{Z} = \{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \}$$ is countable: use \begin{align*} f(n) = \begin{cases} -2n & \text{if } n < 0 \\ 2n + 1 & \text{otherwise.} \end{cases} \end{align*}

Theorem. Every infinite subset $$E$$ of a countable set $$A$$ is countable.

Theorem. If $$A$$ is countable then $$A \times A$$ is countable.

Theorem. $$\mathbb{Q}$$ is countable.

Theorem. If $$A$$ is countable then $$A^k$$ is countable.

Theorem. $$\mathbb{R}$$ is not countable.

The proof for $$\mathbb{R}$$ not being countable does not imply $$\mathbb{Q}$$ is not countable because the resulting constructed number may not be in $$\mathbb{Q}$$.

Theorem. For any set $$A$$, $$A \nsim 2^A$$, where $$2^A$$ is the power set of $$A$$.

Theorem. The countable union of countable sets is countable.

Proof. Let each $$A_1, A_2, A_3, \dots$$ be countable. Then, \begin{align} A_1 & = \{a_{11}, a_{12}, a_{13}, a_{14}, \dots\}, \\ A_2 & = \{a_{21}, a_{22}, a_{23}, a_{24}, \dots\}, \\ A_3 & = \{a_{31}, a_{32}, a_{33}, a_{34}, \dots\}, \\ A_4 & = \{a_{41}, a_{42}, a_{43}, a_{44}, \dots\}, \\ \vdots \end{align}

Zigzagging through the above listings gives a listing, implying $$\bigcup_{i=1}^{\infty} A_i$$ is countable. QED.

Notation: Use $$\bigcup_{\alpha \in J} A_\alpha$$, where $$J$$ is an index set, for possibly uncountable collection.

For example,

1. The set of computer programs is at most countable.

Recall $$\mathbb{R}$$ is not countable (say $$\mathbb{R}$$ is uncountable).

So there are real numbers that are not computable (it cannot be specified up to some arbitrary precision)!

Cantor’s Theorem (diagonalization argument). For any set $$A$$, we have $$A \nsim 2^A$$.

Proof (by contradiction). Suppose there exists a bijection $$f : A \rightarrow 2^A$$. Then $$a \mapsto f(a) \subset A$$. Let $$B = \{a : a \notin f(a)\}.$$

If $$B = f(x)$$ for some $$x \in A$$, consider $$x$$. If $$x \in B$$ then $$x \notin f(x) = B$$, a contradiction. Hence, $$x \notin B$$, which implies $$x \notin f(x)$$, so $$x \in B$$, a contradiction.

Thus, $$B \neq f(x)$$ for any $$x \in A$$ (or $$B$$ is not an image of $$x$$ for any $$x \in A$$). QED.

For example,

1. $$2^A \sim \{\text{function } f : A \rightarrow \{0, 1\}\}$$, by membership relation.
2. $$2^{\mathbb{R}} \sim$$ all functions from $$\mathbb{R}$$ to $$\{0, 1\}$$.

There are infinitely many cardinalities. Let $$\omega$$ be an ordinal number. $0, 1, 2, \dots, \aleph_0, \aleph_1, \aleph_2, \dots, \aleph_\omega, \dots$

The continuum hypothesis ($$\aleph_1 = c$$, where $$c$$ is the cardinality of $$\mathbb{R}$$) is provably undecidable (independent of ZFC).