Cantor-Schröder-Bernstein

One important thing injections help us define are the concept for "sizes" of sets, an ability to compare the number of elements of two sets. Assume you have children and chairs and you want to know whether you have enough for everyone to sit. If you are able to "map" each child to a different chair, than you know you have at least as many chairs as children, this is the core idea of Cardinality. In 1887 Cantor published a theorem that became a pillar of set theory, it states that if exists an injection from $A$ to $B$ and an injection from $B$ to $A$, then exists a bijection between the two. In 1898 both Schröder and Bernstein independently published their proofs of the theorem. The core idea is simple: given an injection $f$ from $A$ to $B$ and an injection $g$ from $B$ to $A$, construct a set $C$ such that $f$ restricted to $C$ and $g^{-1}$ restricted to $A \setminus C$ is a bijection onto $B$.

Notations: Let $A$, $B$ be sets, then:

1. If exists an injection $f:A \rightarrow B$, denote: $|A| \le |B|$.
2. If exists a bijection $f: A \rightarrow B$, denote: $|A| = |B|$, otherwise denote: $|A| \neq |B|$.
3. If $|A| \le |B|$ and $|A| \neq |B|$, denote: $|A| < |B|$.

Claims: Let $A, B, C$ be sets, then:

1. $|A| = |A|$.
2. $A \subseteq B \Longrightarrow |A| \le |B|$.
3. $|A|=|B|\Longleftrightarrow|B|=|A|$.
4. if $|A| \le |B|$ and $|B| \le |C|$ then $|A| \le |C|$.
5. if $|A| = |B|$ and $|B| = |C|$ then $|A| = |C|$.
6. if $f: A \rightarrow B$ injection, then $|A| = |f(A)|$.

Proofs:

1. The identity function $\text{Id}:A \rightarrow A$, defined as $f(a)=a$ is a bijection.
2. The identity function $\text{Id}:A \rightarrow B$, defined as $f(a)=a$ is an injection.
3. Let $f: A \rightarrow B$ be a bijection, then its inverse $f^{-1}:B \rightarrow A$ is also a bijection.
4. Let $f:A \rightarrow B$ and $g: B \rightarrow C$ be injections, then $(f \circ g):A \rightarrow C$ is an injection.
5. Let $f:A \rightarrow B$ and $g: B \rightarrow C$ be bijections, then $(f \circ g):A \rightarrow C$ is a bijection.
6. $f$ is a bijection onto its image.

Claim (Cantor-Schröder-Bernstein theorem): Let $A, B$ be sets, then if $|A| \le |B|$ and $|B| \le |A|$ holds that $|A| = |B|$.

Proof: Let $f:A \rightarrow B$ and $g:B \rightarrow A$ be injections, then $(g \circ f): A \rightarrow A$ is an injection, and $g(f(A)) \subseteq g(B) \subseteq A$. Define $A_0 := A$ and recursively for each natural $n \in \mathbb{N}$ define $A_{S(n)} := (g \circ f)(A_n)$, similarly define $B_0 := g(B)$ and recursively for each $n \in \mathbb{N}$ define $B_{S(n)} := (f \circ g))B_n$. Holds that $A_1 \subseteq B_0 \subseteq A_0$, let $n \in \mathbb{N}$ be natural such that $A_{S(n)} \subseteq B_n \subseteq A_n$, then $(f \circ g)(A_{S(n)})(B_n) \subseteq (f \circ g)(A_n)$ and therefore $A_{S(S(n))} \subseteq B_{S(n)} \subseteq A_{S(n)}$ and from the principle of induction for each $n \in \mathbb{N}$ holds that $A_{S(n)} \subseteq B_n \subseteq A_n$. We can denote $A$ as a disjoint union $$A=\bigcup\limits _{n\in\mathbb{N}}\left((A_{n}\setminus B_{n})\cup(B_{n}\setminus A_{S(n)})\right)=\bigcup\limits _{n\in\mathbb{N}}(A_{n}\setminus B_{n})\cup\bigcup\limits _{n\in\mathbb{N}}(B_{n}\setminus A_{S(n)})$$ Denote $C := \bigcup\limits _{n\in\mathbb{N}}(A_{n}\setminus B_{n}),D := \bigcup\limits _{n\in\mathbb{N}}(B_{n}\setminus A_{S(n)})$, therefore $D\subseteq B_{0}\setminus A_{1}\subseteq B_{0}=g(B)$. $g$ is a bijection onto $B_0$ and therefore exists a bijection $g^{-1}:B_0 \rightarrow A$. Define $h: A \rightarrow B$ in the following way: $$h(a) := \begin{cases} f(a) & a\in C\\ g^{-1}(a) & a\in D \end{cases}$$ Let ${x, y} \subseteq A$ such that $h(x)=h(y)$, if ${x, y} \subseteq C$ then $f(x) = f(y)$ and from the injectiveness of $f$ we get $x = y$, if ${x, y} \subseteq D$ then $g^{-1}(x) = g^{-1}(y)$ and from the injectiveness of $g^{-1}$ we get $x = y$ as well. Assume by way of contradiction that $x \in C$ while $y \in D$, then $f(x)=g^{-1}(y)$ and therefore $(g \circ f)(x)=y$, but $$ \begin{equation} \begin{split} (g\circ f)(C) & =(g\circ f)(\bigcup\limits _{n\in\mathbb{N}}(A_{n}\setminus B_{n})) \\ & =\bigcup\limits _{n\in\mathbb{N}}(g\circ f)(A_{n}\setminus B_{n}) \\ & =\bigcup\limits _{n\in\mathbb{N}}\left((g\circ f)(A_{n})\setminus(g\circ f)(B_{n})\right) \\ & =\bigcup\limits _{n\in\mathbb{N}}\left(A_{S(n)}\setminus B_{S(n)}\right) \\ & \subseteq C \end{split} \end{equation}$$ resulting in $(g \circ f)(x) \in C$ while $y \in D = A \setminus C$ in contradiction, and therefore $h$ is an injection. Calculate: $$\begin{equation} \begin{split}f(C)\cup g^{-1}(D) & =f(\bigcup\limits _{n\in\mathbb{N}}(A_{n}\setminus B_{n}))\cup g^{-1}(\bigcup\limits _{n\in\mathbb{N}}(B_{n}\setminus A_{S(n)})) \\ & =\bigcup\limits _{n\in\mathbb{N}}\left(f(A_{n})\setminus f(B_{n}))\right)\cup\bigcup\limits _{n\in\mathbb{N}}\left(g^{-1}(B_{n})\setminus g^{-1}(A_{S(n)})\right) \\ & =\bigcup\limits _{n\in\mathbb{N}}\left(f(A_{n})\setminus f(B_{n}))\right)\cup\left(g^{-1}(B_{0})\setminus g^{-1}(A_{1})\right)\cup\bigcup\limits _{n\in\mathbb{N}}\left(g^{-1}(B_{S(n)})\setminus g^{-1}(A_{S(S(n))})\right) \\ & =\bigcup\limits _{n\in\mathbb{N}}\left(f(A_{n})\setminus f(B_{n}))\right)\cup\left(B\setminus f(A)\right)\cup\bigcup\limits _{n\in\mathbb{N}}\left(f(B_{n})\setminus f(A_{S(n)})\right) \\ & =\left(B\setminus f(A)\right)\cup f(C)\cup f(D) \\ & =\left(B\setminus f(A)\right)\cup f(A) \\ & =B\end{split} \end{equation}$$ And therfore $h$ is onto $B$.

Claim (Cantor Theorem): Let $A$ be a set, then $|A| < |P(A)|$.

Proof: The function $f: A \rightarrow P(A)$ defined $f(a) = {a}$ is clearly an injection and therefore $A \le P(A)$. Let $f:A \rightarrow P(A)$ be a function and denote $B := \{a\in A: a \notin f(a)\}$ and assume by way of contradiction that exists $a_0 \in A$ such that $f(a)=B$, let $b \in B$, then $b \in f(a)$, from the equation, but also $b \notin f(a)$ from the defintion of $B$ by contradiction and therefore $f$ cannot be onto.

Corollary: For each set $A$ exists a set $B$ such that $|A| < |B|$.

Claim: Let $A, B$ be sets such that $|A| = |B|$, and let $a_0 \in A$ and $b_0 \in B$, then exists a bijection $f: A \rightarrow B$ such that $f(a_0)=b_0$.

Proof: Exists a bijection $h: A \rightarrow B$, define $g:A\rightarrow A$ in the following way: $$g(a) := \begin{cases} h^{-1}(b_{0}) & a=a_{0}\\ a_{0} & a=h^{-1}(b_{0})\\ a & \text{otherwise} \end{cases}$$ It is clear that $g$ is a bijection since it is its own inverse, therefore $f:=(h \circ g)$ is a bijection as well, and holds that $f(a_{0})=h(g(a_{0}))=h(h^{-1}(b_{0}))=b_{0}$.

Finite Sets

We shall now see some how cardinality works with regard to the natural numbers, the results are unsurprising but critical to the discussion about sets.

Claim: Let $m \in \mathbb{N}$ be a natural number, then for each natural $n \in \mathbb{N}$ such that $n < m$ holds that $|n| < |m|$.

Proof: If $m=0$, does not exists $n \in \mathbb{N}$ such that $n < m$ and the claim holds vacuously. Let $m_0 \in \mathbb{N}$ such that for each $n < m_0$ holds that $|n| < |m_0|$, and let $n < S(m_0)$. Since $n \subseteq m_0$ holds that $|n| \le S(m_0)$. If $n = 0$ the only function from $n$ is the empty set, and it is not a bijection onto $S(m_0)$, otherwise exists $k \in \mathbb{N}$ such that $S(k) = n$. Assume by way of contradiction that $|S(m_0)| = |n|$, then exists an injection $f:S(m_0)\rightarrow n$ such that $f(m_0) = k$, therefore $f\upharpoonright m_{0}$ is a bijection from $m_0$ onto $k < m_0$ in contradiction to the choice of $m_0$, and by the principle of induction the claim holds.

Definition: Let $A$ be a set, then $A$ is to be finite, if exists $n \in \mathbb{N}$ such that $|A| = |n|$, otherwise it is said to be infinite. Denote $|A| = n$ and $A$ is said to have $n$ elements.

Corollary Let $A$ be a set such that $|A|=0$, then $A=\emptyset$.

Claim: Any finite set $A$ with $n \in \mathbb{N}$ elements, and for all $B \subseteq A$ subset of $A$, holds that $B$ is finite.

Proof: If $n = 0$, then any set $A$ with $0$ elements is the empty set, and all its subsets are also the empry set with $0$ elements. Let $n_0 \in \mathbb{N}$ be natural such that any set $A$ with $n_0$ elements and any $B \subseteq A$ holds that $B$ is finite, nad let $A$ be a set with $S(n_0)$ elements and let $B \subseteq A$ be a subset. If $B = A$ then $B$ has $S(n_0)$ elements and the claim holds, otherwise exists $a\in A \setminus B$ and a function $f:A\rightarrow S(n_0)$ such that $f(a)=n_0$, then $f\upharpoonright(A\setminus\{a\})$ is an injection from $A\setminus {a}$ to $n_0$ and $|A\setminus \{a\}| = n_0$ and $B \subseteq A \setminus \{a\}$, therefore $B$ is finite and from the principle of induction the claim holds for all $n \in \mathbb{N}$.

Claim: Let $A$ be a finite set, and let $B \subset A$ be a proper subset, then $|B| < |A|$.

Proof: $B \subseteq A$ and therefore $|B| \le |A|$. Exist natural numbers $n, m$ such that $|A|=n, |B|=m$, and bijections $f:n\rightarrow A, g:m\rightarrow B$. Assume by way of contradiction that exists a bijection $h:A\rightarrow B$, then $(g \circ h \circ f)$ is a bijection from $n$ to $m$ in contradiction.

Claim: $\mathbb{N}$ is infinite.

Proof: Define $f:\mathbb{N}\rightarrow \mathbb{N}\setminus \{0\}$ in the following way $f(n) := S(n)$. $f$ is a bijection and therefore $|\mathbb{N}|=|\mathbb{N}\setminus\{0\}|$ which would cause a contradiction if it were finite.

Claim: Let $A$ be a finite set, let $B$ be any set, and let $f: A\rightarrow B$ be a function, then $f(A)$ is finite and $|f(A)| \le |A|$.

Proof: $A$ is finite, therefore exists $n \in \mathbb{N}$ and a bijection $g:A \rightarrow n$. Define $h:f(A) \rightarrow A$ in the following way: $$h(b) := g^{-1}(\min\left\{ g(a):a\in f^{-1}(\{b\})\right\} )$$ Let $\{b_0, b_1\} \subseteq f(A)$ such that $h(b_0)=h(b_1)$, then $$\min\left\{ g(a):a\in f^{-1}(\{b_{0}\})\right\} =\min\left\{ g(a):a\in f^{-1}(\{b_{1}\})\right\} $$ then $$\left\{ g(a):a\in f^{-1}(\{b_{0}\})\right\} \cap\left\{ g(a):a\in f^{-1}(\{b_{1}\})\right\} \neq\emptyset$$ then $$f^{-1}(\{b_{0}\})\cap f^{-1}(\{b_{1}\})\neq\emptyset$$ Let $a_{0}\in f^{-1}(\{b_{0}\})\cap f^{-1}(\{b_{1}\})$, then $f(a_0)=b_0$, and similarly $f(a_0)=b_1$ and therefore $b_0=b_1$ and $h$ is a bijection and $|f(A) \le |A|$, and in prticular $f(A)$ is finite.