We define the equinumerosity relation \(\sim\) on sets as \[ \sim \: \coloneq \{(A, B) \mid \exists f(f: A \twoheadrightarrowtail B)\} \]
If two sets \(A\), \(B\) satisfies the equinumerosity relation, we say that the two sets are equinumerous, denoted as \(A \sim B\). Note that we use \( f: A \twoheadrightarrowtail B\) to denote a bijective function from \(A\) to \(B\). Similarly, we use \( f: A \rightarrowtail B \) to denote an injective function from \(A\) to \(B\), and \( f: A \twoheadrightarrow B \) denotes a surjective function from \(A\) to \(B\). We will now prove that equinumerosity is an equivalence relation.
The equinumerosity relation \(\sim\) is an equivalence relation.
For any set \(A\), there exists the identity map \( \iota \) such that \( \iota: A \twoheadrightarrowtail A \). Therefore, \( A \sim A \), which proves reflexivity. For any sets \(A\) and \(B\), if \( A \sim B \), then there exists a function \(f\) such that \( f: A \twoheadrightarrowtail B \), and thus there exists an inverse function \( g = f^{-1} \) such that \( g: B \twoheadrightarrowtail A \). Therefore, \( B \sim A \), which proves symmetry. For any sets \(A\), \(B\), and \(C\), if \( A \sim B \) and \( B \sim C \), then there exists a function \(f\) such that \( f: A \twoheadrightarrowtail B \), and a function \(g\) such that \( g: B \twoheadrightarrowtail C \), and thus there exists a function \( h = f \circ g \) such that \( h: A \twoheadrightarrowtail C \). Therefore, \( A \sim C \), which proves transitivity. Therefore, \( \sim \) is an equivalence relation. \( \boxed{\text{Q.E.D.}} \)
The following are some properties of equinumerosity given in Definition 1.
Let \(A\), \(B\), \(C\), \(D\) be sets, \(n \in \mathbb{N}\), then: \begin{align*} &\text{1.}\ \ \ A \sim C \land B \sim D \land A \cap B = C \cap D = \emptyset \to A \sqcup B \sim C \sqcup D \\ &\text{2.}\ \ \ A \sim C \land B \sim D \to A \times B \sim C \times D \\ &\text{3.}\ \ \ A \times (B \times C) \sim (A \times B) \times C \\ &\text{4.}\ \ \ A \times B \sim B \times A \\ &\text{5.}\ \ \ A \sim C \land B \sim D \to A^B \sim C^D \\ &\text{6.}\ \ \ B \cap C = \emptyset \to A^{B \sqcup C} \sim A^B \times A^C \\ &\text{7.}\ \ \ (A^B)^C \sim A^{B \times C} \\ &\text{8.}\ \ \ (A \times B)^C \sim A^C \times B^C \\ &\text{9.}\ \ \ A^n \sim A^{\mathbb{N}_{< n}} \\ &\text{10.}\ \ \ A^\infty \sim A^{\mathbb{N}} \end{align*}
1. Since \( A \sim C \) and \( B \sim D \), there exist functions \(f\) and \(g\) such that \( f: A \twoheadrightarrowtail C \) and \( g: B \twoheadrightarrowtail D \). Then \( \varphi = f \sqcup g \) is the bijection from \( A \sqcup B \) to \( C \sqcup D \), which proves (1).
2. Since \( A \sim C \) and \( B \sim D \), there exist functions \(f\) and \(g\) such that \( f: A \twoheadrightarrowtail C \) and \( g: B \twoheadrightarrowtail D \). Let \( \varphi: A \times B \to C \times D \), where \( (a, b) \mapsto (f(a), g(b)) \), then \( \varphi \) is clearly a bijection, which proves (2).
3. Let \( \varphi: A \times (B \times C) \to (A \times B) \times C \), where \( (a, (b, c)) \mapsto ((a, b), c) \), then \( \varphi \) is clearly a bijection, which proves (3).
4. Let \( \varphi: A \times B \to B \times A \), where \( (a, b) \mapsto (b, a) \), then \( \varphi \) is clearly a bijection, which proves (4).
5. Since \( A \sim C \) and \( B \sim D \), there exist functions \(f\) and \(g\) such that \( f: A \twoheadrightarrowtail B \) and \( g: C \twoheadrightarrowtail D \). Let \( \varphi: A^B \to C^D \), where \( h \mapsto \{(f(a), g(b)) \mid h(a) = b\} \). Then \( \varphi^{-1}: C^D \to A^B \), \( h \mapsto \{(f^{-1}(a), g^{-1}(b)) \mid h(a) = b\} \). Hence \( \varphi \) is also a bijection. This proves (5).
6. Let \( \varphi: A^B \times A^C \to A^{B \sqcup C} \), where \( (f, g) \mapsto f \sqcup g \). Then \( \varphi^{-1}: A^{B \sqcup C} \to A^B \times A^C \), \( f \mapsto (f \restriction B, f \restriction C) \), Hence \( \varphi \) is also a bijection. This proves (6).
7. Let \( \varphi: (A^B)^C \to A^{B \times C} \), where \( f_b(a) \mapsto \varphi(f_b)(a, b) \), then \( \varphi \) is clearly a bijection, which proves (7).
8. Let \( \varphi: (A \times B)^C \to A^C \times B^C \), where \( f \mapsto (\pi_1 \circ f, \pi_2 \circ f) \), where \( \pi_1, \pi_2 \) are the projections of the first and second elements of the pair. Then \( \varphi^{-1}: A^C \times B^C \to (A \times B)^C \), \( (f(c), g(c)) \mapsto (f, g)(c) \). Hence \( \varphi \) is also a bijection. This proves (8).
9. Let \( \varphi: A^n \to A^{\mathbb{N}_{< n}} \), where \( \varphi \) maps tuples to sequences while maintaining the order of elements, then \( \varphi \) is clearly a bijection, which proves (9).
10. Let \( \varphi: A^\infty \to A^\mathbb{N} \), where \( \varphi \) maps tuples to sequences while maintaining the order of elements, then \( \varphi \) is clearly a bijection, which proves (10). \( \boxed{\text{Q.E.D.}} \)
From Theorem 2, it can be seen that the disjoint union of two sets is analogous to the addition of natural numbers, and the Cartesian product of two sets is analogous to the multiplication of natural numbers. This serves as the foundation for the subsequent definitions of addition and multiplication of cardinalities.
Similarly, analogous to the ordering of natural numbers, we can also define an order on sets.
We define the order \(\preccurlyeq\) on sets as \[ \preccurlyeq \: \coloneq \{ (A, B) \mid \exists f(f: A \rightarrowtail B) \} \]
Let \(A\) and \(B\) be sets. It is easy to observe that the existence of an injective function from \(A\) to \(B\) is equivalent to the existence of a surjective function from \(B\) to \(A\). This result is trivial when \(A\) or \(B\) is the empty set, so we only consider the case where \(A\) and \(B\) are non-empty. If there exists an injection \(f: A \rightarrowtail B\), we can take \(a \in A\). Then the mapping \(f^{-1} \sqcup (B \setminus f(A)) \times \{a\}\) is a surjection from \(B\) to \(A\). Conversely, if there exists a surjection \(f: B \twoheadrightarrow A\), let \(\varphi\) be a choice function on the set family \(\left\{\{x \mid f(x)=a\} \mid a \in A\right\}\), then \(g: A \to B, \ a \mapsto \varphi(\{x \mid f(x)=a\})\) is an injection from \(A\) to \(B\).
If two sets \(A\), \(B\) satisfies the above ordering relation, we say that \(A\) precedes or is equinumerous to \(B\) (or \(B\) succeeds or is equinumerous to \(A\)), denoted as \(A \preccurlyeq B\) (or \(B \succcurlyeq A\)). Specially, if \(A \nsim B\), we say that \(A\) precedes \(B\) (or \(B\) succeeds \(A\)), denoted as \(A \prec B\) (or \(B \succ A\)).
The order \(\preccurlyeq\) on sets is a total order.
For any set \(A\), there exists the identity map \( \iota \) such that \( \iota: A \twoheadrightarrowtail A \). Therefore, \( A \preccurlyeq A \), which proves reflexivity.
Antisymmetry, known as Bernstein's theorem, has a more complicated proof. For any sets \(A\) and \(B\), if \( A \preccurlyeq B \) and \( B \preccurlyeq A \), then let \( f: A \rightarrowtail B \), \( g: B \rightarrowtail A \), and the sequence \( \{s_n\} \) satisfy \( s_0 = B \), \( s_1 = f(A) \), and \( s_{n+2} = f \circ g(s_n) \). Therefore, we have:
\[s_0 \supseteq s_1 \supseteq s_2 \wedge (s_n \supseteq s_{n+1} \rightarrow s_{n+2} \supseteq s_{n+3})\]
\[\Rightarrow \forall n \in \mathbb{N}\,(s_n \supseteq s_{n+1})\]
\begin{align*}
\Rightarrow s_0 &= \bigcap_{i=0}^{\infty} s_i \sqcup \bigcup_{2\, \nmid \,i} (s_i \setminus s_{i+1}) \sqcup \bigcup_{2\, \mid \,i} (s_i \setminus s_{i+1}) \\
s_1 &= \bigcap_{i=0}^{\infty} s_i \sqcup \bigcup_{2\, \nmid \,i} (s_i \setminus s_{i+1}) \sqcup \bigcup_{2\, \mid \,i} (s_{i+2} \setminus s_{i+3})
\end{align*}
\begin{align*}
f \circ g \left( \bigcup_{2\, \mid \,i} (s_i \setminus s_{i+1}) \right) &= \bigcup_{2\, \mid \,i} \left( f \circ g(s_i) \setminus f \circ g(s_{i+1}) \right)\\
&= \bigcup_{2\, \mid \,i} (s_{i+2} \setminus s_{i+3})
\end{align*}
\[\Rightarrow \bigcup_{2\, \nmid \,i} (s_i \setminus s_{i+1}) \sim \bigcup_{2\, \mid \,i} (s_{i+2} \setminus s_{i+3})\]
\[\Rightarrow B \sim s_0 \sim s_1 \sim A\]
This proves antisymmetry.
For any sets \(A\), \(B\), and \(C\), if \( A \preccurlyeq B \) and \( B \preccurlyeq C \), there exists \(f\), \(g\) such that \( f: A \rightarrowtail B \), \( g: B \rightarrowtail C \), and thus there exists \( h = f \circ g \) such that \( h: A \rightarrowtail C \). Therefore, \( A \preccurlyeq C \), which proves transitivity.
Next, we prove the law of trichotomy, which states that there must exist an injective function between any two sets. Let \(X\) and \(Y\) be two sets. When \(X = \emptyset\) or \(Y = \emptyset\), the theorem obviously holds. We only consider the case where \(X, Y \neq \emptyset\). Let
\[G \coloneq \{f \mid f: K \to Y, K \subseteq X\}\]
Then, we have
\[\exists x \in X \, \exists y \in Y \left(\{(x, y)\} \in G\right)\]
\[\Rightarrow G \neq \emptyset\]
\begin{align*}
&\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \,\exists f = \bigcup_{\alpha \in H} \alpha \,\forall x, y \in D_f\\
&\exists g, h \in H \, (x \in D_g \wedge y \in D_h)
\end{align*}
\begin{align*}
\Rightarrow &\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \,\exists f = \bigcup_{\alpha \in H} \alpha \\
&\forall (x, y \in D_f : f(x)=f(y)) \,\exists (g, h \in H: g \subseteq h) \, (x \in D_g \subseteq D_h \wedge y \in D_h)
\end{align*}
\begin{align*}
\Rightarrow &\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \,\exists f = \bigcup_{\alpha \in H} \alpha \\
&\forall (x, y \in D_f : f(x)=f(y)) \, (x = y)
\end{align*}
\[\Rightarrow \forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \,\exists f = \bigcup_{\alpha \in H} \alpha \, (f \in G)\]
\[\Rightarrow \forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \,\exists f \in G \, (f \text{ is an upper bound of } H)\]
\[\Rightarrow \exists h \in G \,\forall f \in G \, (\neg h \subsetneqq f) \quad \text{(*)}\]
We now assume that
\[\forall h \in G \, (\forall f \in G \, (\neg h \subsetneqq f) \to D_h \neq X \wedge R_h \neq Y)\]
\begin{align*}
\Rightarrow &\forall h \in G (\forall f \in G \, (\neg h \subsetneqq f) \to \exists a \in X \setminus D_h \, \exists b \in Y \setminus R_h \\
&\exists f=h \cup \{(a, b)\} \, (f \in G \wedge h \subsetneqq f))
\end{align*}
\[\Rightarrow \forall h \in G \left(\forall f \in G \, (\neg h \subsetneqq f) \to \exists f \in G \, (h \subsetneqq f)\right)\]
\[\Rightarrow \forall h \in G \, \exists f \in G \, (h \subsetneqq f)\]
\[\Rightarrow \bot\]
which results in a contradiction. Therefore, the assumption does not hold, and we conclude that
\[\exists h \in G \, (\forall f \in G \, (\neg h \subsetneqq f) \wedge (D_h = X \vee R_h = Y))\]
\[\Rightarrow \exists h \in G \, (D_h = X) \vee \exists h \in G \, (R_h = Y)\]
\[\Rightarrow \exists h \, (h: X \rightarrowtail Y \vee h: Y \rightarrowtail X)\]
This proves the law of trichotomy.
Note that the equation (*) uses Zorn's Lemma. Based on the four conditions above, we obtain that \( \preccurlyeq \) is a total order. \( \boxed{\text{Q.E.D.}} \)
The following are some properties of the order given in Definition 2.
Let \(A\), \(B\), \(C\) be sets, then: \begin{align*} &\text{1.}\ \ \ A \subseteq B \to A \preccurlyeq B \\ &\text{2.}\ \ \ A \preccurlyeq B \land A \cap C = B \cap C = \emptyset \to A \sqcup C \preccurlyeq B \sqcup C \\ &\text{3.}\ \ \ A \preccurlyeq B \to A \times C \preccurlyeq B \times C \\ &\text{4.}\ \ \ A \preccurlyeq B \to A^C \preccurlyeq B^C \\ &\text{5.}\ \ \ A \preccurlyeq B \to C^A \preccurlyeq C^B \\ &\text{6.}\ \ \ A \prec 2^A \end{align*}
1. Since \( A \subseteq B \), there exists the identity map \( \iota: A \rightarrowtail B \). Since \( \iota \) is injective, this proves (1).
2. Since \( A \preccurlyeq B \), there exists a function \(f\) such that \( f: A \rightarrowtail B \). Take the identity map \( \iota: C \twoheadrightarrowtail C \), then \( \varphi = f \sqcup \iota \) is an injective function from \( A \sqcup C \) to \( B \sqcup C \), which proves (2).
3. Since \( A \preccurlyeq B \), there exists a function \(f\) such that \( f: A \rightarrowtail B \). Let \( \varphi: A \times C \to B \times C \) be defined by \( (x, y) \mapsto (f(x), y) \), then \( \varphi \) is clearly injective, which proves (3).
4. If \( A \subseteq B \), it is evident that \( A^C \subseteq B^C \), because for every function \( f: C \to A \), we also have \( f: C \to B \). Since \( A \preccurlyeq B \), there exists a function \(f\) such that \( f: A \rightarrowtail B \). Therefore, we have \( A^C \sim f(A)^C \preccurlyeq B^C \), which proves (4).
5. We first prove that if \( A \subseteq B \), then \( C^A \preccurlyeq C^B \). This statement is clearly true for \( C = \emptyset \). Let \( A \subseteq B\) and \( C \neq \emptyset\), then there exists am element \( c \in C \). Thus, there exists a function \( \varphi: C^A \to C^B, f \mapsto f \sqcup (B \setminus A) \times \{c\} \). Then \( \varphi \) is clearly injective, we have \( A \subseteq B \to C^A \preccurlyeq C^B \). Next, let \( A \preccurlyeq B \), then there exists a function \( \psi: A \rightarrowtail B \). Therefore, we have \( C^A \sim C^{\psi(A)} \preccurlyeq C^B \), which proves (5).
6. Let the map \( \varphi: A \to 2^A \) be defined by \( a \mapsto \{a\} \). Clearly, \( \varphi \) is injective, so \( A \preccurlyeq 2^A \). Assume there exists a bijection \( \psi: A \to 2^A \). Let \( S \coloneq \{T \in A \mid T \notin \psi(T)\} \in 2^A \). If \( \psi^{-1}(S) \in S \), then \( \psi^{-1}(S) \notin S \), a contradiction; if \( \psi^{-1}(S) \notin S \), then \( \psi^{-1}(S) \in S \), also a contradiction.Therefore, there does not exist a bijection from \(A\) to \( 2^A \), and thus \( A \prec 2^A \), which proves (6). \( \boxed{\text{Q.E.D.}} \)
According to Theorem 4, we find that the ordering of sets is very similar to the ordering of natural numbers. In particular, based on Theorem 4(6), we have proven that there does not exist a set that strictly succeeds any other set.
Next, we will define countable and uncountable sets and introduce some important properties.
A set \(A\) is countable if and only if \(A \preccurlyeq \mathbb{N}\). If \(A\) is not countable, then \(A\) is called uncountable.
1. Any subset of a countable set is countable.
2. The image of a countable set under a function is countable.
3. The union of countably many countable sets is countable.
1. Let \(B\) be a countable set, and let \(A \subseteq B\). By Theorem 4(1), we have \(A \preccurlyeq B \preccurlyeq \mathbb{N}\), which proves (1).
2. For any countable set \(A\) and function \(f\), \(f: A \twoheadrightarrow f(A)\). Therefore, \(f(A) \preccurlyeq A \preccurlyeq \mathbb{N}\), which proves (2).
3. Assume \(\mathscr{A} \preccurlyeq \mathbb{N} \wedge \forall \alpha \in \mathscr{A} \, (\alpha \preccurlyeq \mathbb{N})\). According to Definition 2 we have
\[\exists f\in\mathscr{A}^\mathbb{N}\,(f: \mathbb{N} \twoheadrightarrow \mathscr{A})\]
\[\Leftrightarrow \exists f\in\mathscr{A}^\mathbb{N}\, \forall \alpha \in \mathscr{A}\,\exists n\in \mathbb{N}\,(\alpha = f(n))\]
Similarly,
\[\forall \alpha \in \mathscr{A} \,\exists f\in\alpha^\mathbb{N}\,(f: \mathbb{N} \twoheadrightarrow \alpha)\]
\[\Leftrightarrow \forall \alpha \in \mathscr{A}\,\exists f\in \left(\bigcup_{A \in \mathscr{A}} A\right)^\mathbb{N}\,\forall a\in\alpha\,\exists n\in \mathbb{N}\,(a=f(n))\]
\[\Leftrightarrow \exists F: \mathscr{A} \to \left(\bigcup_{A \in \mathscr{A}} A\right)^\mathbb{N}\,\forall \alpha \in \mathscr{A}\,\forall a\in\alpha\,\exists n\in \mathbb{N}\,(a=F(\alpha)(n))\]
Hence we have:
\[\forall a \in \bigcup_{A \in \mathscr{A}} A\,\exists\alpha \in \mathscr{A}\,(a\in\alpha)\]
\[\Rightarrow \exists f\in\mathscr{A}^\mathbb{N}\, \forall a \in \bigcup_{A \in \mathscr{A}} A\,\exists\alpha \in \mathscr{A}\,\exists m\in \mathbb{N}\,(a\in\alpha=f(m))\]
\[\Rightarrow \exists f\in\mathscr{A}^\mathbb{N}\, \forall a \in \bigcup_{A \in \mathscr{A}} A\,\exists m\in \mathbb{N}\,(a\in f(m))\]
\[\Rightarrow \exists F: \mathscr{A} \to \left(\bigcup_{A \in \mathscr{A}} A\right)^\mathbb{N}\,\exists f\in\mathscr{A}^\mathbb{N}\, \forall a \in \bigcup_{A \in \mathscr{A}} A\,\exists m\in \mathbb{N}\,\exists n\in \mathbb{N}\,(a=F(f(m))(n))\]
\begin{align*}
\Rightarrow \, &\exists F: \mathscr{A} \to \left(\bigcup_{A \in \mathscr{A}} A\right)^\mathbb{N}\,\exists f\in\mathscr{A}^\mathbb{N}\, \exists (\varphi: \varphi: \mathbb{N}^2 \to \bigcup_{A \in \mathscr{A}} A, \\
&(x,y)\mapsto F(f(x))(y))\,\forall a \in \bigcup_{A \in \mathscr{A}} A\,\exists m, n\in \mathbb{N}\,(a=\varphi(m,n))
\end{align*}
\[\Rightarrow \exists \varphi: \mathbb{N}^2 \to \bigcup_{A \in \mathscr{A}} A\,\forall a \in \bigcup_{A \in \mathscr{A}} A\,\exists m, n\in \mathbb{N}\,(a=\varphi(m,n))\]
\[\Rightarrow \exists \varphi\in\left(\bigcup_{A \in \mathscr{A}} A\right)^{\mathbb{N}^2}\,\left(\varphi: \mathbb{N}^2 \twoheadrightarrow \bigcup_{A \in \mathscr{A}} A\right)\]
\[\Rightarrow \bigcup_{A \in \mathscr{A}} A \preccurlyeq \mathbb{N}^2\]
Since \(f: \mathbb{N}^2 \to \mathbb{N}, \ (a, b) \mapsto 2^a 3^b\) is an injective function, we have \(\mathbb{N}^2 \preccurlyeq \mathbb{N}\). However, it is evident that \(\mathbb{N} \preccurlyeq \mathbb{N}^2\), so \(\mathbb{N}^2 \sim \mathbb{N}\). Therefore,
\[\bigcup_{A \in \mathscr{A}} A \preccurlyeq \mathbb{N}^2 \sim \mathbb{N}\]
which proves (3). \( \boxed{\text{Q.E.D.}} \)
In addition to countable and uncountable sets, we can also classify sets into two categories: finite sets and infinite sets. The concept of finite sets is quite intuitive, but here we will provide a rigorous definition of finite sets.
A set \(A\) is finite if and only if \(A \prec \mathbb{N}\). If \(A\) is not finite, then \(A\) is called infinite.
Clearly, all finite sets are countable sets. It is important to note that finite sets and infinite sets can be defined in different ways, and we will now explain that these definitions are equivalent.
Furthermore, due to the construction of the natural set \(\mathbb{N}\), each natural number \(n\) is also a set \(\mathbb{N}_{< n}\). To clarify, we will denote natural numbers as \(n\) when referring to them as numbers, and as \(\mathbb{N}_{< n}\) when referring to them as sets. However, the reader should recognize that these two forms are equal, i.e., \(n = \mathbb{N}_{< n}\).
The following propositions are equivalent:
1. \(A\) is an infinite set.
2. \(A\) contains a countably infinite subset.
3. \(A\) is equinumerous to the union of \(A\) with any countable set.
4. \(A\) is equinumerous to the union of \(A\) with some non-empty countable set that is disjoint from \(A\).
5. \(A\) is equinumerous to some proper subset of itself.
6. \(A\) is not equinumerous to any natural number.
(1) \(\Rightarrow\) (2). Since \(A \succcurlyeq \mathbb{N}\), there exists an injection \(f\) such that \(f: \mathbb{N} \rightarrowtail A\). Therefore, \(f(\mathbb{N}) \subseteq A\), and by Theorem 5(2), \(f(\mathbb{N}) \preccurlyeq \mathbb{N}\). Hence, \(f(\mathbb{N})\) is a countably infinite subset of \(A\).
(2) \(\Rightarrow\) (3). Let \(B \preccurlyeq \mathbb{N}\), \(C\) be a countably infinite subset of \(A\). Since \(B \setminus A \subseteq B\), we have \(B \setminus A \preccurlyeq B \preccurlyeq \mathbb{N}\). According to Theorem 5(3), \(C \preccurlyeq C \cup (B \setminus A) \preccurlyeq \mathbb{N} \sim C\). Hence, by antisymmetry, \(C \cup (B \setminus A) \sim C\). Therefore,
\[A = (A \setminus C) \sqcup C \sim (A \setminus C) \sqcup (C \cup (B \setminus A)) = A \cup B\]
(3) \(\Rightarrow\) (4). Obvious.
(4) \(\Rightarrow\) (5). Let \(B\) be a set satisfing \(\emptyset \neq B \preccurlyeq \mathbb{N}\) and \(A \sqcup B \sim A\). Let \(f: A \sqcup B \twoheadrightarrowtail A\). Then \(f(A \sqcup B) = f(A) \sqcup f(B) = A\). Therefore, \(f(A) = A \setminus f(B) \subsetneqq A\). Since \(f\) is a bijection from \(A\) to \(f(A)\), it follows that \(A \sim f(A) \sim A \setminus f(B) \subsetneqq A\).
(5) \(\Rightarrow\) (6). We first prove that no natural number is equinumerous to any of its proper subsets by induction. The case for \(\emptyset\) is vacuously true since \(\emptyset\) has no proper subsets. If \(\mathbb{N}_{< n}\) is not equinumerous to any of its proper subsets, then for the case of \(n + 1\), assume \(\exists S \subsetneqq \mathbb{N}_{< n+1} \, (\mathbb{N}_{< n+1} \sim S)\). Therefore,
\[\exists S \subseteq \mathbb{N}_{< n} \, (\mathbb{N}_{< n+1} \sim S) \vee \exists (S: S \setminus \{n\} \subsetneqq \mathbb{N}_{< n} \wedge n \in S)\,(\mathbb{N}_{< n+1} \sim S)\]
\begin{align*}
\Rightarrow \, &\exists S \subseteq \mathbb{N}_{< n} \, (\mathbb{N}_{< n+1} \sim S) \vee \exists (S: S \setminus \{n\} \subsetneqq \mathbb{N}_{< n} \wedge n \in S) \,\exists k \in \mathbb{N}_{< n} \setminus S \\
&\exists f: \mathbb{N}_{< n+1} \twoheadrightarrowtail S \,\exists \varphi=(f \setminus \{(f^{-1}(n), n)\}) \sqcup \{(f^{-1}(n), k)\} \,\exists T = \varphi(\mathbb{N}_{< n+1})\,(T \subseteq \mathbb{N}_{< n})
\end{align*}
\[\Rightarrow \exists S \subseteq \mathbb{N}_{< n} \,(\mathbb{N}_{< n+1} \sim S) \vee \exists T \subseteq \mathbb{N}_{< n} \,(\mathbb{N}_{< n+1} \sim T)\]
\[\Rightarrow \exists S \subseteq \mathbb{N}_{< n} \,(\mathbb{N}_{< n+1} \sim S)\]
\[\Rightarrow \exists S \subseteq \mathbb{N}_{< n} \,\exists f: \mathbb{N}_{< n+1} \twoheadrightarrowtail S \,(f(\mathbb{N}_{< n}) = S \setminus \{f(n)\} \subsetneqq \mathbb{N}_{< n})\]
\[\Rightarrow \exists S \subseteq \mathbb{N}_{< n} \,\exists f: \mathbb{N}_{< n+1} \twoheadrightarrowtail S \,\exists T = S \setminus \{f(n)\} \,\exists \varphi = f \restriction \mathbb{N}_{< n}\,(\varphi: \mathbb{N}_{< n} \twoheadrightarrowtail T \wedge T \subsetneqq \mathbb{N}_{< n})\]
\[\Rightarrow \exists T \subsetneqq \mathbb{N}_{< n} \,(\mathbb{N}_{< n} \sim T)\]
\[\Rightarrow \bot\]
Therefore, \(\mathbb{N}_{< n+1}\) is not equinumerous to any of its proper subsets. This completes the induction, proving that no natural number is equinumerous to any of its proper subsets.
Now, suppose \(B \subsetneqq A\) and \(A \sim B\). Assume there exists \(n \in \mathbb{N}\) such that \(A \sim \mathbb{N}_{< n}\). Then there exists a bijection \(f: A \twoheadrightarrowtail \mathbb{N}_{< n}\), implying \(\mathbb{N}_{< n} \sim A \sim B \sim f(B)\), but
\[f(B) = f(A \setminus (A \setminus B)) = \mathbb{N}_{< n} \setminus f(A \setminus B) \subsetneqq \mathbb{N}_{< n}\]
leading to a contradiction. Therefore, \(A\) is not equinumerous to any natural number.
(6) \(\Rightarrow\) (1). If \(A\) is not equinumerous to any natural number, then for any element \(a \in A\), \(A \setminus \{a\}\) is also not equinumerous to any natural number. For, if there exists a natural number \(n\) such that \(A \setminus \{a\} \sim \mathbb{N}_{< n}\), let \(f: \mathbb{N}_{< n} \twoheadrightarrowtail A \setminus \{a\}\). Then \(f \sqcup \{(n, a)\}: \mathbb{N}_{< n+1} \twoheadrightarrowtail A\), implying \(A \sim \mathbb{N}_{< n+1}\), leading to a contradiction. Hence, we can successively remove elements \(a_0\), \(a_1\), \(a_2\), ... from \(A\), forming a sequence \(\{a_n\}: \mathbb{N} \rightarrowtail A\), i.e., \(A \succcurlyeq \mathbb{N}\).
In conclusion, the above six propositions are equivalent. \( \boxed{\text{Q.E.D.}} \)
According to Theorem 6(6), every finite set has a natural number that is equinumerous to it. Clearly, this natural number is unique. Let \(A\) be a finite set. Without loss of generality, let \(m, n \in \mathbb{N}\) and \(m \leq n\). Assume \(\mathbb{N}_{< m} \sim A \sim \mathbb{N}_{< n}\). Since no natural number is equinumerous to its proper subset, \(\mathbb{N}_{< m}\) is not a proper subset of \(\mathbb{N}_{< n}\). However, \(\mathbb{N}_{< m} \subseteq \mathbb{N}_{< n}\), so \(\mathbb{N}_{< m} = \mathbb{N}_{< n}\), which is \(m = n\). This proves the uniqueness. This natural number is typically referred to as the number of elements in the finite set \(A\).
Next, we will derive some simple corollaries about finite sets. Typically, we denote the power set of \(A\) as \(2^A\), and the set of functions from \(A\) to \(B\) as \(B^A\). The following corollaries can explain the reason behind our use of these symbols.
Let \(A\), \(B\) be sets and \(m, n \in \mathbb{N}\). If \(A \sim \mathbb{N}_{< m}\), \(B \sim \mathbb{N}_{< n}\), then: \begin{align*} &\text{1.}\ \ \ A \cap B = \emptyset \to A \sqcup B \sim \mathbb{N}_{< m+n} \\ &\text{2.}\ \ \ A \times B \sim \mathbb{N}_{< mn} \\ &\text{3.}\ \ \ 2^A \sim \mathbb{N}_{< 2^m} \\ &\text{4.}\ \ \ B^A \sim \mathbb{N}_{< n^m} \end{align*}
1. Let \(f\) be a bijection from \(A\) to \(\mathbb{N}_{< m}\), and \(g\) be a bijection from \(B\) to \(\mathbb{N}_{< n}\). Then \(f \sqcup (g+m)\) is a bijection from \(A \sqcup B\) to \(\mathbb{N}_{< m+n}\). Therefore, \(A \sqcup B \sim \mathbb{N}_{< m+n}\), which proves (1).
2. Let \(f\) be a bijection from \(A\) to \(\mathbb{N}_{< m}\), and \(g\) be a bijection from \(B\) to \(\mathbb{N}_{< n}\). Then \(h: A \times B \to \mathbb{N}_{< mn}, \ (a, b) \mapsto nf(a) + g(b)\) is a bijection from \(A \times B\) to \(\mathbb{N}_{< mn}\). Therefore, \(A \times B \sim \mathbb{N}_{< mn}\), which proves (2).
3. Let \(S \subseteq A\). For each element of \(A\), the element is either in \(S\) or not in \(S\), so there are two choices. Since \(A\) has \(m\) elements, there are a total of \(2^m\) possible choices. Therefore, the total number of subsets of \(A\) is \(2^m\), i.e., \(2^A \sim \mathbb{N}_{< 2^m}\), which proves (3).
4. For each element of \(A\), there is a unique corresponding element in \(B\). There are n possible choices for such elements. Since \(A\) has \(m\) elements, the total number of possible mappings from \(A\) to \(B\) is \(n^m\). Therefore, \(B^A\) contains \(n^m\) elements, i.e., \(B^A \sim \mathbb{N}_{< n^m}\) , which proves (4). \( \boxed{\text{Q.E.D.}} \)
Next, we will discuss the properties of operations between infinite sets. Similar to the proof of trichotomy in Theorem 3, we will prove the following lemma.
Let \(A \succcurlyeq \mathbb{N}\) be an infinite set, then: \[A^2 \sim A\]
Let the set \(G \coloneq \{f \mid f: K \twoheadrightarrowtail K^2, K \subseteq A\}\). We first prove that \(G\) is non-empty. Since \(A \succcurlyeq \mathbb{N}\), according to Theorem 6(2), we have \[\exists K \subseteq A \, (K \sim \mathbb{N} \sim \mathbb{N}^2 \sim K^2)\] \[\Rightarrow \exists K \subseteq A \, \exists f \, (f: K \twoheadrightarrowtail K^2)\] \[\Rightarrow \exists f \, (f \in G)\] Therefore, \(G \neq \emptyset\). We will then prove that \((G, \subseteq)\) has a maximal element. Since \[\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \left(f: \bigcup_{\alpha \in H} D_\alpha \to \left(\bigcup_{\alpha \in H} D_\alpha \right)^2\right)\] \begin{align*} &\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \forall y \in \left(\bigcup_{\alpha \in H} D_\alpha \right)^2 \, \exists \alpha \in H \, \exists x \in D_\alpha \\ &\left(y = \alpha (x) = f(x)\right) \end{align*} \begin{align*} \Rightarrow \, &\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \forall y \in \left(\bigcup_{\alpha \in H} D_\alpha \right)^2 \, \exists x \in \bigcup_{\alpha \in H} D_\alpha \\ &\left(y = f(x)\right) \end{align*} \[\Rightarrow \forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \left(f: \bigcup_{\alpha \in H} D_\alpha \twoheadrightarrow \left(\bigcup_{\alpha \in H} D_\alpha \right)^2\right) \quad \text{(Eq. 1)}\] \begin{align*} &\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \forall \left(a, b \in \bigcup_{\alpha \in H} D_\alpha: f(a) = f(b)\right) \, \exists \alpha \in H \\ &\left(\alpha(a) = f(a) = f(b) = \alpha(b) \right) \end{align*} \[\Rightarrow \forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \forall \left(a, b \in \bigcup_{\alpha \in H} D_\alpha: f(a) = f(b)\right) \, (a = b)\] \[\Rightarrow \forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f = \bigcup_{\alpha \in H} \alpha \, \left(f: \bigcup_{\alpha \in H} D_\alpha \rightarrowtail \left(\bigcup_{\alpha \in H} D_\alpha \right)^2\right) \quad \text{(Eq. 2)}\] According to (1), (2), we have \[\forall (H \subseteq G: (H, \subseteq) \text{ is a totally ordered set}) \, \exists f \in G \, (f \text{ is an upper bound of } H)\] \[\Rightarrow \exists h \in G \,\forall f \in G \, (\neg h \subsetneqq f) \quad \text{(*)}\] We now assume that \[\exists h \in G \,\forall f \in G \, (\neg h \subsetneqq f \wedge A \setminus D_h \succcurlyeq \mathbb{N})\] \[\Rightarrow \exists h \in G \,\forall f \in G \, (\neg h \subsetneqq f \wedge \{F \mid F: K \twoheadrightarrowtail K^2, K \subseteq A \setminus D_h\} \neq \emptyset)\] \[\Rightarrow \exists h \in G \,\forall f \in G \, \exists \varphi \in \{F \mid F: K \twoheadrightarrowtail K^2, K \subseteq A \setminus D_h\} \, (\neg h \subsetneqq f \wedge h \subsetneqq h \sqcup \varphi)\] \[\Rightarrow \exists h \in G \, \left(\forall f \in G \, (\neg h \subsetneqq f ) \wedge \exists f \in G \, (h \subsetneqq f ) \right)\] \[\Rightarrow \bot\] which results in a contradiction. Therefore, the assumption does not hold, and we conclude that \[\exists h \in G \,\forall f \in G \, (\neg h \subsetneqq f \wedge A \setminus D_h \prec \mathbb{N})\] \[\Rightarrow \exists h \in G \, (A = (A \setminus D_h) \sqcup D_h \sim D_h \sim D_h^2 \sim A^2)\] \[\Rightarrow A \sim A^2\] which proves the theorem. Note that the equation (*) uses Zorn's Lemma. \( \boxed{\text{Q.E.D.}} \)
Based on the above lemma, we can obtain some important formulas regarding the comparison of infinite sets.
Let \(A, B \succcurlyeq \mathbb{N}\) be infinite sets, then: \begin{align*} &\text{1.}\ \ \ A \cup B \sim \max \{A, B\} \\ &\text{2.}\ \ \ A \times B \sim \max \{A, B\} \\ &\text{3.}\ \ \ A \succ B \to A \setminus B \sim A \\ &\text{4.}\ \ \ A^A \sim 2^A \end{align*}
1. Since
\begin{align*}
A \cup B &= (A \setminus B)\sqcup B \\
&\preccurlyeq \max \{A, B\} \times \{0\} \sqcup \max \{A, B\} \times \{1\} \\
&= \max \{A, B\} \times \{0, 1\} \\
&\preccurlyeq \left(\max \{A, B\}\right)^2 \sim \max \{A, B\}
\end{align*}
and
\[A \preccurlyeq A \cup B \wedge B \preccurlyeq A \cup B\]
\[\Rightarrow \max \{A, B\} \preccurlyeq A \cup B\]
by the antisymmetry, we get \(A \cup B \sim \max \{A, B\}\), which proves (1).
2. Since
\[A \times B \preccurlyeq \left(\max \{A, B\}\right)^2 \sim \max \{A, B\}\]
and
\[A \preccurlyeq A \times B \wedge B \preccurlyeq A \times B\]
\[\Rightarrow \max \{A, B\} \preccurlyeq A \times B\]
by the antisymmetry, we get \(A \times B \sim \max \{A, B\}\), which proves (2).
3. Let \(A \succ B\). Since
\begin{align*}
A &\sim A \cup B = (A \setminus B)\sqcup B \\
&\sim \max \{A \setminus B, B\} \sim A \setminus B
\end{align*}
which proves (3).
4. Since
\[A^A \preccurlyeq (2^A)^A \sim 2^{A^2} \sim 2^A\]
and
\[2^A \preccurlyeq A^A\]
by the antisymmetry, we get \(A^A \sim 2^A\), which proves (4). \( \boxed{\text{Q.E.D.}} \)
Let \(R \succcurlyeq \mathbb{N}\) be a ring. Let \(R[x]\), \(R(x)\) respectively represent the set of all polynomials and the set of all rational functions over \(R\). Then \(R \sim R[x] \sim R(x)\).
For any natural number \(n\), let \(R_n[x]\) represent the set of all polynomials over \(R\) with degree less than \(n\). Thus, it is evident that \[R[x] = \bigsqcup_{i=0}^{\infty} R_i[x]\] Clearly, any \(n\)-degree polynomial corresponds one-to-one with an \((n + 1)\)-tuple, i.e., \(R_n[x] \sim R^{n+1}\). Therefore, \[\bigsqcup_{i=0}^{\infty} R_i[x] \sim \bigsqcup_{i=0}^{\infty} R^{i+1}\] Furthermore, since any finite power of \(R\) is equinumerous to \(R\) (this can be derived by induction from Theorem 7(2)), it follows that \[R[x] \sim \bigsqcup_{i=0}^{\infty} R^{i+1} \sim \bigsqcup_{i=0}^{\infty} R \times \{i\} = R \times \mathbb{N} \sim R\] At the same time, if \(f\) maps the ordered pair \((p, q)\) in \((R[x])^2\) to \(\frac{p}{q}\), then \(f\) is a surjection from \((R[x])^2\) to \(R(x)\). Furthermore, since \(R[x] \subseteq R(x)\), it follows that \[R \sim R[x] \preccurlyeq R(x) \preccurlyeq (R[x])^2 \sim R^2 \sim R\] By antisymmetry, we obtain \(R[x] \sim R\). Thus, the corollary is completely proven. \( \boxed{\text{Q.E.D.}} \)
Finally, we shall define the concept of the continuum.
A set \(A\) is a continuum if and only if \(A \sim 2^\mathbb{N}\).
We will prove that the set of real numbers \(\mathbb{R}\) is a continuum. Consider all the real numbers in the interval \([0, 1)\), which can be uniquely written as binary decimals without a repeating tail of 1s. Define a function \(f\) from \([0, 1)\) to \(2^\mathbb{N}\), such that \(f\) maps a real number \(a\) to a set \(\{n\in\mathbb{N} \mid \text{the } (n+1) \text{-th binary bit of } a \text{ is } 1\}\). It is evident that \(f\) is a bijection from \([0, 1)\) to \(2^\mathbb{N} \setminus \{\mathbb{N}_{\ge n} \mid n\in \mathbb{N}\}\). Since \(\{\mathbb{N}_{\ge n} \mid n\in \mathbb{N}\} \sim \mathbb{N} \prec 2^\mathbb{N} \), according to Theorem 7(3), \(2^\mathbb{N} \sim 2^\mathbb{N} \setminus \{\mathbb{N}_{\ge n} \mid n\in \mathbb{N}\} \sim [0, 1)\). Also, since \(\tan(\pi x - \frac{1}{2})\) is a bijection from \((0, 1)\) to \(\mathbb{R}\), we have \( \mathbb{R} \sim (0, 1) \sim [0, 1) \). Therefore, \(\mathbb{R} \sim [0, 1) \sim 2^\mathbb{N}\) is a continuum.