For two sets \(X\) and \(Y\), we say that the cardinality of \(X\) is less than or equal to the cardinality of \(Y\), or that the equipotency of \(X\) is less than or equal to the equipotency of \(Y\), or that \(Y\) is at least as large as \(X\), or that \(X\) is not larger than \(Y\), if there exists an injective function from \(X\) to \(Y\). We write: \(X\preccurlyeq Y\).
We say that the cardinality of \(X\) is less than the cardinality of \(Y\), or that the equipotency of \(X\) is less than the equipotency of \(Y\), or that \(Y\) is greater than \(X\), or that \(X\) is less than \(Y\), if there exists an injective function from \(X\) to \(Y\) but no bijection from \(X\) to \(Y\). In other words, \(X\preccurlyeq Y\), but \(X\ncong Y\). We write: \(X\prec Y\).
With the above definitions, we can also say that a set \(X\) is countable if \(X\preccurlyeq \mathbb{N}\) and uncountable if \(\mathbb{N}\prec X\).
\(X\prec{\Large\wp}(\mathbb{X})\) for every set \(X\).
The function \(f:\; X\rightarrow {\Large\wp}(\mathbb{X}),\quad f(x)=\{x\}\) is an injective function, because if \(x\neq y\), then \(\{x\}\neq\{y\}\) and thus \(f(x)\neq f(y)\).
Now suppose that there exists a bijection \(g\; X\rightarrow {\Large\wp}(\mathbb{X})\). Define \(D=\bigl\{x\in X\mid x\notin g(z)\bigl\}\). Because \(g\) is surjective, there exists a \(d\in X\) such that \(g(d)=D\). But then we have: \[\begin{aligned}d\in g(d)& \text{ if and only if }d\in D&(\text{because }g(d)=D)\\ &\text{ if and only if }d\notin g(d)&(\text{due to the definition of }D)\end{aligned}\] This is a contradiction, so a bijection \(g\) cannot exist.
The following Cantor-Schröder-Bernstein theorem provides a convenient way to demonstrate the equipotency of sets, because one no longer needs to find a bijective function between two sets, but it suffices to find two injective functions from one set to the other and vice versa.
Let \(X\) and \(Y\) be two sets. If there exists an injective function from \(X\) to \(Y\) and there exists an injective function from \(Y\) to \(X\), then there exists a bijective function from \(X\) to \(Y\) and the two sets are thus equipotent. In formula language:
For two sets \(X\) and \(Y\): \(\text{If }X\preccurlyeq Y\text{ and }Y\preccurlyeq X\text{ then } X\cong Y\).
Assume \(X\preccurlyeq Y\) and \(Y\preccurlyeq X\). Then there are two injective functions \(f:\;X\rightarrow Y\) and \(g\;Y\rightarrow X\). Note that \(Y\cong \mathrm{im}(g)\). To prove that \(Y\cong X\), it is therefore sufficient to prove that \(\mathrm{im}(g)\cong X\). Now, \(\mathrm{im}(g)\subset X\) and the composition \(g\circ f\) is an injective function from \(X\) to \(\mathrm{im}(g)\). It is therefore sufficient to prove the following lemma:
If \(U\subset X\) and \(U\preccurlyeq X\), then \(U\cong X\).
The proof of this lemma is quite technical and we will omit it.
The open and closed intervals \((0,1)\) and \([0,1]\) in \(\mathbb{R}\) are equipotent. In formula form: \((0,1)\cong [0,1]\).
The function \(\mathrm{id}:\;(0,1)\rightarrow [0,1]\) is injective. Define the function \(\mathrm{id}:\;[0,1]\rightarrow (0,1)\) by \(f(x)=\tfrac{1}{3}(x+1)\). The function \(f\) is also injective. According to the Cantor-Schröder-Bernstein theorem, the two intervals are then equipotent.
\(\mathbb{R}\times \mathbb{R} \cong \mathbb{R}\).
We already know \(\mathbb{R}\cong (0,1)\). Thus, i suffices to show: \((0,1)\times (0,1) \cong (0,1)\). Each element \((x,y)\in (0,1)\times (0,1)\) can be written in decimal form as \[(x,y)=(0.\xi_1\xi_2\xi_3\cdots, 0.\eta_1\eta_2\eta_23\cdots)\] where each decimal expansion contains an infinite number of nonzero digits (write, for example, \(1/2=0.4999\cdots\)). The function \[f:\; (0,1)\times (0,1)\rightarrow (0,1),\quad f(x,y)=0.\xi_1\eta_1\xi_2\eta_2\xi_3\eta_3\cdots\] is injective. The function \[g:\;(0,1)\rightarrow (0,1)\times (0,1),\quad g(x)=(x,\tfrac{1}{2})\] is also injective. Thus, accoding to the Cantor-Schröder-Bernstein theorem: \((0,1)\times (0,1) \cong (0,1)\).
The Cantor-Schröder-Bernstein theorem
