This post was translated from Korean by LLM (Kimi). The translation may contain errors or awkward sentences. The Korean original is the source of truth.
Review
Let us begin by briefly reviewing the key topics from the previous post. We constructed the natural numbers, then defined ordinal numbers and examined their properties. Well-ordering, though largely independent of ordinal numbers, was another topic we covered. A well-ordering is defined as follows.
Definition A total order \(R\) on a set \(A\) is a well-ordering if every non-empty subset \(X\) of \(A\) has a least element.
We also proved that every set can be well-ordered, and this proof relied on the Axiom of Choice.
The Axiom of Choice. Every set has a choice function.
Theorem (Zermelo) Every set \(A\) can be well-ordered.
Theorem (Zorn’s lemma) Every inductive set has a maximal element.
Of the results proved using these, the following theorem is the one we shall use.
Proposition Let \(A,B\) be two well-ordered sets. Then at least one of the following holds.
- There exists an order isomorphism from \(A\) to a segment of \(B\), or
- There exists an order isomorphism from \(B\) to a segment of \(A\).
Finally, we saw that ordinal numbers allow us to define the size of a set rigorously.
In this post, we define the size of a set in a somewhat less rigorous manner and introduce operations on them.
Basic Definitions
Let us begin. The cardinal of a set is a generalization of its size—that is, of the number of its elements. However, since we have not yet defined the natural numbers, we must adopt a different perspective. While we cannot define how large an arbitrary set is, we can define when two sets have the same size, as follows.
Definition 1 A set \(A\) is equipotent to a set \(B\) if there exists a bijection from \(A\) to \(B\).
Then
- For any set \(A\), \(\id_A\) is a bijection from \(A\) to \(A\).
- If there exists a bijection \(f:A\rightarrow B\) between sets \(A,B\), then its inverse \(f^{-1}:B\rightarrow A\) is a bijection from \(B\) to \(A\).
- The composition of two bijections is also a bijection.
Thus, the only condition in the definition of an equivalence relation that remains unsatisfied is for the above relation to be reflexive on some particular set \(U\); consequently, if we can resolve the problem that no universal set exists, we may regard this relation as an equivalence relation defined on a universal set.
Although this is not a rigorous solution, we shall proceed under the assumption that this problem has been resolved. (See: Wikipedia, Class)
Definition 2 A representative of the equivalence class of a set \(A\) is called the cardinal of \(A\), denoted by \(\card A\).
Since the empty set is unique, \(\card\emptyset\) is precisely \(\emptyset\). When dealing with cardinals, we denote this by \(\mathbf{0}\). All singletons, such as \(\{a\}\) and \(\{b\}\), are mutually equipotent, for \(\{(a,b)\}\) is a bijection from \(\{a\}\) to \(\{b\}\). Let us denote this cardinal by \(\mathbf{1}\). Although these are not yet natural numbers, we will soon endow cardinals with operations that allow us to regard them as natural numbers.
Before defining operations, let us first define an ordering relation between cardinals.
Definition 3 The relation among cardinals
\(\mathfrak{a}\) is equipotent to a subset of \(\mathfrak{b}\).
is an order relation, denoted by \(\mathfrak{a}\leq\mathfrak{b}\).
Of course, we have not yet verified that this relation is indeed an order relation. However, the only non-trivial part is antisymmetry.
Lemma 4 (Cantor-Bernstein) The relation \(\leq\) defined above is antisymmetric.
Proof
Let \(\mathfrak{a}\) and \(\mathfrak{b}\) be two cardinals satisfying \(\mathfrak{a}\leq\mathfrak{b}\) and \(\mathfrak{b}\leq\mathfrak{a}\).
If \(i\) is a bijection from \(\mathfrak{a}\) to a subset of \(\mathfrak{b}\), then \(i(\mathfrak{a})\subset\mathfrak{b}\) and \(\mathfrak{a}\) is equipotent to \(i(\mathfrak{a})\). Hence it suffices to show that a bijection exists between \(i(\mathfrak{a})\) and \(\mathfrak{b}\).
Since \(\mathfrak{b}\leq\mathfrak{a}\), there exists a bijection from \(\mathfrak{b}\) to a subset of \(\mathfrak{a}\), which may be regarded as an injection from \(\mathfrak{b}\) into \(\mathfrak{a}\). Since \(\mathfrak{a}\) is equipotent to \(i(\mathfrak{a})\), composing the bijection between them with the foregoing injection yields an injection from \(\mathfrak{b}\) into \(i(\mathfrak{a})\). Denote this by \(f\). Now let \(C_0=\mathfrak{b}\setminus i(\mathfrak{a})\), define \(C_{n+1}=f(C_n)\) inductively, and set \(C=\bigcup C_n\). We define \(h:\mathfrak{b}\rightarrow i(\mathfrak{a})\) by the formula
and show that it is a bijection from \(\mathfrak{b}\) to \(i(\mathfrak{a})\).
First, \(h\) is a function from \(\mathfrak{b}\) to \(i(\mathfrak{a})\). That \(h\) is well-defined is clear, and we need only verify that its target is \(i(\mathfrak{a})\). If \(x\in C\), then \(h(x)=f(x)\in i(\mathfrak{a})\), which is immediate. If \(x\not\in C\), then \(x\not\in C_0\), so \(x\not\in\mathfrak{b}\setminus i(\mathfrak{a})\); hence \(x\in i(\mathfrak{a})\) in this case as well.
Moreover, \(h\) is injective. If \(h(x)=h(y)\), then when \(x,y\in C\) we have \(f(x)=f(y)\), and since \(f\) is injective, \(x=y\). When \(x,y\not\in C\), clearly \(x=y\).
The non-trivial case is when one of them lies in \(C\) and the other does not. Suppose \(x\in C\) and \(y\not\in C\). Then \(x\in C_n\) for some \(n\), and in particular \(h(x)=f(x)\in C_{n+1}\subseteq C\), so \(h(x)\in C\). On the other hand, \(h(y)=y\), and by assumption \(y\not\in C\), contradicting \(h(x)=h(y)\). Thus \(x=y\) in all cases, and \(h\) is injective.
Finally, we show that \(h\) is surjective. Take any \(y\in i(\mathfrak{a})\). Either \(y\in C\) or \(y\not\in C\). If \(y\not\in C\), then \(h(y)=y\) by definition. If \(y\in C\), then \(y\in C_{n}\) for some \(n\geq 1\) (since \(y\in C_0=\mathfrak{b}\setminus i(\mathfrak{a})\) is impossible). Thus \(y\in f(C_{n-1})\), so there exists \(x\in C_{n-1}\) such that \(y=f(x)\). This \(x\) also lies in \(C\), whence \(h(x)=f(x)=y\). Therefore \(h\) is surjective.
Moreover, any set of cardinals is well-ordered.
Theorem 5 Any set \(A\) of cardinals has a least element.
Proof
Consider the set \(A=\bigcup_{\mathfrak{a}\in E}\mathfrak{a}\). Then every cardinal \(\mathfrak{a}\in E\) is a subset of \(A\).
By the well-ordering principle, there exists a well-ordering on this set; denote it by \(\leq\). Moreover, every subset of \(A\) is equipotent to a segment of \(A\) (Proposition in Review). Thus for every cardinal \(\mathfrak{a}\), the set of segments of \(A\) equipotent to it is non-empty, and by the well-orderedness of \(A^*\), there exists a least element. Denote this element by \(\varphi(\mathfrak{a})\).
If we can show that \(\mathfrak{a}\leq\mathfrak{b}\) is equivalent to \(\varphi(\mathfrak{a})\subset\varphi(\mathfrak{b})\), then the proof will be complete by the well-orderedness of \(A\).
First, the latter condition clearly implies the former. Conversely, suppose \(\mathfrak{a}\leq\mathfrak{b}\); that is, \(\mathfrak{a}\) is equipotent to a subset of \(\mathfrak{b}=\varphi(\mathfrak{b})\) (equality holds as cardinals). If \(\varphi(\mathfrak{b})\subset\varphi(\mathfrak{a})\) and \(\varphi(\mathfrak{a})\neq\varphi(\mathfrak{b})\), then some segment of \(\varphi(\mathfrak{b})\) would be equipotent to \(\mathfrak{a}\), contradicting the definition of \(\varphi(\mathfrak{b})\). Therefore the two conditions are equivalent.
References
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기