1.6

Cardinality

Definition

We say that \(X, Y\) have the same cardinality if they are equivalent.

Notation: \(|X| = |Y|\)

Example

If \(X\approx\mathbb{N}\), then we say that \(X\) has cardinal \(\aleph_0\) (aleph). And we will write \(|X| = \aleph_0\).

So, \(|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0\) where \(\aleph_0\) is the first infinite cardinality.

If \(X\approx(0,1)\), then we say that \(X\) has cardinal \(\mathfrak{c}\) (continuum).
And we will write \(|X| = \mathfrak{c}\).

So \(|\mathbb{R}| = |(0,1)| = |(a,b)| = \mathfrak{c}.\) In addition, \(\mathfrak{c} \neq \aleph_0.\)

There are more cardinals.

Define \(|X| \leq |Y|\).

Definition

\(|X| \leq |Y|\) means there exists \(f: X \to Y\) injective.
\(|X| < |Y|\) means \(|X| \leq |Y|\) and \(|X| \neq |Y|\).

For example: \(|[n] |<| [n+1] |< |\mathbb{N}| < |\mathbb{R}|.\)

Obs.: \(|X|\leq |X|\)
If \(|X| \leq |Y|\) and \(|Y| \leq |Z|\), then \(|X| \leq |Z|.\)

Cantor–Schröder–Bernstein Theorem

If \(|X| \leq |Y|\) and \(|Y| \leq |X|\), then \(|X| = |Y|\).

Proof:
We prove first the following: If \(f: X \to X\) is injective and \(f(X) \subseteq B \subseteq X\), then \(X\approx B\).

If \(f(X) = X\), then \(B = X\). (Trivial)

We assume \(f(X) \neq X\), so \(f(X)\neq B\neq X\). (If \(f(X)=B\) also trivial)

Let \(D = B - f(X)\). Let \(W=D\cup f(D)\cup f^2(D)\cup f^3(D)\cup f^4(D)\cup\dots\subseteq B\)

Let \(H: X \to B\) be

\[ H(x) = \begin{cases} x & \text{if } x \in W, \\ f(x) & \text{if } x \in X - W. \end{cases} \]

\(H\) is injective: Let \(x_1, x_2 \in X\) such that \(x_1 \neq x_2\).

If \(x_1, x_2 \in W\), then \(H(x_1) = x_1 \neq x_2 = H(x_2)\).
If \(x_1, x_2 \in X - W\), then \(H(x_1) = f(x_1) \neq f(x_2) = H(x_2)\).

Suppose \(x_1 \in W\) and \(x_2 \in X - W\).

If \(H(x_1) = H(x_2)\), then \(x_1 = f(x_2)\). (So \(x_1 \in f(X)\)).

Then \(x_1 \in f(X)\), so \(x_1 \in f^n(D)\) for some \(n \geq 1\). Hence \(x_1 = f(\tilde{x}_1)\) for some \(\tilde{x}_1\in f^{n-1}\left(D\right)\subseteq W\).

Then \(f(\tilde{x}_1) = f(x_2)\), so \(\tilde{x}_1 = x_2\). But \(\tilde{x}_1\in W\) and \(x_2\in X-W\) a contradiction.

Therefore, \(H(x_1) \neq H(x_2)\) .

\(H\) is surjective:

Let \(y \in B\).

If \(y \in W\), then \(y = H(y)\), so \(y \in \text{Im}(H)\).
If \(y \in B - W \subseteq f(X)\), then there exists \(x \in X\) such that \(y = f(x)\).

Now \(x \in X - W\), otherwise \(x \in W\) and then \(f(x) = y\) is also in \(W\), which is not true because \(y \notin W\).

Since \(x \in X - W\), \(H(x) = f(x) = y\).

We now prove the theorem.

Suppose \(F:X\to Y\) inj. and \(G:Y\to X\) inj.

Let \(f = G \circ F : X \to X\), injective

Let \(B = G(Y) \supseteq G(F(X)) = f(X)\).

By the first part, \(X\approx B\). But \(B=\text{Im}(G)\approx Y\) because \(G\) is injective.

Hence \(X\approx Y\) by transitivity.

Summarizing:

\(|X| \leq |X|\).
\(|X| \leq |Y| \; \& \; |Y| \leq |X| \implies |X| = |Y| \; \text{(CSB)}\).
\(|X| \leq |Y| \; \& \; |Y| \leq |Z| \implies |X| \leq |Z|\).

Example:
If \(A \subseteq \mathbb{R}\) contains some open interval \((a,b)\), then \(A\approx\mathbb{R}\). (e.g., \(\mathbb{R}\approx\mathbb{Z}\cup(0,1)\)).

Why?
\(|A| \leq |\mathbb{R}|\) because \(A \subseteq \mathbb{R}\).

\(|\mathbb{R}| = |(a,b)| \leq |A|\) because \((a,b) \subseteq A\).

\(\therefore |A| = |\mathbb{R}|\).

So far we have two infinite cardinals: \(\aleph_0, \mathfrak{c}\). Are there more?

Cantor's Theorem:

\(|X| < |P(X)|\)(So \(|\mathbb{R}| < |P(\mathbb{R})| < |P(P(\mathbb{R}))| < \dots\))

Strategy: Cantor's idea

Trick: discuss \(b\) belonging

Proof:

Firstly, we prove \(|X| \leq |P(X)|\).

\(\exists X\to P(X)\) given \(x\mapsto\{x\}\), so \(|X| \leq |P(X)|\).

Then we prove \(|X|\neq |P(X)|\), suppose they are equal

Then there exists a bijective function \(f: X \to P(X)\).

Let \(A = \{ x \in X : x \not\in f(x) \} \subseteq X,\)so \(A \in P(X)\).

We will show that \(A \not\in \text{Im}(f)\), which will lead to a contradiction.

Suppose that \(A = f(x)\) for some \(x \in X\).

If \(x \in f(x)\), then \(x \not\in A = f(x)\), not possible.
If \(x \not\in f(x)\), then \(x \in A = f(x)\), not possible.

\(\therefore A \not\in \text{Im}(f)\).

So far, we have: \(\aleph_0 = |\mathbb{N}| < |P(\mathbb{N})|\) and \(\mathfrak{c} = |\mathbb{R}|\)

Theorem

\(|\mathbb{R}| = |P(\mathbb{N})|\)

Proof (Sketch):

\(|P(\mathbb{N})|=|\{0,1\}^{\mathbb{N}}|=|\{1,2\}^{\mathbb{N}}|=|\{\left(a_1,a_2,a_3,\ldots):a_{i}\in\left\lbrace1,2\right\rbrace\}|\right.\)

Let \(f:\{(a_1,a_2,a_3,\ldots):a_{i}\in\{1,2\}\}\to(0,1)\)

\((a_1, a_2, a_3, \ldots) \mapsto 0.a_1a_2a_3\ldots\)

\((1,2,1,2,\ldots)\mapsto0.1212\ldots\)

This is injective, so \(|P(\mathbb{N})| \leq |(0, 1)| = |\mathbb{R}|\)

On the other hand, \(|\mathbb{R}| = |(0, 1)|\)and there exists an injective function

\(g: (0, 1) \to \{ (a_1, a_2, a_3, \ldots) : a_i \in \{0, 1, \ldots, 9\} \}.\)

For example:\(0.123123\mapsto(1,2,3,1,2,3,\ldots).\)

Now, any \(a \in \{0, 1, 2, \ldots, 9\}\) can be written in a unique way as:

\(a=a\left(3\right)2^3+a\left(2\right)2^2+a\left(1\right)2+a\left(0\right)\) with \(a\left(0\right),a\left(1\right),\ldots,a\left(3\right)\in\{0,1\}\).

For example, \(7=0\cdot2^3+1\cdot2^2+1\cdot2+1\) \(9=1\cdot2^3+0\cdot2^2+0\cdot2+1\)

We now define:

\(h:\{(a_1,a_2,a_3,\ldots):a_{i}\in\{0,1,\ldots,9\}\}\to\{(b_1,b_2,\ldots):b_{i}\in\{0,1\}\}=\left\lbrace0,1\right\rbrace^{\mathbb{N}}\)

For example:

\((a_1,a_2,a_3,\ldots)\mapsto\left(a_1\left(0\right),a_1\left(1\right),a_1\left(2\right),a_1\left(3\right),a_2\left(0\right),a_2\left(1\right),a_2\left(2\right),a_2\left(3\right),\ldots\right)\)This function is injective.

So \(h\circ g:(0,1)\to\{0,1\}^{\mathbb{N}}\) is injective, and

\(|\R|=|(0,1)| \leq |\{0,1\}^\mathbb{N}| = |P(\mathbb{N})|.\)

By the Cantor-Schröder-Bernstein Theorem, \(|\mathbb{R}| = |P(\mathbb{N})|.\)

Axiom of Choice:

If \((X_i)_{i \in I}\) is a family of non-empty sets, then \(\exists f:I\to\bigcup_{i\in I}X_{i}\;\text{such that}\;f(i)\in X_{i}\)

Theorem

\(|X|\leq|Y|\;\iff\;\exists f:Y\to X\) surjective

Proof:

\(\Rightarrow)\)

Define \(g: Y \to X\) such that \(g(y)=\begin{cases}f^{-1}\left(y\right),y\in f\left(X\right)\\ x_0,y\notin f(x)\end{cases}\), then \(g\) is surjective.

(\(\Leftarrow\)):

Consider \(\left\lbrace g^{-1}(x)\right\rbrace_{x\in X}\). Since \(g\) is surjective: \(g^{-1}(x) \neq \emptyset.\)

By the Axiom of Choice: \(\exists f: X \to \bigcup_{x \in X} g^{-1}(x) = Y \; \text{s.t.} \; f(x) \in g^{-1}(x) \; \forall x \in X.\)

This is injective because if \(x \neq x'\), then \(g^{-1}(x) \cap g^{-1}(x') = \emptyset.\)

Corollary:

\(X\approx Y\;\iff\;\exists X\to Y\;\text{injective and }\exists X\to Y\text{surjective}\)

\(\exists X\to Y\;\text{injective}\Rightarrow\left|X|\leq|Y|,\quad\exists X\to Y\text{surjective}\Rightarrow|Y|\leq|X|\right.\)