Real Analysis

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