# Homework Help: Proving PMI from nothing? Help find the error!

1. Aug 11, 2012

### Wenti

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

1. The problem statement, all variables and given/known data
Prove the Principle of Mathematical Induction from the Well-Ordering Principle.

2. Relevant 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.

3. 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}$.

2. Aug 11, 2012

### HallsofIvy

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

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.

3. Aug 11, 2012

### Wenti

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

$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?

4. Aug 13, 2012

### Ray Vickson

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

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

5. Aug 13, 2012

### Wenti

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

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$?

6. Aug 13, 2012

### Ray Vickson

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

"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

7. Aug 14, 2012

### Wenti

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

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.

8. Aug 14, 2012

### Ray Vickson

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

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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook