- #1
Wenti
- 4
- 0
"Proving" PMI from... nothing? Help find the error!
Prove the Principle of Mathematical Induction from the Well-Ordering Principle.
Principle of Mathematical Induction (PMI):
If [itex]A \subset \mathbb{N}[/itex] satisfies
(i) [itex]1 \in A[/itex],
(ii) if [itex]k \in A[/itex], then [itex]k+1 \in A[/itex],
then [itex]A = \mathbb{N}[/itex].
Well-Ordering Principle (WOP):
If [itex]A \subset \mathbb{N}[/itex] is nonempty, then [itex]A[/itex] has a least element.
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 [itex]A \neq \mathbb{N}[/itex]. Then, there exists some [itex]m \in \mathbb{N}[/itex] such that [itex]m \notin A[/itex]. By the (contrapositive) second hypothesis of PMI, this means that [itex]m-1 \notin A[/itex]. But if [itex]m-1 \notin A[/itex], then [itex]m-2 \notin A[/itex]. Repeating this process [itex]m-1[/itex] times yields that [itex]1 \notin A[/itex], contradicting the first hypothesis of PMI that we are assuming. Therefore, [itex]A =\mathbb{N}[/itex].
Homework Statement
Prove the Principle of Mathematical Induction from the Well-Ordering Principle.
Homework Equations
Principle of Mathematical Induction (PMI):
If [itex]A \subset \mathbb{N}[/itex] satisfies
(i) [itex]1 \in A[/itex],
(ii) if [itex]k \in A[/itex], then [itex]k+1 \in A[/itex],
then [itex]A = \mathbb{N}[/itex].
Well-Ordering Principle (WOP):
If [itex]A \subset \mathbb{N}[/itex] is nonempty, then [itex]A[/itex] 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 [itex]A \neq \mathbb{N}[/itex]. Then, there exists some [itex]m \in \mathbb{N}[/itex] such that [itex]m \notin A[/itex]. By the (contrapositive) second hypothesis of PMI, this means that [itex]m-1 \notin A[/itex]. But if [itex]m-1 \notin A[/itex], then [itex]m-2 \notin A[/itex]. Repeating this process [itex]m-1[/itex] times yields that [itex]1 \notin A[/itex], contradicting the first hypothesis of PMI that we are assuming. Therefore, [itex]A =\mathbb{N}[/itex].