Is the use of complete induction advantageous in this proof?

[snipez90]

I came across this proof in Spivak that appears to use complete (strong) induction. He is trying to argue that a set A of natural numbers with no least member is the empty set.

He let's another set B be the set of natural numbers 1, ..., n that are NOT in A. For the base case, 1 is in B since otherwise 1 would be the least member in A. Then he assumes that 1, ..., k are not in A, then k + 1 is not in A (otherwise, k+1 is the least member of A). Hence, the set B contains all the natural numbers, all not in A, so A is the empty set.

Is this an example of complete induction? Do you use complete induction when it is advantageous or clear that the numbers between 1 and k are important in understanding the proof? For instance, this proof emphasizes the notion that the numbers between 1 and k (and also 1 and k) could not be in A, so it makes it clear why k + 1 would be the least member if it was in A. Although I guess it wouldn't really be that different if we used regular induction. You would still precede from 1 to 2 to 3 to show that the statement holds for all natural numbers, but does complete induction help to reduce the perceived gap between 1 and k?

 

[gunch]

Although I guess it wouldn't really be that different if we used regular induction.

Actually it would be somewhat different. To use induction you create a predicate P(k). Using regular induction you show that,
P(k)\Rightarrow P(k+1)
And for complete induction you show,
P(1),P(2),\ldots,P(k) \Rightarrow P(k+1)
If we let,
P(k) = "k \not\in A"
as in your example, then we can use complete induction, but we can't use regular induction since the assumption that k is not in A isn't enough to conclude that k+1 is the least element in A (k-1 could be in A because we haven't assumed P(k-1)). So at the very least we need a new predicate to use regular induction. On the other hand we can simulate complete induction using regular induction by letting the predicate be,
Q(k) = "1,2,\ldots,k\not\in A"
Then Q(1) is true and Q(k) \Rightarrow Q(k+1). We can always simulate complete induction in this way using regular induction, but when complete induction feels more natural, why not use it? Complete induction is simply a tool when we need a somewhat more powerful assumption.

 

[HallsofIvy]

I would call it "strong induction": if a statement, P(n), depending on the positive integer n, is true for n= 1, and whenever P(i) is true for all i less than or equal to k, P(k+1) is also true, then P(n) is true for all positive integers n.

That is "stronger" than regular induction- if a statement, P(n), depending on the positive integer n, is true for n= 1, and whenever P(i) is true for k, P(k+1) is also true, then P(n) is true for all positive integers n- but can be proved from regular induction.

The fact that every non-empty set of positive integers contains a smallest integer follows from that as you say.

And then you can prove regular induction from "well-ordered". All three are equivalent.

 

[mathwonk]

actually the well ordering principle does not folow from induction, unless you assume that every positive integer has a predecessor. of course this is true, so those properties are equivalent when stated for the positive integers.

but they are not equivalent for any well ordered set. e.g. if you consider two copies of the natural numbers, one following the other, or equivalently assume that all even numbers are larger than all odd numbers then you still have the fact that every non empty subset has a least element, but you do not any longer have the property that set containing 1 and also containing n+1 whenever it contains n, is the whole set.

so the principles of induction are not true for all well ordered sets, hence are not equivalent as abstract properties to the principle of well ordering. but for the positive integers, assuming every such integer (after 1) has a largest predecessor, they are equivalent.

many books make the error of claiming these properties are equivalent. they are not unless you assume the principle of induction is true. i.e. in any set satisfying the principle of induction, all three properties are equivalent, but the properties are not equivalent in general. i.e. you cannot assume only the well ordering principle about the integers, you ned to assume one of the principles of induction, or else define the natural numbers somehow as the smallest inductive set, or some other such nonsense.