Math 135: Solutions to Homework Set # 11

1. (page 178, # 4)

Proof. We check first that $R$ defines a linear order.

(irreflexivity)

Let $x \in P$ then $f(x) = f(x)$ while $x \not < x$ so that $x \not R x$.

(transitivity)

Let $x, y, z \in P$. Suppose $xRy$ and $yRz$. So we have $f(x) \leq f(y)$ and $f(y) \leq f(z)$ which implies by transitivity of $\leq$ that $f(x) \leq f(z)$. If $f(x) < f(z)$, then we have $xRz$. If $f(x) = f(z)$, then as $f(x) \leq f(y) \leq f(z) = f(x)$, we have $f(x) = f(y) = f(z)$ so that by the definition of $R$ we have $x < y$ and $y < z$. Thus, $x < z$ and by definition of $R$ we have $xRz$.

(trichotomy)

Let $x$ and $y \in P$. By the trichotomy for $<$ we have $f(x) < f(y)$, $f(y) < f(x)$ or $f(x) = f(y)$. If the first case holds, we have $xRy$; while if the second case holds, we have $y R x$. In the last case, we note that the $f(x) = f(y) \to (x R y \leftrightarrow x < y)$ so that the trichotomy for $<$ is equivalent to the trichotomy for $R$ when restricted to this case.

Now, we show that this ordering is a well-ordering. Let $A \subseteq P$ be nonempty. Let $B := f {[\![}A {\,]\!\!]}\subseteq \omega$. Then $B$ is a nonempty set of natural numbers and therefore has a least element $b$. By definition of $B$, the set $(f \upharpoonright A)^{-1} \{ b \}$ is a nonempty subset of $P \subseteq \omega$ so that it, too, has a least element which we call $a$. This $a$ is the $R$-least element of $A$ for if $x \in A$ is any element of $A$, then $f(a) = b \leq f(x)$ as $b$ is the least element of $B$ and if $b = f(a) = f(x)$ we have $a \leq x$ as $a$ is the least element of $(f \upharpoonright A)^{-1} \{ b \}$.

The ordering $(P,R)$ looks lke case (d). $\qedsymbol$

2 (page 178 # 7)

(a)

$$F(0) = C \cup \bigcup \bigcup {\rm rng}(F \upharpoonright 0)$$

$$= C \cup \bigcup \bigcup {\rm rng}({\varnothing})$$

$$= C$$

$$F(1) = C \cup \bigcup \bigcup {\rm rng}(F \upharpoonright 1)$$

$$= C \cup \bigcup \bigcup \{ F(0) \}$$

$$= C \cup \bigcup \bigcup \{ C \}$$

$$= C \cup \bigcup C$$

$$F(2) = C \cup \bigcup \bigcup {\rm rng}(F \upharpoonright 2)$$

$$= C \cup \bigcup \bigcup \{ F(0), F(1) \}$$

$$= C \cup \bigcup (C \cup (C \cup \bigcup C))$$

$$= C \cup \bigcup C \cup \bigcup \bigcup C$$

Naïvely,

$$F(n) = \bigcup_{i=0}^n (\stackrel{n \text{ times }}{\overbrace{\bigcup \cdots \bigcup}} C)$$

(b)

From the definition of $F(n^+)$ we have

$$F(n^+) = C \cup \bigcup \bigcup {\rm rng}(F \upharpoonright n^+)$$

$$= C \cup \bigcup \bigcup ( {\rm rng}(F \upharpoonright n) \cup \{ F(n) \} )$$

$$\supseteq \bigcup F(n)$$

Thus, if $a \in F(n)$ and $x \in a$ we have $x \in F(n^+)$ so that $a \subseteq F(n^+)$.

(c)

As $C = F(0)$ we have by part (b) that $C \subseteq F(1) \subseteq \bigcup {\rm rng}F = \overline{C}$.

Now, suppose that $x \in \overline{C}$. By definition, there is some $n \in \omega$ with $x \in F(n)$. By part (b) we have $x \subseteq F(n^+) \subseteq \overline{C}$. Thus, $\overline{C}$ is a transitive superset of $C$.

3 (page 187, # 13)

Proof. Let $(X,<)$ and $(Y,<)$ be two well-ordered structures. Suppose that $f:X \to Y$ and $g:X \to Y$ are two order-isomorphisms. If $f \neq g$, then the set $\{ x \in X \ \vert \ f(x) \neq g(x) \}$ is nonempty and therefore has a least element, $a$. Without loss of generality, we may assume that $f(a) < g(a)$. As $g$ is an isomorphism (and, in particular, surjective) there is some $b \in X$ with $g(b) = f(a) < g(a)$. As $g$ preserves order, we must have $b < a$. But by the minimality of $a$ with $g(a) \neq f(a)$, we have $f(b) = g(b) = f(a)$ contradicting injectivity for $f$. Thus, $f = g$. $\qedsymbol$

4 (page 187, # 14)

Proof. As we took $S$ to be the range of $F$, necessarily $F$ is surjective onto $S$. For injectivity, it suffices to show that $F$ preserves order.

Let $a < b$ be elements of $A$. Let $x \in F(a)$. By definition of $F(a)$, we have $x \leq a < b$ so that $x \in F(b)$ as well. That is, $F(a) \subseteq F(b)$. As $b \in F(b) \setminus F(a)$ we actually have $F(a) \subset F(b)$ as desired. $\qedsymbol$

5 (page 195, # 18)

Proof. We know in general for any set $C$ that $\bigcup C$ is the least upper bound of $C$ with respect to $\subseteq$. That is, $(\forall x \in C) [x \subseteq \bigcup C]$ and if $B$ is any other set with $(\forall x \in C) [x \subseteq B]$, then $\bigcup C \subseteq B$.

For ordinals $\alpha$ and $\beta$ we know $\alpha \subseteq \beta \leftrightarrow (\alpha \in \beta$    or $\alpha = \beta)$. Thus, $\bigcup S$ is an ordinal and is the least upper bound of $S$ with respect to $\in$.

If $S$ has no greatest element, then its least upper bound cannot be an element. That is, $\bigcup S \notin S$. Moreover, $\bigcup S$ cannot be the successor of some ordinal $\beta$ for if $\beta$ were a bound to $S$ we would contradict minimality of $\bigcup S$ and if it is not a bound to $S$, then there would be some $\alpha \in S$ with $\beta \in \alpha \subseteq \bigcup S = \beta^+$ implying that $\bigcup S \in S$.

If $S$ has a greatest element, then that greatest element is the least upper bound, $\bigcup S$. $\qedsymbol$

19 (page 195 # 19)

We prove a slightly more general statement:

Proposition: If $(A_1,<_1)$ are $(A_2,<_2)$ are linearly ordered structures and $A_1$ and $A_2$ have the same finite cardinality, then they are order isomorphic.

To prove the proposition, we need a lemma.

Lemma: Let $(A,<)$ be a finite nonempty linearly ordered set. Then $A$ has a least element.

Proof. We prove this result by induction on the cardinality of $A$. If the cardinality is one, then it is clear that the unique element of $A$ is the least element. If the cardinality of $A$ is $n^+$ for some $n \geq 1$, then write $A = \{ a \} \cup A'$ for some subset $A' \subseteq A$ with $A' \approx n$. The restriction of $<$ to $A'$ is a linear ordering so that by the inductive hypothesis, there is a least element $b \in A'$. By the trichotomy (as $a \notin A'$) we have $a < b$ or $b < a$. In the first case, $a$ is the least element of $A$ as for any $x \in A$ either $x = a$ or $x \in A'$ and $a < b \leq x$. In the other case, $b$ is the least element as for $x \in A$ we have either $x = a > b$ or $x \in A'$ and $x \geq b$. $\qedsymbol$

We are now in a position to prove the proposition.

Proof. We prove this result by induction on the cardinality of $A_1$. When this cardinality is zero, the results is immediate as $A_1 = <_1 = A_2 = <_2 = {\varnothing}$.

If $A_1 \approx n^+$, then for $i = 1$ or $2$ write $A_i = \{ a_i \} \cup A_i'$ where $a_i$ is the $<_i$-least element of $A_i$ (given by the lemma) and $A_i' \approx n$.

By the inductive hypothesis, there is an order isomorphism $g:(A_1', <_1 \upharpoonright A_1') \to (A_2', <_2 \upharpoonright A_2')$. Set $f := \{ \langle a_1, a_2 \rangle \} \cup g$. As $a_1 \notin A_1'$, $f$ is a function. For $x <_1 y$ in $A_1$ we see that necessarily $y \in A_1'$ so that $f(y) = g(y) \in A_2'$. If $x \in A_1'$ as well we have $f(x) = g(x) <_2 g(y) = f(y)$. Otherwise, $x = a_1$ so that $f(a_1) = a_2 <_2 f(y)$. In either case, we see that $f$ preserves the ordering and is thus injective. As any injective function from a set of size $n+$ to a set of size $n^+$ is bijective, $f$ is an order isomorphism.

$\qedsymbol$

7 (page 200, # 24)

Proof. Let $\alpha$ be an ordinal. By Hartog's theorem, there is an ordinal $\beta$ with $\beta \not \preceq \alpha$. Let $\kappa$ be the least ordinal with this property. Then $\kappa$ is a cardinal for if $\gamma \in \kappa$, then by minmality of $\kappa$ we would have $\alpha \succeq \gamma \approx \kappa$ contradicting the fact that $\kappa \not \preceq \alpha$. By the trichotomy for inclusion amongst ordinals, $\alpha \subset \kappa$ or $\kappa \subseteq \alpha$. The latter cannot happen as it would imply $\kappa \preceq \alpha$. Thus, $\alpha \subset \kappa$ which implies that $\alpha \in \kappa$ (so, is less than $\kappa$ as an ordinal). $\qedsymbol$

8 (page 207, # 33)

Proof. We show by induction on $\alpha \in {\mathbf O}{\mathbf N}$ that $V_\alpha \cap D \subseteq B$.

For $\alpha = 0$, this inclusion is obvious as $V_0 \cap D = {\varnothing}\cap D = {\varnothing}\subseteq B$.

For $\alpha = \beta^+$, assuming that $V_\beta \cap D \subseteq B$, we note that if $x \in (V_\alpha \cap D)$, then as $V_{\beta^+} = {\mathcal P}V_\beta$ by definition, we have $x \subseteq V_\beta$ and $x \subseteq D$ as $D$ is transitive. Thus, $x \subseteq (V_\beta \cap D) \subseteq B$ (by the inductive hypothesis). By the hypothesis on the relation between $D$ and $B$, we have $x \in B$. As $x$ was arbitrary in $V_\alpha \cap D$, we have $V_\alpha \cap D \subseteq B$.

Finally, for $\alpha = \lambda$ a limit ordinal, we have

$$V_\lambda \cap D = (\bigcup_{\beta < \lambda} V_\beta) \cap D V_\lambda$$

$$= \bigcup_{\beta < \lambda} (V_\beta \cap D)$$

$$\subseteq B$$

Thus, our claim is proven. As every set is grounded, if $x \in D$ then for some $\alpha \in {\mathbf O}{\mathbf N}$ we have $x \in V_\alpha$ so that $x \in (V_\alpha \cap D) \subseteq B$. Therefore, $D \subseteq B$. $\qedsymbol$