0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I don't know what you are asking here. You know they are equivalent. What does it even mean "to write a valid proof without knowing the well-ordering principle". This doesn't make sense, if the principle is equivalent to weak induction, then (1) you cannot not know it and (2) everything deducible from well-ordering is deducible from weak induction by first proving weak induction. The question is weird to be honest. $\endgroup$
    – freakish
    Jan 22 at 11:49
  • $\begingroup$ I understand your confusion and have added clarification to the post. What I am really asking it that if you have a proof by induction for a statement, can you create a proof that uses WOP (instead of induction) for the statement? $\endgroup$
    – Cynicrom
    Jan 22 at 12:17
  • $\begingroup$ I am not sure why this got downvoted (( I will try to rectify that with my +1 )) OP is trying to learn something & has put in the effort. Yes , OP is confused & that is why the Question was asked. $\endgroup$
    – Prem
    Jan 22 at 13:20
  • $\begingroup$ @Cynicrom I think you are confused. Formally define "proof by induction" and "proof that uses WOP" so that we can know how these are different. If you try that you will quickly realize that if $A\leftrightarrow B$ then "$A\to X$" statement can be replaced freely with "$B\to X$" and vice versa. Using the language of logic I don't even see a way to formalize your question. $\endgroup$
    – freakish
    Jan 23 at 7:38
  • $\begingroup$ When you say 'Using the language of logic I don't even see a way to formalize your question" , @freakish , that is what I am hinting at when I say "we can not escape that Equivalence" : there is no way to avoid one & use the other , because the two are actually the Exact Same !! $\endgroup$
    – Prem
    Jan 23 at 9:19

2 Answers 2

1
$\begingroup$

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 :

MES

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.

$\endgroup$
6
  • $\begingroup$ I appreciate the answer, but I believe you've only proven the equivalence between WOP and MI, and not whether you can write a proof using WOP given a proof using MI, which is what I (and the textbook problem) is asking. $\endgroup$
    – Cynicrom
    Jan 22 at 12:19
  • $\begingroup$ Eventually , that is what it is : [[ (1) Take a Proof of S using WOP (2) Ignore WOP (3) But use MI to show that WOP is true (4) Then use WOP to conclude S ]] : Hence we have used MI to conclude S. $\endgroup$
    – Prem
    Jan 22 at 12:33
  • $\begingroup$ You have opened my eyes to a possibility I did not consider. I wonder if this is the author's own answer hinted by her choice of replacing this problem in later editions with a problem asking for a proof that MI => WOP. I still wonder if there is another way to obtain a proof by MI from a proof by WOP. $\endgroup$
    – Cynicrom
    Jan 22 at 12:39
  • $\begingroup$ Correct ! Indeed , "I wonder if this is the author's own answer hinted by her choice of replacing this problem" : That is Exactly what I said in with "More-over , (Exercise 3) is the Best Way to state that Core Idea" : In My Way of thinking here , (Ex 1) & (Ex 2) could be merged to the Stronger Ex3 & that is why the Author did that in the New Editions. $\endgroup$
    – Prem
    Jan 22 at 12:50
  • $\begingroup$ Would it still be possible to construct a proof by MI without first proving WOP? Because a proof by MI that proves WOP in order to arrive at the conclusion technically uses WOP. $\endgroup$
    – Cynicrom
    Jan 22 at 12:53
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .