Rigorously prove the principle of complete induction from mathematical induction??

Printable View

June 28th 2010, 09:53 AM
mfetch22

Rigorously prove the principle of complete induction from mathematical induction??

Use the following definition of "The Principle Of Mathematical Induction", given as:

Quote:

THE PRINCIPLE OF MATHEMATICAL INDUCTION

If $A \subseteq \mathbb{N}$ and

[1] $1 \in A$

[2] $(k+1) \in A$ whenever $k \in A$

Then it follows that $A= \mathbb{N}$

using only the above definition, and the nine basic axioms of number (along with the axioms for positive numbers, i.e. Trichotomy Laws, Closure Under Addition, and Closure Under Multiplication), to rigorously prove that "The Principle of Complete Induction" is a consequence of "The Principle of Mathematical Induction". The Principle of Complete Induction (which is required to be rigorously proven as a consequence of mathematical induction) is defined below:

Quote:

THE PRINCIPLE OF COMPLETE INDUCTION

If $A \subseteq \mathbb{N}$ and

[1] $1 \in A$

[2] $(k+1) \in A\;\;if\;\;(1,\;...\;,k) \in A$

Then it follows that $A = \mathbb{N}$

I've tried this multiple ways, and nothing seems to arrive at the second principle as being a consequence of the first. Can anybody please help me out here?
June 28th 2010, 10:25 AM
MoeBlee

I don't know what are your "nine basic axioms of numbers".

Do you have the "least number principle"? I.e., if there is a natural number in A, then there is a LEAST natural number in A. If so:

Assume (1) and (2) in the second principle.

Use the first principle to show A=N.

From (1) in the second principe, we have 1 in A.

Suppose k in A. We need to show k+1 in A. So, from the second principle, we need to show that every n less than or equal to k is in A. But we have k in A. So we only need to show that every number less than k is in A. Toward a contradiction, suppose n is the LEAST number less than k that is not in A. So every number less than n is in A. But then, by (2) in the second principle, we have n in A, a contradiction.
June 28th 2010, 12:36 PM
mfetch22

Quote:

Originally Posted by MoeBlee

I don't know what are your "nine basic axioms of numbers".

Do you have the "least number principle"? I.e., if there is a natural number in A, then there is a LEAST natural number in A. If so:

Assume (1) and (2) in the second principle.

Use the first principle to show A=N.

From (1) in the second principe, we have 1 in A.

Suppose k in A. We need to show k+1 in A. So, from the second principle, we need to show that every n less than or equal to k is in A. But we have k in A. So we only need to show that every number less than k is in A. Toward a contradiction, suppose n is the LEAST number less than k that is not in A. So every number less than n is in A. But then, by (2) in the second principle, we have n in A, a contradiction.

This problem is in a text book that is for a class I will be taking this fall, so I don't have any teachers or classmates to refer to. The text book did not actually make the stipulation that the proof may only use the nine basic axioms of number, but I assumed this to be a stipulation since all the proofs in the book so far seemed to only use axioms that have been given to the reader, or certain properties that have been proved within the previous pages. The book simply gives the principle of mathematical induction as I stated above, then goes on to say

Quote:

Originally Posted by "Calculus: Fourth Edition", a text book written by Michael Spivak; page 23, paragraph 3

"There is still another form of induction which should be mentionded. It sometimes happens that in order to prove $P(k+1)$ we must assume not only $P(k)$ , but also $P(l)$ for all natural numbers $l \leq k$ . In this case we rely on the 'principal of complete induction' [the text then states the principle as posted above] Although the principle of complete induction may appear much stronger then the ordinary principle of induction, it is actually a consequence of that principle. The proof of this fact is left to the reader. "

Flipping back through the practice problems of the previous chapter (which was the first chapter of the book) I found a few more "principles" that I failed to mention as already proven or shown at this point in the text. I will post these "principles", along with the exact definitions given for the "nine basic axioms of number" below in order to be more exact as to which concepts I'm guessing are implied as 'allowed' by the text book within this proof.

Quote:

Originally Posted by From the textbook

Axioms, or Properties, of Numbers

[P1] $a+(b+c) = (a+b)+c$

[P2] $a+0 = 0+a=a$

[P3] $a+(-a)=(-a)+a=0$

[P4] $a+b = b+a$

[P5] $a \cdot (b \cdot c) = (a \cdot b)\cdot c$

[P6] $a \cdot 1 = 1 \cdot a = a;\;\;1 \neq 0$

[P7] $a \cdot a^{-1} = a^{-1} \cdot a = 1,\;\;for\;\;a \neq 0$

[P8] $a \cdot b = b \cdot a$

[P9] $a \cdot (b+c) = a \cdot b + a \cdot c$

Properties for the collection of all positive numbers, deonted P

[P10] For every number $a$ , one and only one of the following holds:
(i) $a=0$

(ii) $a \in P$

(iii) $-a \in P$

[P11] If $a \in P$ and $b \in P$ , then $(a+b) \in P$

[P12] If $a \in P$ and $b \in P$ , then $(a \cdot b) \in P$

In the same chapter it also includes (these are the things I forgot to mention), that:

[1] The absolute value of a number $a$ is denoted $|a|$ and is defined as,

$\[|a| = \begin{cases} \;\;\;a & \text{ if }\;\; a \geq 0 \\ -a & \text{ if } \;\;a \leq 0 \end{cases}\] $

[2] For the collection of all positive numbers, denoted $P$ , we shall make the following definitions,

$(i)\;\;\;a>b\;\;\text{if}\;\;(a-b) \in P$ ;

$(ii)\;\;\;a<b\;\;\text{if}\;\;b>a$ ;

$(iii)\;\;\;a \geq b\;\;\text{if}\;\;a>b\;\;\text{or}\;\;a=b$ ;

$(iv)\;\;\;a \leq b\;\;\text{if}\;\;a<b\;\;\text{or}\;\; a=b$ ;

[3] The maximum of two numbers $a$ and $b$ is denoted as $max(a, b)$ . The minimum of two numbers $a$ and $b$ is denoted as $min(a, b)$ . More precisely we have,

$max(a, b) = \frac{a + b + |b - a|}{2}$

and

$min(a, b) = \frac{a + b -|b - a|}{2}$

[4] For all numbers $a$ and $b$ we have,

$|a+b| \leq |a|+|b|$

Phew! With all that out of the way, does your proof use any properties that are not listed? A side note, which is probably very obvious, but also included in the "properties allowed for usage in the proof" would be, I'm assuming, any additional properties that can be proved/shown/derived using the listed properties, correct? Sorry, I'm new to this "proof" stuff. Thats why I included so much in this post, because I'm not certain what is and what isn't truly neccesarly to logically and 'axiomatically' deduce the solution to the orginal problem. Thanks in advance
June 28th 2010, 04:11 PM
emakarov

The equivalence of simple (or ordinary) and strong (or complete) induction is an interesting and deep fact. The proof is based on the choice of a different (what I call) induction statement.

Suppose we are allowed to use simple induction for any induction statement A. (In your formulation, A is a set, but I prefer to view it as a predicate that is true precisely on elements of the set. These views are equivalent.) We need to prove complete induction for some particular statement (set) B.

Since complete induction is an implication, to prove it we assume the premises:

(*) B(1) and
(**) for all n, B(n+1) follows from B(1), ..., B(n)

The goal is to show "for all n, B(n)".

(Optional remark: note that the combined premise B(1), ..., B(n) is stronger (i.e., implies) B(n). Therefore, the whole implication (**) is weaker (i.e., is implied) by the implication "B(n) => B(n + 1)". Thus, when we are faced with deriving "for all n, B(n)", we are given weaker assumptions than in simple induction and so cannot use simple induction without some change. Deriving B(n) from weaker assumptions is a more difficult task; therefore it is called "strong" induction.)

We need to show "for all n, B(n)". The proof of this last fact is done using simple induction; however, as the induction statement A(n) we choose not B(n) itself but "for all k <= n, B(k)". I.e., A(n) states that not only B(n) is true but B(1), ..., B(n) are all true.

Now our intermediate goal is to prove "for all n, A(n)", i.e., "for all n, for all k <= n, B(k)" using simple induction. The required conclusion of the complete induction "for all n, B(n)" easily follows from here using reflexivity of <=.

The base case of simple induction is A(1), i.e., B(1). It has been assumed as (*).

The induction step is "for all n, A(n) implies A(n + 1)". It is easy to see that this means proving B(1), ..., B(n), B(n + 1) from B(1), ..., B(n). Now, B(1), ..., B(n) are already contained in the assumption. One only has to derive B(n + 1) from (B(1), ..., B(n). But this is assumed as (**).

tl;dr: In proving complete induction from regular one, the key is to change the induction statement so that it pertains not just to one n but to all 1 <= k <= n.
June 29th 2010, 12:06 AM
aman_cc

Quote:

Originally Posted by emakarov

The equivalence of simple (or ordinary) and strong (or complete) induction is an interesting and deep fact. The proof is based on the choice of a different (what I call) induction statement.

Suppose we are allowed to use simple induction for any induction statement A. (In your formulation, A is a set, but I prefer to view it as a predicate that is true precisely on elements of the set. These views are equivalent.) We need to prove complete induction for some particular statement (set) B.

Since complete induction is an implication, to prove it we assume the premises:

(*) B(1) and
(**) for all n, B(n+1) follows from B(1), ..., B(n)

The goal is to show "for all n, B(n)".

(Optional remark: note that the combined premise B(1), ..., B(n) is stronger (i.e., implies) B(n). Therefore, the whole implication (**) is weaker (i.e., is implied) by the implication "B(n) => B(n + 1)". Thus, when we are faced with deriving "for all n, B(n)", we are given weaker assumptions than in simple induction and so cannot use simple induction without some change. Deriving B(n) from weaker assumptions is a more difficult task; therefore it is called "strong" induction.)

We need to show "for all n, B(n)". The proof of this last fact is done using simple induction; however, as the induction statement A(n) we choose not B(n) itself but "for all k <= n, B(k)". I.e., A(n) states that not only B(n) is true but B(1), ..., B(n) are all true.

Now our intermediate goal is to prove "for all n, A(n)", i.e., "for all n, for all k <= n, B(k)" using simple induction. The required conclusion of the complete induction "for all n, B(n)" easily follows from here using reflexivity of <=.

The base case of simple induction is A(1), i.e., B(1). It has been assumed as (*).

The induction step is "for all n, A(n) implies A(n + 1)". It is easy to see that this means proving B(1), ..., B(n), B(n + 1) from B(1), ..., B(n). Now, B(1), ..., B(n) are already contained in the assumption. One only has to derive B(n + 1) from (B(1), ..., B(n). But this is assumed as (**).

tl;dr: In proving complete induction from regular one, the key is to change the induction statement so that it pertains not just to one n but to all 1 <= k <= n.

I have struggled with this myself, so here is a proof I came up to satisfy myself.

Let A be as defined for complete induction.

Define X as follows
$n \in X$ IFF ${1,2,3,...,n} \subseteq A$

1. $1 \in X$
2. Let $n \in X$ => ${1,2,3,...,n} \subseteq A$ => $(n+1) \in A$ => ${1,2,3,...,n,n+1} \subseteq A$ => $n+1 \in X$

Hence X = N
All we need to show now is X = A and we will be done.

$ A \subseteq X $

Let $n \in X$ => $1,2,3,...,n \in A$ => $n \in A$

Hence done !

Any comments on this? This is essentially the idea emakarov suggested - However if someone can throw more light on "The equivalence of simple (or ordinary) and strong (or complete) induction is an interesting and deep fact"? Why is that so?
June 29th 2010, 05:31 AM
emakarov

I agree with your proof.

Quote:

Originally Posted by aman_cc

Hence X = N
All we need to show now is X = A and we will be done.

$ A \subseteq X $

Let $n \in X$ => $1,2,3,...,n \in A$ => $n \in A$

I believe you are showing $X \subseteq A$ , which is indeed what is needed because it implies $A=N$ .

Quote:

However if someone can throw more light on "The equivalence of simple (or ordinary) and strong (or complete) induction is an interesting and deep fact"? Why is that so?

I'll write some thoughts later. For starters, this fact is important because, for example, in writing a proof assistant software, it is sufficient to have just one induction axiom. There are other induction principles, like two-dimensional and strong two-dimensional ones, but they are also derivable from the basic variant. Some other things are harder to explain without going technical, and I am not an expert on them either.
June 29th 2010, 05:41 AM
aman_cc

Yes that's exaclty what I wanted to prove.
Becuase the other side is obvious from the fact that X = N
June 29th 2010, 09:37 AM
mfetch22

Thanks everybody. This clears it up allot. I never even considered to try just simply defining another set to facilitate the proof in the manner above, but it works just perfect. Thanks again for all the posts.
June 29th 2010, 10:31 AM
MoeBlee

Ah, interesting that Emarkov's proof is essentially the same strategy for a proof I was going to post proving the "least number principle". His proof uses that strategy to go, as is preferable for the purpose of the exercise, straight from weak induction to strong induction, whereas I was going to go from weak induction to least number principle to strong induction.
June 29th 2010, 11:22 AM
TheCoffeeMachine

I'm wondering, why didn't you use the hint?

Quote:

Originally Posted by Question 11

Prove the principle of complete induction from the ordinary principle of induction. Hint: If $A$ contains $1$ and $A$ contains $n+1$ whenever it contains $1,..., n$ , consider the set $B$ for all $k$ , such that $1,...,k,$ are all in $A$ .

Clearly, $1$ is in $B$ . If $K$ is in $B$ , then $1,...,k$ are all in $A$ , so $k+1$ is in $A$ , so $1,...,k+1$ are in $A$ , and $k+1$ is in $B$ . By ordinary induction, $B = N$ , so also $A = N$ .
June 29th 2010, 12:10 PM
mfetch22

Quote:

Originally Posted by TheCoffeeMachine

I'm wondering, why didn't you use the hint?
Clearly, $1$ is in $B$ . If $K$ is in $B$ , then $1,...,k$ are all in $A$ , so $k+1$ is in $A$ , so $1,...,k+1$ are in $A$ , and $k+1$ is in $B$ . By ordinary induction, $B = N$ , so also $A = N$ .

It was not until this afternoon that I even realized that the question at hand was a "practice problem" in the book. It was an unreasonable oversight on my behalf, but I was only refering to the part within the text where the author dicusses both principles and than drops the line "The proof of this is left to the reader, with a hint". Of course I over looked the fact that he stated in "(Problem 11)" next to the suggestion to the reader. It was not until this afternoon that I went back to the practice problems again for a seperate reason, and happened to noticed problem 11. In a "no duh!" type of moment, I clearly realized that the reference was to a practice problem within the book, where the hint resided. Of course, I had already tried proving the statement without the hint, and as a consequence had already posted this thread. By the time I stumbled upon the hint, it had already been explained within the numerous posts above, here in this thread. Therefore, the reason I did not use the given hint was due to the fact that I had completely over looked the obvious reference at the end of the sentence in which the suggestion to prove the statement was contained.