$$ \text{For any two well-ordered set} \,\, U, W \,\, \text{either} \,\, U < W \,\, \text{or}\,\, W < U \,\, \text{or} \,\, U \cong W.$$ I was self-reading a textbook on algebra by Alexey L. Gorodentsev, And this exercise was proposed after defining well ordered sets and transfinite induction, the problem is it never did any example on how to do transfinite induction, and I am unable to proceed in it. I initially try to fix one of the set say W, and try to induct on elements of $U$, but, I was not able to proceed.
Asked
Active
Viewed 59 times
1 Answers
2
For reasons made clear below, start by assuming that $W\not<U$. We want to define $f\colon U\to W$ recursively. That is, for $u\in U$, we want to define a value $f(u)\in W$ and may use that we have already defined $f(x)$ for all $x\in U$ with $x<u$. A priori, it might happen that $A_u:=\{\,f(x)\mid x\in U, x<u\,\}$ is already all of $W$. But then $f^{-1}$ maps $W$ to a proper initial segment $\{\,x\in U\mid x<u\,\}$ of $U$, i.e., $W<U$, contrary to our initial assumption. Hence $W\setminus A_u$ is non-empty and we can define $f(u)=\min(W\setminus A_u)$.
The map $f\colon U\to W$ defined recursively this way is either onto and then witnesses $U\cong W$, or is not onto and then witnesses that $U$ corresponds to a proper initial segment of $W$, i.e., $U<W$.
Hagen von Eitzen
- 374,180