Proving PMI from nothing? Help find the error

[Wenti]

"Proving" PMI from... nothing? Help find the error!

Homework Statement

Prove the Principle of Mathematical Induction from the Well-Ordering Principle.

Homework Equations

Principle of Mathematical Induction (PMI):
If A \subset \mathbb{N} satisfies
(i) 1 \in A,
(ii) if k \in A, then k+1 \in A,
then A = \mathbb{N}.

Well-Ordering Principle (WOP):
If A \subset \mathbb{N} is nonempty, then A has a least element.

The Attempt at a Solution

I know how to solve this problem using the hypotheses from WOP. My problem is that I noticed an alternate "proof" that does not even use WOP, and I can't seem to find my error.

Assume that A \neq \mathbb{N}. Then, there exists some m \in \mathbb{N} such that m \notin A. By the (contrapositive) second hypothesis of PMI, this means that m-1 \notin A. But if m-1 \notin A, then m-2 \notin A. Repeating this process m-1 times yields that 1 \notin A, contradicting the first hypothesis of PMI that we are assuming. Therefore, A =\mathbb{N}.

 

[HallsofIvy]

How do you prove the statement "Repeating this process m−1 times yields 1"? Think carefully about how "m-1" is defined before answering this.

 

[Wenti]

m-1 = \underbrace{1 + 1 + \cdots + 1}_{m-1 times}.

I'm not sure why the statement needs to be proved or how to prove it statement. A little stab in the dark: are you saying that proving that statement requires induction itself, so I'm using my problem in my proof?

 

[Ray Vickson]

m-1 = \underbrace{1 + 1 + \cdots + 1}_{m-1 times}.

I'm not sure why the statement needs to be proved or how to prove it statement. A little stab in the dark: are you saying that proving that statement requires induction itself, so I'm using my problem in my proof?

How you prove the result depends on what you know already and are allowed to use. You are NOT allowed to use any theorem whose proof used the PMI, because you are trying to prove the PMI. So, although every m \in \mathbb{N} has a successor Sm, and there are some axioms made about how S behaves, there is no guarantee that every m \in \mathbb{N} has a *predecessor*; that is, how do you know that m-1 exists? Of course, if we have the PMI we can prove all the things we need, such as the existence of a predecessor for every m \neq 1, but without such results, you cannot begin to talk about m-1.

RGV

 

[Wenti]

That makes sense.

... However, I'm still a little confused, because I thought that conclusion was based on the second hypothesis of PMI, not on PMI itself. Isn't it analogous to say "how do you know that m+1 exists?"; the second hypothesis of PMI asserts that existence. So shouldn't the contrapositive assert the non-existence of m-1?

 

[Ray Vickson]

That makes sense.

... However, I'm still a little confused, because I thought that conclusion was based on the second hypothesis of PMI, not on PMI itself. Isn't it analogous to say "how do you know that m+1 exists?"; the second hypothesis of PMI asserts that existence. So shouldn't the contrapositive assert the non-existence of m-1?

"m+1" exists is the same as saying m \in \mathbb{N} \longrightarrow Sm \in \mathbb{N}, where S is the successor operator. The existence of S (and some properties of S) are in the very axioms you started with.

RGV

 

[Wenti]

So then don't we have m \in S \Rightarrow Sm \in S \Leftrightarrow Sm \notin S \Rightarrow m \notin S? Or is that not correct? If it's not, that's probably exactly where my problem is.

 

[Ray Vickson]

So then don't we have m \in S \Rightarrow Sm \in S \Leftrightarrow Sm \notin S \Rightarrow m \notin S? Or is that not correct? If it's not, that's probably exactly where my problem is.

Without induction I think that all we can say is that the successor function S obeys the following: S:\mathbb{N} \longrightarrow \mathbb{N}\backslash \{1\} is _into_ and one-to-one (basically, those are among the axioms). In order to show that any y \in \mathbb{N} \backslash \{1\} has the form y = Sx for some x \in \mathbb{N}, we would need to know that the map is _onto_.

Anyway, even if we could prove that, it is still not clear that, starting from m you can eventually get to 1 by taking m-1, (m-1)-1, ... . Of course, it must be true, but we are speaking here about what can be _proven_ without using PMI.

RGV