Theorem $($Transfinite Induction and Construction$)$ (James Dugundji - 5.1, Page - 40)

Question

Let $W$ be a well ordered set, and let $Q \subset W$. If $[ W(x) \subset Q] \Rightarrow [ x \in Q]$ for each $x \in W$, then $Q = W$.

For each $a \in W$, the set $W(a) = \{x \in W; (x\prec a) \land (x\ne a)\}$ is the initial interval determined by a.

The proof given is Dugundji's book is the following.

Proof: The first element, $0$, of $W$ is in $Q$, since $\emptyset = W(0) \subset Q$, and evidently there can be no first among the elements not in $Q$.

Let $0$ be the first element of $W$, I can easily show that $0 \in Q$. Further I am not understanding what he wants to prove. Please help me. Thank you

Answer 1

Assume that $W\setminus Q\ne\emptyset$.

Since $W$ is well-ordered and $W\setminus Q$ is non-empty, there exists the smallest element $x=W\setminus Q$.

Can you explain why then $W(x)\subseteq Q$? Can you see how this leads to a contradiction?

---

BTW this is called induction on well-ordered set. See, for example, ProofWiki.

Answer 2

There are two forms of "transfinite induction" there's this form and then there's the "transfinite induction on the ordinals" form. Keep that in mind when learning this form. (Both forms use the same argument in their proof)