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

- \(\mathbb{N}\) is countable: use \(f : \mathbb{N} \rightarrow \mathbb{N}\) where \(f(x) = x\).
- 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,

- \(\{2, 3, 4, \dots \}\) is countable: use \(f(n) = n + 1\).
- \(\{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,

- \(\mathbb{N} \sim 2\mathbb{N} = \{2, 4, 6, 8, \dots\}\). \(\mathbb{N}\) and \(2\mathbb{N}\) have the
*same cardinality*. - \(\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,

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,

- \(2^A \sim \{\text{function } f : A \rightarrow \{0, 1\}\}\), by membership relation.
\(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).