I dont understand induction on well-orders

Question

Question: (Induction on well-orders) Suppose < is a well-order on A. Suppose $\phi(x)$ is a formula such that for every y $\in A$, if $\phi(x)$ holds for all $x<y$, then $\phi(y)$ holds for all x $\in A$ .

Proof: Suppose towards a contradiction that $\neg\phi(x)$ holds for some x $\in A$. The set $\{x \in A : \neg\phi(x)\} $ is a nonempty subset of A, so it has a $< -$ least element y $\in A$ . Then $\phi(x)$ holds for all $x < y$ but $\phi(y)$ fails, contrary to assumption.

I don't really understand the proof. Why is it that $\phi(x)$ holds for all $x < y$ but $\phi(y)$ fails?

Answer 1

Line your classmates and look for the first one that isn't wearing a green shirt. Say it was the fifth person in the line. Do you see why the first four people were wearing a green shirt?

Now, suppose that you already knew that if everyone before you were wearing a green shirt, then you must be wearing a green shirt as well, then the fifth person in line, whom we knew was the first one not wearing green, would satisfy the premise: all the predecessors, from the first to the fourth, were wearing green. So by the property we assumed, it must be that person no. five is also wearing green.

But now, the fifth person both wears and doesn't wear a green shirt. That's impossible!

Answer 2

First, your statement of the induction principle is wrong. It should be

Suppose $<$ is a well-order on $A$. Suppose $\phi(x)$ is a formula such that for every $y\in A$, if $\phi(x)$ holds for all $x<y$, then $\phi(y)$ holds. Then $\phi(x)$ holds for all $x\in A$.

Second, note generally that for any formula $\psi$ and any $z\in A$, $\psi(z)$ fails (in other words, is false) if and only if $\lnot\psi(z)$ holds (in other words, is true).

Now in the proof, write $B=\{\,x\in A\mid\lnot\phi(x)\,\}$. Then $\phi(y)$ fails since $\lnot\phi(y)$ holds, since $y\in B$. And $\phi(x)$ holds for all $x<y$ since $y$ is least in $B$--that is, there is no $x<y$ for which $\lnot\phi(x)$ holds.