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!

  • $\begingroup$ possible duplicate of Well-Ordering and Mathematical Induction $\endgroup$ – Shobhit Sep 11 '13 at 4:43
  • 1
    $\begingroup$ Different statements can be logically equivalent. They are still different. $\endgroup$ – Zev Chonoles Sep 11 '13 at 4:44
  • $\begingroup$ 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? $\endgroup$ – user60887 Sep 11 '13 at 5:16
  • $\begingroup$ @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" $\endgroup$ – whatdidthefoxsay Sep 11 '13 at 5:19
  • $\begingroup$ Because they are equivalent, you can transform one into the other. $\endgroup$ – Carsten S Dec 28 '13 at 22:13

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)$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.