Set Theory

\(L\) is a chain: For any two elements \(a, b\) in \(L\), consider the subset \(\{ a, b \} \subseteq L\).

\(L\) is finite: \(L\) has a top element \(t_0\) and a bottom element \(b_0\). If \(L \setminus \{ t_0, b_0 \} \neq \emptyset\) , then it also has a top element \(t_1\) and a bottom element \(b_1\), and so on. Suppose \(L\) is infinite, then the process goes forever and we have an infinite chain \(b_0 \preceq b_1 \preceq \dots \) (similar for top elements) that does not have a top element, which is a contradiction.

Non-emptiness: Every equivalent \(\bar{x}\) at least contains \(x\). Disjointness: By the previous lemma. Union: easy.

Converse: easy.

Reflexivity: Identity. Symmetry: Inverse. Transitivity: Composition.

\(f(x) = 2x\) for \(x > 0\) and \(-(1 + 2x)\) for \(x \leq 0\).

Let \(A = U_{i \in I} A_{i}\), where \(A_{i}\) and \(I\) are countable. Suppose \(I\) is countably infinite, we can reindex the union using \(\mathbb{N} \), i.e., \(A = \cup _{i=1} ^{\infty} A_{n}\). Since each \(A_{n}\) is countable, it can be expresssed as \(A_{n} = \{ A_{n m} \}_{m=1} ^{\infty}\). Then, we can enumerate the union as \(A = \{ a_{11}, a_{12}, a_{21}, a_{31}, a_{22}, \dots \}\). In case there are duplicates, we discard all but the first occurrence.

Find a countable union of countable set to express \(\mathbb{Q} \). E.g., \(\mathbb{Q} = \cup _{n=1}^{\infty} \{ \frac{m}{n} | m \in \mathbb{Z} \}\).

Basic idea: write the target set as countable union of countable sets.

Let \(S = \{ f(x): \sum_{k=1}^{n} a_{k} x ^{k}, a_{k} \in \mathbb{Z}, \text{ some } a_{k} \neq 0\) be the set of all such polynomials. Let \(T\) be the set of all algebraic numbers.

For each \(f \in S\), denote by \(T(f) = \{ c \in \mathbb{R} : f(c) = 0 \}\) the set of roots of \(f\). Let \(S_{n} = \{ f \in S: \deg (f) = n \}\). Then, \(S = \cup _{n=1} ^{\infty} S_{n}\). Let \(S_{n, l} = \{ f \in S_{n}: \| f \| \gets l\}\), where \(\| f \| = \sum_{k=1}^{n} \| a_{k} \|\). Then for any finite \(n, l\), \(S_{n, l}\) is finite. And we have \(S_{n} = \cup _{l=1} ^{\infty} S_{n, l}\).

Thus, \(S_{n}\) is countable. And \(S\) is countable. Finally, \(T = \cup _{f \in S} T(f)\) is countable.

First prove that the subset \(S\) of real numbers between \(0\) and \(1\) is uncountable. Then, as the supset, \(\mathbb{R} \) is also uncountable.

Suppose \(S\) is countable, i.e., \(S = \{ a_{n} \}_{n=1} ^{\infty}\). We claim that there exists \(b \in S\) s.t. \(b\) does not appear in this enumeration.

Consider expressing numbers in \(S\) using infinite decimals. For the special cases where a decimal ending with infinite 9’s equals to a decimal ending with infinite 0’s, we always take the latter one. Now, for any \(n\), set the \(n\)-th digit of \(b\) to 1 if the \(n\)-th digit of the decimal expression of \(a_{n}\) is 0, and to 0 otherwise. Then, \(b \neq a_{n}\) for all \(n\).

\(\star\) Suppose a sujective map \(f: A \to \mathcal{P}(A)\) exist, we want to show the contradiction that \(\exists B \in \mathcal{P}(A), \nexists b \in A, f(b) = B\).

A tricky construction (by Cantor): Let \(B = \{ a \in A : a \notin f(A) \}\). This basically divides \(A\) into two categories, those map to a set including themselves and those do not. One can verify \(B\) is a valid choice.

How to think of this construction? Think of this weaker condition: \(B\) is a set such that (1) every \(f(b)\), where \(b \in A\), just covers a proper (strict) subset of \(B\), and (2) the covers form a partition of \(B\). Then, considering any \(C \in \mathcal{P}(A)\), we can find that \(\{ c \in C: f(c) = C \}\) (pretending \(A\) is “larger” than \(\mathcal{P}(A)\)) forms a partition of \(B\).

An evident injective map \(g: A \to \mathcal{P}(A)\): For any \(a\), \(g(a) = \{ a \}\).

Firstly, applying the previous theorem to \(2 ^{d}\) and so on, we have \(2 ^{d} < 2 ^{2 ^{d}}\). By \(\prec \implies \preceq\) and the transitivity of \(\preceq\), this implies \(d_{i} \preceq d_{j}\) for any \(i < j\).

Then, we want to rule out \(d_{i} = d_{j}\). Suppose \(d_{i} = d_{j} = 2 ^{d_{j-1}}\), then we have \(d_{j-1} < 2 ^{d_{j-1}} = d_{i}\). Thus, it suffices to prove \(d_{i} < d_{j-1}\). This can be done inductively.

Consider applying \(f\) and \(f ^{-1}\) (if possible) to elements in \(A\) repeatedly.

First, let’s look at the case where \(A\) is finite: Starting from any \(a \in A\), we obtain a sequence \(a, f(a), f(f(a)), \dots \). By injectivity, it is easy to show that it eventually goes back to \(a\) after a finite number of steps (i.e., \(f ^{n}(a) = a\)). This is called a cycle. If we keep doing with starting with an unseen element, we can get disjoint cycles covering \(f(A)\) (but not necessarily \(A\)).

Now, broaden the context to infinite \(A\): For any \(a \in A\), there are several cases:

• If \(a \in f(A)\): Apply \(f\) and \(f ^{-1}\) (if possible) repeatedly to get \(\dots , f ^{-1}(f ^{-1}(a)), f ^{-1}(a), a, f(a), f (f(a)), \dots \)
  • If the applications in both direction can go forever without any repetition, then this is called a bilateral infinite cycle.
  • If there is ever a repetition, it boils down to a finite cycle.
  • If we cannot no longer apply \(f ^{-}\), then this becomes the following case:
• If \(a \notin f(A)\): Could apply \(f\) repeatedly but not \(f ^{-1}\) to get \(a, f(a), f(f(a)), \dots \).
  • If it goes forever without any repetition, then it is called a unilateral infinite cycle.
  • Actually, there must not be a repetition (if any, the first must be \(a\)), because this violates \(a \notin f(A)\).

Clearly, \(A\) is partitioned into disjoint finite cycles, bilateral cycles, and unilateral cycles. Let’s denote by \(D\) (the set of elements in) all the finite cycles and bilateral infinite cycles and by \(E\) all the unilateral infinite cycles. Then, \(A = D \sqcup E\) and \(f(A) = f(D) \sqcup f(E) = D \sqcup (E \setminus \text{the initial elements})\).

Then, construct a bijection \(g: A \to C\): We consider assign values by cycles. If we use \(f\) on some subset of \(A\), we don’t need to worry about the injectivity of that part. However, we have to cover entire \(C\).

• For unilateral cycle with an initial element \(\in C\): Better not to set \(g = f\), because the initial element \(\in C\) is not mapped to. We set \(g = \) the identity map.
• For unilateral cycle with an initial element \(\notin C\): Set \(g = f\).
• For \(D\): Any bijection between \(D\) and \(D\). E.g., the identity map or \(f\) (rigorous verification needed).

It can be easily checked that \(g\) is bijective.

Proof sketch:

1. Let \(L := \{ (A_{i}, B_{i}, f_{i}) : A_{i} \subset A, B_{i} \subset B, f_{i}: A_{i} \to B_{j} \text{ is bijective} \}\). Define \((A_{i}, B_{j}, f_{i}) \preceq (A_{j}, B_{j}, f_{j})\) iff \(A_{i} \subset A_{j}\), \(B_{i} \subset B_{j}\), and \(f_{i} = f_{j} |_{A_{i}}\). Show that \(L\) is a poset.

2. Show that any chain in \(L\) has an upper bound. By Zorn’s Lemma, \(L\) contains a maximal element.

   Proof: For any chain \(\{ (A_{i}, B_{i}, f_{i}) : i \in I \} \subset L\), we construct an upper bound in the followings: Let \(A_0 = \cup _{i \in I} A_{i}, B_{0} = \cup _{i\in I} B_{i}\). For every \(a \in A_0\), \(\exists A_{i}\) s.t. \(a \in A_{i}\). In this case, set \(f(a) = f_{i}(a)\). We can check that (1) \(f_0\) is well defined by the property of chain, (2) \(f_0\) is bijective, and (3) \((A_0, B_0, f_0)\) is indeed an upper bound.

3. Let \((A ^{*}, B ^{*}, f ^{*})\) be a maximal element. Show that either \(A ^{*} = A\) or \(B ^{*} = B\). Then, we have either an injection from \(A\) into \(B ^{*} \subset B\) or an injection from \(B\) into \(A ^{*} \subset A\), which concludes the proof.

   Proof: Suppose not, then there exists \(a \in A \setminus A ^{*}, b \in B \setminus B ^{*}\). We can construct a bijection \(g: A ^{*} \cup \{ a \} \to B ^{*} \cup \{ b \}\) by \(g(x) = f ^{*}(x)\) for \(x \in A ^{*}\) and \(g(x) = b\) for \(x = a\). Then, \((A ^{*} \cup \{ a \}, B ^{*} \cup \{ b \}, g)\) dominates \((A ^{*}, B ^{*}, f ^{*})\).

Let \(I \subsetneq C\) be an ideal that is not all of \(C\). Let \(a\) be the least element of \(I ^{C}\).

We claim \(I = S(a)\). If \(x \prec a\), then \(x \in I\) for if \(x \in I ^{C}\) we could contradict minimality of \(a\). Thus, \(S(a) \subset I\). Conversely, if \(x \in I\) then \(x \prec a\) for if \(a \preceq x\) then this would imply \(a \in I\). Thus, \(I \subset S(a)\).

We prove the contrapositive. If \(C\) is not well-ordered, by definition, then it contains an infinite descending sequence \(a_1 \succ a_2 \succ a_3 \succ \dots \). Consider the segment \(S(a_1) = \{ x \in C: x \prec a_1 \}\). \(S(a_1)\) itself has no minimal element and thus is not well-ordered. Thus, the contrapositive is true.

Suppose on the contrary that the well-ordered \(C\) is order-isomorphic to the segment \(S(a)\), \(a \in C\), via \(f: C \to S(a)\). Then, for any \(c \in C\), \(f(c) \in S(a)\), implying \(f(c) \prec a\). Specially, \(f(a) \prec a\). By the order-perserving property of \(f\), we have \(a \succ f(a) \succ f(f(a)) \succ \dots \). Thus, we find an infinite descending sequence in \(C\), which contradicts the well-ordering of \(C\).

Alternative: Let \(T := \{ x \in C: f(x) \prec x \} \neq \emptyset\). Since \(C\) is well-ordered, \(T \subset C\) must have a least element, say \(b\). As an element in \(T\), \(b\) satisfies \(f(b) \prec b\). Since \(f\) is order-preserving, this implies \(f(f(b)) \prec f(b)\). Thus, \(f(b) \in T\). However, \(b\) is the minimal element, so this is a contradiction.

Since we only utilize the property that any non-empty subset in \(C\) has a least element, the same proof with \(C\) replaced with a non-empty subset still applies.

Prove the contrapositive: Suppose \(A \neq C\), let \(x \in C \setminus A\) be the least element. Then, by minimality of \(x\), \(S(x) = \{ y \in C : y \prec x \} \subset A\), but \(x \notin A\).

Suppose on the contrary that both statements fail. Call an element \(a \in A\) good if \(\exists b \in B\) such that \(S(a) \cong S(b)\) via some order isomorphism. By Thm. 1, for a good element \(a\), the \(b\) is unique. Let \(I\) be the set of all good elements in \(A\). By the uniqueness of the corresponding \(b\), we can define a map \(f: I \to B\) by \(f(a) = b\).

Then, we check

• \(I\) is an ideal in \(A\).

  Suppose \(x \in I\), \(y \in A\), and \(y \preceq x\). Then, \(\exists b \in B\) such that \(S(x) \overset{\phi}{\cong} S(b)\) for some \(\phi\). Consider \(S(y) = \{ z \in A: z \prec y \} \subset S(x)\). For any \(a \in A\), \(a \in S(y) \iff a \prec y \iff \phi(a) \preceq \phi(y)\) by \(\phi\) being order-preserving. Note that \(\phi(S(x)) \subset S(b)\), so \(\phi(y) \prec b\) and \(S(\phi(y)) \prec S(b)\). It is easy to show that \(\phi|_{S(y)}: S(y) \to \phi(S(y))\) is an order-isomorphism. Then, \(y\) is a good element. Thus, \(I\) is an ideal.

• \(f\) is injective: Definition + Thm. 1.

• \(f\) is order-preseving:

  Assume \(a_1, a_2 \in I\), \(a_1 \preceq a_2\), \(b_1 = f(a_1)\), \(b_2 = f(a_2)\). First show that there exists an order-surjection \(: S(b_2) \to S(b_1)\) by showing an order-surjection \(: S(a_2) \to S(a_1)\). Then, disprove \(b_2 \prec b_1\), which leads to an order-isomorphism \(: S(b_1) \to S(b_1)\).

• Let \(J\) be the image of \(f\), i.e., \(f(I)\), then \(J\) is an ideal in \(B\). Then, \(I \overset{f}{\cong} J\):

  Let \(x \in J, y \in B, y \preceq x\). There exists a unique \(a \in I\) s.t. \(f(a) = x\), \(S(a) \cong_{\phi} S(x)\). Consider \(\phi ^{-1}(y)\).

By the assumption, \(I \neq A\) and \(J \neq B\). Let \(x\) be the least element in \(I ^{C}\) and \(J\) be the least element in \(J ^{C}\). Since \(x\) is the least element in \(I ^{C}\), we have \(S(x) \subset I\). On the other hand, for any \(\hat{x} \in I\), \(S(\hat{x}) \overset{\phi}{\cong} S(\hat{y})\) for some \(\hat{y}\). If \(x \prec \hat{x}\), we have \(x \in S(\hat{x})\) and \(S(x) \overset{\phi}{\cong} S(\phi(\hat{y}))\), which contradicts with \(x\) not being a good element. Thus, \(I \subset S(x)\) and \(I = S(x)\). Similarly, we have \(S(y) = J\).

We know that \(S(x) \overset{f}{\cong} S(y)\), so \(x\) is a good element, contradicting with \(x \notin I\).

Let \(L := \{ (A_{i}, \preceq_{i}) : A_{i} \subset A, A_{i} \neq \emptyset, (A_{i}, \preceq_{i}) \text{ is well-ordered} \}\). The subscript in \(\prec_{i}\) emphasizes that elements in \(L\) are not only distinguished by the sets but also by the orders.

E.g., all singletons, \((\{ a \}, )\) for \(a \in A\), are in \(L\) with no choice of ordering. All two-elements subsets of \(A\), say \(\{ a, b \}\), appear in \(L\) twice as \(B_1 = (\{ a, b \}, \prec_{1}), a \prec_{1} b\) and \(B_2 = (\{ a, b \}, \prec_{2}), b \prec_{2} a\), and so on. A finite subsets of \(A\) with \(n\) elements appear precisely \(n!\) times in \(L\).

We define \(\preceq\) on \(L\) as \((A_{i}, \preceq_{i}) \preceq (A_{j}, \preceq_{j})\) iff (1) \(\prec_{i}\) is the restriction of \(\preceq_{j}\) to \(A_{i}\) and (2) \(A_{i}\) is an ideal in \((A_{j}, \preceq_{j})\) and .

We claim that every chain in \(L\) possesses an upper bound. Let \((\{ (B_{i}, \preceq_{i}) \}, \preceq)\) be a chain in \(L\). We may natural exmaine whether \(B = \cup _{i} B_{i}\) equipped with some order can be the upper bound of the chain in \(L\). We have to

• Define an order \(\hat{\preceq}\) on \(B\) s.t. \(\preceq_{i}\)’s are restrictions of \(\hat{\preceq}\).

  Let \(x, y \in B, x \neq y\). It is easy to see that \(x, y \in B_{i}\) for some \(i\). Since \(B_{i}\) itself is a chain (well-ordered), exactly one of \(x \prec_{i} y\) and \(y \prec_{i} x\) holds. We set \(\hat{\prec}\) to be \(\prec_{i}\) on the comparison of \(x\) and \(y\). This is well-defined because \(\{ (B_{i}, \preceq_{i}) \}\) is a chain.

• Show that \(B_{i}\) is an ideal in \((B, \hat{\preceq})\):

  Let \(x \in B_{i}, y \in B, y \hat{\preceq} x\). \(y \in B_{j}\) for some \(j\). If \(j \leq i\), then \(y \in B_{j} \subset B_{i}\). If \(j > i\), by definition of \(\preceq\), \(B_{i}\) is an ideal in \((B_{j}, \preceq_{j})\). Then, \(y \in B_{j}, y \preceq_{j} x \implies y \in B_{i}\). Thus, \(B_{i}\) is an ideal in \((B, \hat{\preceq})\).

• Show that \((B, \hat{\preceq}) \in L\), i.e., it is a well-ordered set.

  By Thm. 1, it suffices to show that

  • It is a chain.

    First we prove that it is a poset. (1) Reflexivity is trivial. (2) Transitivity: If \(x \hat{\preceq} y\) and \(y \hat{\preceq} z\), then this will present in a single \((B_{i}, \preceq_{i})\). By the transitivity of \(\preceq_{i}\) there, \(x \preceq_{i} z\), and hence \(x \preceq z\). (3) Anti-symmetry: Similar.

    Similarly, for any \(x, y \in B\), they will present in a single \(B_{i}\), and since \(B_{i}\) is a chain, they are comparable by \(\preceq_{i}\) and hence by \(\preceq\).

  • Every segment \(S(x), x \in B\) is well-ordered. TODO

Suppose the opposite. Then by Thm. 1, there exist an infinite descending sequence \(d_1 \succ d_2 \succ \dots \). Let \(D_{i}\) be a set with \(o(D_{i}) = d_{i}\). By Axiom. 1, \(D_{i}\) equipped with some order is well-ordered. Applying Thm. 1 to \(D_{i}\) and \(D_1\), in view of \(d_1 \succ d_{i}\), it must be the case that \(D_{i}\) is order-isomorphic to a segment (since not the entire \(D_1\)) in \(D_1\), say \(S(b_{i})\). Then, we have \(o(S(b_{i})) = d_{i} \succ d_{i+1} = o(S(b_{i+1}))\). If \(b_{i} \preceq b_{i+1}\), then \(S(b_{i}) \subset S(b_{i+1})\) and \(o(S(b_{i})) \preceq o(S(b_{i+1}))\), which is a contradiction (with the natural ordering of cardinals). Thus, \(b_{i} \succ b_{i+1}\) (by the order on \(D_{i}\)) and we find an infinite descending sequence in \(D_1\) which violates the well-ordering of \(D_{1}\).

Reflexivity is obvious.

• Transitivity: Let well-ordered sets \(A, B, C\) have the ordinal \(\alpha, \beta, \gamma\), resp. Assume \(\alpha \preceq \beta\) and \(\beta \preceq \gamma\). Then, \(A\) is order-iso. to \(I_{B}\) via some \(\phi\) and \(B\) is order-iso. to \(I_{C}\) via some \(\psi\). Clearly, \(\psi|_{I_{B}} \circ \phi\) is an order-iso. from \(A\) to \(\psi(I_{B})\). We want to show that \(\psi(I_{B})\) is an ideal in \(C\).

  Let \(x \in \psi(I_{B}) \subset I_{C}\), then there is a unique \(b_{x} \in I_{B}\) with \(\psi(b_{x}) = x\). For any \(y \in C\) with \(y \preceq x\), we have \(y \in I_{C}\) (ideal). Thus, there is a unique \(b_{y} \in B\) with \(\psi(b_{y}) = y\). Additionally, \(b_{y} \preceq b_{x}\) (order-preserving), so \(b_{y} \in I_{B}\) (ideal), and hence \(y \in \psi(I_{B})\).

• Antisymmetry: If \(\alpha \leq \beta\) and \(\beta \leq \alpha\), by transitivity, then \(\alpha \leq \alpha\). This means that \(A\) is order-isomorphic to one of its ideal. From Thm. 1, we know that the only possibility is \(\alpha = \alpha\).

Let \(A\) be a well-ordered set with ordinal-number \(\alpha\). Show that the map \(\beta \to b\), where \(b\) satisfies that \(S(b)\) has ordinal number \(\beta\), is an order-isomorphism \(\{ \beta: \beta < \alpha \} \to A\).