Can every statement that can be proved using the well-ordering principle be proved using weak mathematical induction?

Question

The following is problem 30 of chapter 4.4 of Discrete Mathematics with Applications, 3rd ed. by Susanna Epp:

Prove that if a statement can be proved by the well-ordering principle, then it can be proved by ordinary mathematical induction.

I am not sure how to answer this and could not find the answer online.

Interestingly, this problem appears to have been replaced by a problem asking to prove that weak mathematical induction implies the well-ordering principle in later editions of the book.

Edit: Clarification

I am asking for an answer to the problem in the textbook. I am not asking about the equivalence of the well-ordering principle (WOP) and weak mathematical induction (MI). In other words, if you can write a proof by WOP for a statement, can you also write a proof by MI for the statement that doesn't use WOP?

My meaning may be made clearer by considering the converse of the problem: prove that if a statement can be proved by MI, then it can be proved by WOP (this is problem 29 of the textbook). This is true because we can construct a proof by WOP from a proof by MI as follows: take the proofs for the base case and inductive step from the proof by MI, then assume to the contradiction that the set $S=\{n>=a:\neg{}P(n)\}$ is nonempty, then use WOP to arrive at a contradiction. This forms a complete proof of the original statement that uses WOP without ever using MI.

The above example shows that the converse is simple because a proof by MI can be easily converted to a proof by WOP. Can a proof by WOP be converted to a proof by MI? An example where this might not be true is Bézout's identity; Bézout's identity can be proven by WOP, but how would you prove it by MI?

Perhaps this is merely a problem with the wording of the textbook's problem. But I still hope to get an answer to the problem at face value (unaltered). I would appreciate any clarification.

Answer 1

Property $WOP$ is Well-Ordering Principle.
Property $MI$ is Mathematical Induction.

(Exercise 1) Statement $S$ is given with a Proof , hence we are given $WOP \implies S$.
We are asked to show that $MI \implies S$.

(Exercise 2) Statement $S$ is given with a Proof , hence we are given $MI \implies S$.
We are asked to show that $WOP \implies S$.

(Exercise 3) We are asked to show that $WOP \iff MI$.

While (Exercise 1) is the OP Query in the text book $3^{rd}$ Edition , we might also consider (Exercise 2) which might not be given in that text book , though (Exercise 3) is there in Newer Editions & all 3 Claims are essentially the Same Idea.
More-over , (Exercise 3) is the Best Way to state that Core Idea.

That can be seen with this intuitive thinking :

(Exercise 1) $[ (WOP \implies S) \land (WOP \iff MI) ] \implies (MI \implies S)\tag{X1}$
(Exercise 2) $[ (MI \implies S) \land (MI \iff WOP) ] \implies (WOP \implies S)\tag{X2}$

We can also see it using logical manipulation.

We are simply assuming & using (Exercise 3) here.
Proving (Exercise 3) is simple enough : Check out https://brilliant.org/wiki/the-well-ordering-principle/#equivalence-with-induction

I am skipping the Proof here , because OP says that the Proof is known & that Proof is not what the Question is about.

OP : To clarify, I know that the well-ordering principle is equivalent to weak mathematical induction; this is not what I am asking.

Proof Over-view : We show that $WOP \implies MI$ & $MI \implies WOP$ , to then conclude that $WOP \iff MI$.

Naturally , the Newer Edition is better focused on the Core Issue.

OP : Another way to state the problem above is: if I can write a valid proof for a statement using the well-ordering principle, can I write a valid proof for the same statement that uses weak mathematical induction without knowing the well-ordering principle?

Yes , we can achieve that with the Equivalences given by (X1) & (X2) , where we can use the Proof Method itself , while not invoking WOP.

OP : I am not sure how to answer this and could not find the answer online.

In general , we just have to show the Equivalence between the two.

Even though we have the Stronger Claim that $MI \iff WOP$ here , within the Context of the Exercise , we have to just show $MI \implies WOP$.

Basic Out-line : Prove WOP with MI , then use the given Proof that "$WOP \implies S$" to get the Chain "$[ MI \implies WOP ] \land [ WOP \implies S ]$" to eventually conclude that "$MI \implies S$"

Diagram & Analogy :

When WOP gives S , we can start at MI , then show WOP & then show S. Hence MI gives S.
When MI gives S , we can start at WOP , then show MI & then show S. Hence WOP gives S.

Here is one analogy to see what is going on.

P1 : When $x$ is Even number , then $x^3+5$ is not divisible by $8$.
P2 : When $x=2y$ , then $x^3+5$ is not divisible by $8$.

Both are true because "$x$ is Even" $\iff$ "$x=2y$" & we have to use that fact (Directly or not) : We can not escape that Equivalence.

Here is one non-mathematical analogy :

Prove that "X1 : US President can press the nuclear bombing button"
Prove that "X2 : Biden can press the nuclear bombing button"
Prove that "X3 : White House Boss can press the nuclear bombing button"

Every Proof of X2 will utilize the fact (Directly or not) that the Authority lies with US President who is "Currently" Equivalent to Biden.
Every Proof of X3 will utilize the fact that White House Boss is Biden who is "Currently" US President.
We can not escape that Equivalence.

Here is one last scientific analogy :

Suppose we have Chemical Ingredient X.
Suppose liquid water is necessary to convert X to Chemical Y through a well-known reaction.
Suppose ice will not react with X.

Prove that we can make Chemical Y with Chemical Ingredient X & ice , even though ice is inert & will not react with X.

Proof : Heat the ice to make liquid water. Then use that water in the well-known reaction to convert X to Y.
We have used the inert ice to convert X to Y !
That occurs because ice (WOP) is equivalent to water (MI) !
We can easily convert X (Premises) to Y (Conclusion S) with that Equivalence
More-over , we can not escape that Equivalence.

Answer 2

In logic if we have two statements $A$ and $B$ such that $A\leftrightarrow B$ (they are equivalent) then this pretty much means there is no essential difference between them. You can think of logic as description of reality, and then $A\leftrightarrow B$ means that both $A$ and $B$ describe (some piece of) reality in equally the same way. In particular we can replace $A$ with $B$ and $B$ with $A$ anywhere in logic, and nothing will change. Or in other words every statement of the form $A\to X$ is equivalent to $B\to X$.

So $A$ and $B$ are just different names for the same phenomenon. Therefore it is unclear what exactly you mean by "use one and not the other". You can of course replace the name "weak induction" with "well ordering" in you proof and everything will be fine and correct. Some conclusions might not be clear, but it is guaranteed to be correct.

My meaning may be made clearer by considering the converse of the problem: prove that if a statement can be proved by MI, then it can be proved by WOP (this is problem 29 of the textbook). This is true because we can construct a proof by WOP from a proof by MI as follows: take the proofs for the base case and inductive step from the proof by MI, then assume to the contradiction that the set $S=\{n>=a:\neg{}P(n)\}$ is nonempty, then use WOP to arrive at a contradiction. This forms a complete proof of the original statement that uses WOP without ever using MI.

So you've taken the proof of "$WOP\to MI$" and then given a statement "$MI\to X$" you combined it to get "$WOP\to MI\to X$", which you can simplify to "$WOP\to X$".

Yeah, the inverse is obvious then. Take the proof of "$MI\to WOP$" and replace statement "$WOP\to Y$" with "$MI\to WOP\to Y$", and finally simplify it to "$MI\to Y$".

But again: this is artificial. There's nothing substantial here, just different wordings.