Exercises for Week 3

1. Prove the following statements.
   1. If there is a surjection $X \to Y$ and $X$ is well-ordered, then $Y \precsim X$ (meaning that there is an injection $Y \to X$.)
   2. If $Y \precsim X$ and $Y \ne \emptyset$ then there is a surjection $X \to Y$.
2. Prove that if $x$ is a finite set, then every injection $x \to x$ is a surjection.
3. Let $\alpha, \beta$ be ordinals.
   1. Define $\lt_\text{sum}$ on the disjoint union $(\{0\} \times \alpha) \cup (\{1\} \times \beta)$ by saying
      • $(0,\gamma) \lt_\text{sum} (0,\gamma')$ for all $\gamma,\gamma' \lt \alpha$ with $\gamma \lt \gamma'$,
      • $(1,\gamma) \lt_\text{sum} (1,\gamma')$ for all $\gamma,\gamma' \lt \beta$ with $\gamma \lt \gamma'$, and
      • $(0,\gamma) \lt_\text{sum} (1,\gamma')$ for all $\gamma \lt \alpha$ and $\gamma' \lt \beta$.
      Prove that $\lt_\text{sum}$ is a well-ordering of order type $\alpha + \beta$.
   2. Define $\lt_\text{lex}$ on the Cartesian product $\alpha \times \beta$ by saying $(\gamma,\delta) \lt (\gamma',\delta')$ if
      • $\gamma \lt \gamma'$, or
      • $\gamma = \gamma'$ and $\delta \lt \delta'$.
      Prove that $\lt_\text{lex}$ is a well-ordering of order type $\beta \cdot \alpha$.
4. Prove that if $\beta$ is an ordinal and $A \subset \beta$, then $\text{otp}(A;\in)\le \beta$.