Exercise 10.10

Proof. Let $J_0=\left\{x\in J\mid P(x)\right\}$. We show that $J_0$ is inductive. So consider any $\alpha \in J$ and suppose that $S_{\alpha }\subset J_0$. Then, for any $x\in S_{\alpha }$ we have that $x\in J_0$ so that $P(x)$. It then follows that $P(\alpha )$ is also true since $x$ was arbitrary, and so $\alpha \in J_0$. Since $\alpha \in J$ was arbitrary, this shows that $J_0$ is inductive. It then follows from Exercise 10.7 that $J_0=J$. So consider any $\beta \in J$ so that also $\beta \in J_0$ and hence $P(\beta )$ is true. Since $\beta$ was arbitrary, this shows the desired result. □

Proof. First, suppose that the domains of $h$ and $k$ are sets $H$ and $K$ where each is either a section of $J$ or $J$ itself. Since this is the case, we can assume without loss of generality that $H\subset K$ and so $H$ is exactly the domain common to both $h$ and $k$. Now suppose that the hypothesis we are trying to prove is not true so that there is an $x$ in both domains (i.e. $x\in H$) where $h(x)\ne k(x)$. We can also assume that $x$ is the smallest such element since $H\subset J$ and $J$ are well-ordered. It then clearly follows that $S_x\subset H$ is a section of $J$ and that $h(y)=k(y)$ for all $y\in S_x$. From this, we clearly have that $h(S_x)=k(S_x)$. But then we have

since both $h$ and $k$ satisfy $\text{(∗)}$ and $x$ is in the domain of both. This contradicts the supposition that $h(x)\ne k(x)$ so that it must be that no such $x$ exists and hence $h$ and $k$ are the same in their common domain as desired. □

Proof. Suppose that $h:S_{\alpha }\to C$ is such a function satisfying $\text{(∗)}$. Now let ${\overline{S}}_{\alpha }=S_{\alpha }\cup \left\{\alpha \right\}$ and we define $k:{\overline{S}}_{\alpha }\to C$ as follows. For any $x\in {\overline{S}}_{\alpha }$ set

We note that clearly $S_{\alpha }$ and $\left\{\alpha \right\}$ are disjoint so that this is unambiguous. We also note that $h$ is not surjective onto $C$ since $S_{\alpha }$ is a section of $J$, and hence $C-h(S_{\alpha })\ne \varnothing$ and so has a smallest element since $C$ is well-ordered.

Now we show that $k$ satisfies $\text{(∗)}$. First, clearly $h(S_x)=k(S_x)$ for any $x\le \alpha$ since $k(y)=h(y)$ by definition for any $y\in S_x\subset S_{\alpha }$. Now consider any $x\in {\overline{S}}_{\alpha }$. If $x=\alpha$ then by definition we have

On the other hand, if $x\in S_{\alpha }$ then $x<\alpha$ so that

since $h$ satisfies $\text{(∗)}$. Therefore, since $x$ was arbitrary, this shows that $k$ also satisfies $\text{(∗)}$. □

Proof. Let

which we claim is the function we seek.

First, we show that $k$ is actually a function from ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in K}{S}_{\alpha }$ to $C$. So consider any $x$ in the domain of $k$. Suppose that $(x,a)$ and $(x,b)$ are both in $k$ so that there are $\alpha$ and $\beta$ in $K$ where $(x,a)\in h_{\alpha }$ and $(x,b)\in h_{\beta }$. Since $h_{\alpha }$ and $h_{\beta }$ both satisfy $\text{(∗)}$, it follows from part (a) that $a=h_{\alpha }(x)=h_{\beta }(x)=b$ since clearly $x$ is in the domain of both. This shows that $k$ is indeed a function since $(x,a)$ and $(x,b)$ were arbitrary. Also clearly the domain of $k$ is ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in K}{S}_{\alpha }$ since, for any $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in K}{S}_{\alpha }$, we have that there is an $\alpha \in K$ where $x\in S_{\alpha }$. Hence $x$ is in the domain of $h_{\alpha }$ and so in the domain of $k$. In the other direction, clearly, if $x$ is in the domain of $k$ then it is in the domain of $h_{\alpha }$ for some $\alpha \in K$. Since this domain is $S_{\alpha }$, clearly $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in K}{S}_{\alpha }$. Lastly, obviously, the range of $k$ can be $C$ since this is the range of every $h_{\alpha }$.

Now we show that $k$ satisfies $\text{(∗)}$. So consider any $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in K}{S}_{\alpha }$ so that $x\in S_{\alpha }$ for some $\alpha \in K$. Clearly we have that $k(y)=h_{\alpha }(y)$ for every $y\in S_{\alpha }$ since $h_{\alpha }\subset k$. It then immediately follows that $k(x)=h(x)$ and $k(S_x)=h_{\alpha }(S_x)$ since $S_x\subset S_{\alpha }$. Then, since $h_{\alpha }$ satisfies $\text{(∗)}$, we have

Since $x$ was arbitrary, this shows that $k$ satisfies $\text{(∗)}$ as desired. □

Proof. Consider any $\beta \in J$ and suppose that, for every $x\in S_{\beta }$, there is a function $h_x:S_x\to C$ satisfying $\text{(∗)}$. Now, if $\beta$ has an immediate predecessor $\alpha$ then we claim that $S_{\beta }=S_{\alpha }\cup \left\{\alpha \right\}$. First if $x\in S_{\beta }$ then $x<\beta$ so that $x\le \alpha$ since $\alpha$ is the immediate predecessor of $\beta$. If $x<\alpha$ then $x\in S_{\alpha }$ and if $x=\alpha$ then $x\in \left\{\alpha \right\}$. Hence in either case we have that $x\in S_{\alpha }\cup \left\{\alpha \right\}$. Now suppose that $x\in S_{\alpha }\cup \left\{\alpha \right\}$. If $x\in S_{\alpha }$ then $x<\alpha <\beta$ so that $s\in S_{\beta }$. On the other hand if $x\in \left\{\alpha \right\}$ then $x=\alpha <\beta$ so that again $x\in S_{\beta }$. Thus we have shown that $S_{\beta }\subset S_{\alpha }\cup \left\{\alpha \right\}$ and $S_{\alpha }\cup \left\{\alpha \right\}\subset S_{\beta }$ so that $S_{\beta }=S_{\alpha }\cup \left\{\alpha \right\}$. Since $\alpha \in S_{\beta }$ it follows that there is an $h_{\alpha }:S_{\alpha }\to C$ that satisfies $\text{(∗)}$. Then, by part (b), we have that there is an $h_{\beta }:S_{\beta }=S_{\alpha }\cup \left\{\alpha \right\}\to C$ that also satisfies $\text{(∗)}$.

If $\beta$ does not have an immediate predecessor then we claim that $S_{\beta }={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\beta }{S}_{\gamma }$. So consider any $x\in S_{\beta }$ so that $x<\beta$. Since $x$ cannot be the immediate predecessor of $\beta$, there must be an $\alpha$ where $x<\alpha <\beta$. Then $x\in S_{\alpha }$ so that, since $\alpha <\beta$, clearly $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\beta }{S}_{\gamma }$. Now suppose that $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\beta }{S}_{\gamma }$ so that there is an $\alpha <\beta$ where $x\in S_{\alpha }$. Then clearly $x<\alpha <\beta$ so that also $x\in S_{\beta }$. Thus we have shown that $S_{\beta }\subset {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\beta }{S}_{\gamma }$ and ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\beta }{S}_{\gamma }\subset S_{\beta }$ so that $S_{\beta }={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\beta }{S}_{\gamma }$. Now, clearly $S_{\beta }$ is a subset of $J$ where there is an $h_x:S_x\to C$ satisfying $\text{(∗)}$ for every $x\in S_{\beta }$. Then it follows from what was shown in part (c) that there is a function $h_{\beta }$ from ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <S_{\beta }}{S}_{\gamma }={\bigcup }_{\gamma <\beta }{S}_{\gamma }=S_{\beta }$ to $C$ that satisfies $\text{(∗)}$.

Therefore, in either case, we have shown that there is an $h_{\beta }:S_{\beta }\to C$ that satisfies $\text{(∗)}$. The desired result then follows by transfinite induction. □

Proof. First, suppose that $J$ has no largest element. Then we claim that $J={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }$. For any $x\in J$ there must be a $y\in J$ where $x<y$ since $x$ cannot be the greatest element of $J$. Hence $x\in S_y$ so that also clearly ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }$. Then, for any $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }$, there is an $\alpha \in J$ where $x\in S_{\alpha }$. Clearly, $S_{\alpha }\subset J$ so that $x\in J$ also. Hence $J\subset {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }$ and ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }\subset J$ so that $J={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }$. Since we know from part (d) that there is an $h_{\alpha }:S_{\alpha }\to C$ that satisfies $\text{(∗)}$ for every $\alpha \in J$, it follows from part (c) that there is a function $h$ from ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in J}{S}_{\alpha }=J$ to $C$ that satisfies $\text{(∗)}$.

If $J$ does have a largest element $\beta$ then clearly $J=S_{\beta }\cup \left\{\beta \right\}$. Since we know that there is an $h_{\beta }:S_{\beta }\to C$ that satisfies $\text{(∗)}$ by part (d), it follows from part (b) that there is a function $h$ from $S_{\beta }\cup \left\{\beta \right\}=J$ to $C$ that satisfies $\text{(∗)}$. Hence the desired function $h$ exists in both cases. part (a) also clearly shows that this function is unique. □