Back to Ishan Levy’s website

Analysis Theorems

1 Set Theory

Here are some basic theorems from introductory analysis.
  • Theorem 1.1 (Cantor-Bernstein). If \(f:X \to Y\) and \(g:Y \to X\) are injections, \(|X|=|Y|\).

  • Proof. We will construct a function \(h: X \to Y\) that is a bijection. First, define \(C \subset X\) as \(\bigcup _{n \in \NN \cup 0}(g \circ f)^n(A-g(B))\). Then we define

    \[ h(x) = \begin {cases} f & x \in C \\ g^{-1} & x \notin C \end {cases} \]

    We can now check this is a bijection. For injectivity, suppose \(h(a)=h(b)\), we’d like to show \(a = b\). As \(f,g^{-1}\) are injective, it suffices to suppose \(a \in C, b \notin C\) and find a contradiction. Then \(g^{-1}(b)=h(b)=h(a)=f(a)=f\circ (g\circ f)^n(c)\), but by applying \(g\) to each side of this equation we have \(b \in C\), a contradiction.

    For surjectivity, let \(y \in Y\). Suppose \(g(y) \notin C\). Then \(h(g(y)) = y\). Now suppose \(g(y) \in C\). Then \(g(y) = (g\circ f)^n(c)\) with \(c \notin g(B)\), which implies \(n\geq 1\). Then by injectivity of \(g\) we get \(y = f((g\circ f)^{n-1}(c)) = h((g\circ f)^{n-1}(c))\).