I'm studying the proof given in Rosen's discrete mathematics for well-ordered induction.
THE PRINCIPLE OF WELL-ORDERED INDUCTION:
Suppose that S is a well-ordered set. The P(x) is true for all x $\in$ S, if
INDUCTIVE STEP: For every y $\in$ S, if P(x) is true for all x $\in$ S with x $\prec$ y, then P(y) is true.
Proof:
Suppose it is not the case that P(x) is true for all x $\in$ S. Then there is an element y $\in$ S such that P(y) is false. Consequently, the set A = {x $\in$ S | P(x) is false} is nonempty. Because S is well ordered, A has a least element a.
By the choice of a as a least element of A, we know that P(x) is true for all x $\in$ S with x $\prec$ a. <– (I couldn't understand how it gets this)
This implies by the inductive step P(a) is true. This contradiction shows that P(x) must be true for all x $\in$ S.
My question is : where does the sentence, "By the choice of a as a least element of A, we know that P(x) is true for all x $\in$ S with x $\prec$ a.", come from?
I mean if we want to prove
"The P(x) is true for all x $\in$ S, if for every y $\in$ S, if P(x) is true for all x $\in$ S with x $\prec$ y",
Why can the conclusion "The P(x) is true for all x $\in$ S" be used in the proof? I remember it's not valid to do so while proving something.
Best Answer
Part 1: Justifying the assertion you are asking about.
Note that $\mathbf{a}$ is the smallest element of the set $A$. $A$ is the collection of all elements of $S$ for which $P(\mathbf{x})$ is not true.
Suppose $\mathbf{x}\in S$. If $P(\mathbf{x})$ is false, then $\mathbf{x}\in A$, so that means that $\mathbf{a}\preceq\mathbf{x}$ (because $\mathbf{a}$ is the smallest element of $A$).
So: $P(\mathbf{x})$ is false $\implies$ $\mathbf{a}\preceq \mathbf{x}$.
The contrapositive is that if $\mathbf{x}\prec \mathbf{a}$, then $P(\mathbf{x})$ is true.
So: for all $\mathbf{x}\in S$, if $\mathbf{x}\prec\mathbf{a}$, then $P(\mathbf{x})$ is true.
Part 2: Rest of your question:
We are not assuming what we are trying to prove: we are assuming the opposite of what we are trying to prove: that there is at least one element of $S$ for which $P(\mathbf{x})$ is false. From that assumption, we conclude that the set $A$ is not empty, and so has a smallest element. The next thing we deduce from this is not that “every element $\mathbf{x}$ of $S$ satisfies $P(\mathbf{x})$”. What we deduce is that “every element $\mathbf{x}$ of $S$ is either greater than $\mathbf{a}$, or else $P(\mathbf{x})$ holds.”
We never assume “$P(\mathbf{x})$ is true for all $\mathbf{x}\in S$”.