4
$\begingroup$

For proofs by well-ordering principle the general template is to consider the negation of some predicate $P(n)$. Then assume the set of all elements that fulfill $\lnot P(n)$, i.e.

$\qquad N = \{ n \mid \lnot P(n) \}$

has a smallest element according to WOP, say $m = \min N$, and if we manage to prove that there is another element $m' \in N$ that is less than $m$ that also negates then we contradict our assumption that $m$ is the smallest element.

My question is that should we be proving some sort of a base case as well for the above mentioned template. As in proving that for some base case, $P(\mathrm{base})$ is true?

Improve this question
$\endgroup$
1
4
$\begingroup$

In the Wiki page,

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element.

Pay attention to the word non-empty.

Consider the negation of P(n). Before you assume the set that satisfying P(n) is false has a smallest element m, you already assume that the set is non-empty. You prove that there is another element that is less than m. This contradicts the assumption that the set is non-empty. Thus, the set is empty which means P(n) is true.

Improve this answer
$\endgroup$
2
$\begingroup$

This is not an induction proof, but a proof by contradiction.

Goal: Proof that $P(n)$ for all $n \in X$.

Strategy: Assume towards a contradiction the contrary, i.e. there is non-empty $N \subseteq X$ so that for all $n \in N$, $P(n)$ does not hold. Then, as you describe, pick $m = \min N$ -- this is not an assumption as such, but a choice¹ -- and derive that there is $m' < m$ with $m' \in N$, which contradicts the choice of $m$. Hence, the assumption that there is such $N \neq \emptyset$ can not hold and the claim must be true.

  1. It requires, of course, that the base set $X$ is well-ordered.
Improve this answer
$\endgroup$
-1
$\begingroup$

A typical example is show gcd(a,b) = min { ma+nb > 0: integers m,n }.

By Well-Ordering-Principle this set has a least element x. One check's it's the GCD.

The GCD certainly divides x. If it did not divide a or b we could run division algorithm and the remainder would be a smaller number in this set.

We've basically shown the Euclidean algorithm terminates at some point (using WOP), which is the GCD.

Invoking WOP is like the "base case" and checking that x satisfies your properties of interest can be compared to "induction".

The outline for using WOP is

  • Let's prove P(n) for all n by consider the set where P(n) is false
  • As a subset of natural numbers there is a least positive number m where P(m) is false
  • Prove there's a smaller number m' < m where P(m') is still false

Well Ordering Principle and Induction are equivalent even though they feel different.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks John. Just to clarify that in your above example all you are using WOP for is that some minimum element for a set {ma+nb > 0 and ma+nb<max(a,b)} exist right? You are not using WOP to prove that it is the gcd though right or even that the algorithm results in some common divisor. $\endgroup$ – Abdul Rahman Sep 2 '13 at 14:09
  • $\begingroup$ WOP tells us this minimum number exists we then argue it is the GCD $\endgroup$ – john mangual Sep 2 '13 at 14:18
  • $\begingroup$ One thing I had against not proving the base case for proofs by WOP is that this can let bogus induction proofs pass through. Suppose P(n) in which P(base) is not true but P(m)->P(m+1). Using WOP the proof for P(n) would be something like that a minimum number that contradicts P(n) exists. Suppose m+1 is the minimum number and then we prove that P(m)->P(m+1). and that contradicts that P(m+1) is false. Hence for no m P(m) is false. So even though P(base) is false using WOP the proof just went through $\endgroup$ – Abdul Rahman Sep 2 '13 at 14:22
  • $\begingroup$ Hey John, So using your outline of proof by WOP as a reference eventually we will fall all the way through to P(base) and if P(base) is false then you have the smallest integer for which P(base) is false. $\endgroup$ – Abdul Rahman Sep 2 '13 at 15:03
  • 1
    $\begingroup$ You've missed the point: you need to prove that the set is non-empty. For the gcd example, it's easy (take $m=a$ and $n=b$) except when $a=b=0$ (then the set is empty). $\endgroup$ – Gilles 'SO- stop being evil' Sep 3 '13 at 9:42

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.