1 Prove Fact 3.3

(a)

If \(x\) is an ordinal and \(y\in x\), then \(y\) is an ordinal and \(y = \operatorname{\mathsf{pred}}\left(x,\in,y\right)\).

By definition of an ordinal, \(x\) is transitive and \((x,\in)\) is a well ordering. First observe \(y\subseteq x\) because \(y\in x\) and \(x\) is transitive.

\(y\) is transitive

Let \(z\in y\subseteq x\). Since \(z\in x\) and \(x\) is transitive \(z\subseteq x\). Let \(w\in z\subseteq x\), by \(\in\) being a linear order on \(x\) and transitivity \(w\in y\). Therefore \(z\subseteq y\).

\((y,\in)\) is a well ordering

Let \(z\subseteq y\), \(z\ne 0\), then \(z\) is also a nonempty subset of \(x\), and since \((x,\in)\) is well ordered \(z\) contains a \(\in\)-least element.

\(y = \operatorname{\mathsf{pred}}\left(x,\in,y\right)\).

Let \(z \in y \subseteq x\), we can see that \(y\subseteq \operatorname{\mathsf{pred}}\left(x,\in,y\right)\). Let \(z \in \operatorname{\mathsf{pred}}\left(x,\in,y\right)\), that is \(z\in x, z\in y\), we are also done.\(\square\)

(b)

If \(x,y\) are ordinals and \((x,\in)\cong (y,\in)\), then \(x = y\).

Let \(f: x\to y\) witness the isomorphism. It suffices to show that \(z = f(z)\) for all \(z\in x\). Suppose the result fails, then we collect the set \[ S = \left\{z\in x: f(z) \ne z \right\} \] which is not empty by our assumption. Let \(z\) be the \(\in\)-least member of \(S\).

By part (a), \(z = \operatorname{\mathsf{pred}}\left(x,\in,z\right)\), and because \(z\) is minimal in \(S\), for all \(w\in z\), \(f(w) = w\). So the \(f\)-image of \(z\) is just \(z\). On the other hand \(f(z) = \operatorname{\mathsf{pred}}\left(y,\in,f(z)\right)\) is also the image of \(z\), so \(z = f(z)\) which is a contradiction. \(\square\)

(c)

If \(x,y\) are ordinals, then exactly one of the following holds: \(x=y, x\in y, y\in x\).

By Theorem 2.11 exactly one of the following holds.

1. \((x,\in)\cong (y,\in)\)

   • Apply (b) to get \(x = y\).

2. for some \(z\in y\), \((\operatorname{\mathsf{pred}}\left(y,\in,z\right),\in) \cong (x,\in)\)

   • Apply (a) to see that \((z,\in)\cong (x,\in)\), applying (b) \(x = z\), and \(x\in y\) follows.

3. for some \(z\in x\), \((\operatorname{\mathsf{pred}}\left(x,\in,z\right),\in) \cong (y,\in)\)

   • Similar to 2. \(\square\)

(d)

If \(C\) is a non empty set of ordinals, then there exists \(x\in C\) such that \(\forall y\in C\left( y=x \lor x\in y \right)\).

Suppose for a contradiction \[ \forall x\in C\exists y\in C \left(y\ne x \land x\notin y\right). \] Then applying the trichotomy in part (c) we have for all \(x\in C\), there exists \(y\in C\) such that \(y\in x\), this allows us to find an infinite descending chain of members of \(x\), which contradicts \(x\) being an ordinal.

2

Suppose \((L,\prec)\) is a linear ordering such that for every \(X\subseteq L\), \((X,\prec)\) is isomorphic to an initial segment of \((L,\prec)\). Show that \((L, \prec)\) is a well ordering.

First consider \(0\subseteq L\), let \(m\in L\) such that \((0,\prec) \cong \operatorname{\mathsf{pred}}\left(L,\prec,m\right)\). We can see that \(m\) is the \(\prec\)-least member of \(L\).

Let \(X\subseteq L\), since \((X,\prec)\) is isomorphic to an initial segment of \((L,\prec)\) which necessarily contains \(m\), \(X\) also has a \(\prec\)-least element and this shows \((L,\prec)\) is a well ordering. \(\square\)

3

Suppose \(X\) is an uncountable set and \(\prec_1, \prec_2\) are two well orderings on \(X\). Show that there is an uncountable \(Y\subseteq X\) such that \(\prec_1,\prec_2\) agree on \(Y\).

Without loss of generality we can only consider the case in which \(\operatorname{type}(X,\prec_1) = \omega_1\) (by only considering the \(\prec_1\)-initial segment of \(X\) otherwise, and \((X,\prec_2)\) will still be a well order). Now let \(Z\) be the \(\prec_2\)-initial segment of \(X\) such that \(\operatorname{type}(Z,\prec_2) = \omega_1\). Define \[ \mathcal{F} = \left\{Y\subseteq Z: \left(\forall a,b\in Y\right)\left(a\prec_1 b \iff a\prec_2 b\right) \right\} \] \(\mathcal{F}\) is non-empty (otherwise one of the orderings will fail to be a well order) and it is clear that \(\mathcal{F}\) has finite character. By Teichmüller-Tukey (AC) every \(W\in \mathcal{F}\) is contained in a maximal \(M\in\mathcal{F}\). Suppose the result fails and let \(Y\in\mathcal{F}\) be maximal, then \(Y\) is at most countable.

Note that \(\operatorname{type}(Z,\prec_1) = \omega_1\) still, let \[ Y_1 = \left\{z\in Z: \left(\exists y\in Y\right)\left(z \preccurlyeq_1 y\right)\right\} \] since no element of \(\omega_1\) has uncountably many predecessors, \(|Y_1| \leq \omega_0\). Define \(Y_2\) analogously. Let \(w \in Z\setminus\left(Y_1\cup Y_2\right)\), the set is not empty since \(Y_1\cup Y_2\) is only countable. Note that \(w\) satisfies \[\left(\forall y\in Y\right)\left(y\prec_1 w\right) \land \left(\forall y\in Y\right)\left(y\prec_2 w\right),\] which means \(Y\cup\left\{w\right\} \in \mathcal{F}\), contradicting maximality of \(Y\). \(\square\)