1

I was asked to recast an induction proof to a proof by well ordering princple. How are the 2 different? From my understanding the two are equivalent, so how will the proof be different? Thanks!

whatdidthefoxsay
  • 111
  • 1
  • 1
  • 7
  • possible duplicate of Well-Ordering and Mathematical Induction – Shobhit Sep 11 '13 at 04:43
  • 1
    Different statements can be logically equivalent. They are still different. – Zev Chonoles Sep 11 '13 at 04:44
  • Usually if you take a look at a proof by the well ordering principle it usually is used to prove that given a set that has positive integers as elements that it has a least element. Usually done so by contradiction. Take a look at a proof of the division alogrithm. While induction does imply the well ordering principle and vice versa. But if its going from an induction proof to a proof by the well ordering principle those are two different proof techniques. What was the proof you were trying to change? – user60887 Sep 11 '13 at 05:16
  • @user60887 I'm trying to proof that "If I draw n straight lines on a piece of paper I cannot divide the piece of paper into more than n(n+1)/2 +1 regions" – whatdidthefoxsay Sep 11 '13 at 05:19
  • Because they are equivalent, you can transform one into the other. – Carsten S Dec 28 '13 at 22:13

1 Answers1

1

Since you already have an induction proof of some statement $\forall n \in \mathbb{N}: P(n)$, you presumable have some reasoning that concludes $P(0)$ and other reasoning that proves $P(n) \implies P(n+1)$ for arbitrary $n \in \mathbb{N}$.

This can be transformed into a proof using the well-ordering principle as follows:

Suppose that $\lnot \forall n \in \mathbb{N}: P(n)$. Then there is at least one $n \in \mathbb{N}$ for which $\lnot P(n)$; take the least such $n$. By [insert reasoning here that $P(0)$] $n \neq 0$. By [insert reasoning here that $P(n-1) \implies P(n)$, which we can do because $n \neq 0$] we now also have $\lnot P(n-1)$. This contradicts the fact that $n$ was minimal.

Therefore $\forall n \in \mathbb{N}: P(n)$.

(Note, this looks most natural if you original reasoning for $P(n) \implies P(n+1)$ actually works by assuming $\lnot P(n+1)$ and concluding $\lnot P(n)$.)

Magdiragdag
  • 15,049