◀ ▲ ▶Branches / Logic / Lemma: The Proving Principle by Complete Induction

Lemma: The Proving Principle by Complete Induction

The proving principle by complete induction is a valid logical argument in first order predicate logic¹. It consists of:

• the base case premise: $p(m)$ for some natural number $m\in\mathbb N.$
• the induction step premise: prove that $p(n+1)$ is true assuming that $p(m)$ is true for all $m \le n,$
• the conclusion: $p(n)$ is true for all $n\in\mathbb N$ greater than or equal the base case $n\ge m.$

Example

We can write the logical argument also as follows:

$$\begin{array}{rll} p(m)&\text{base case premise}&\text{e.g. } 1 = 1^2.\quad (m=1)\\ p(n)\Rightarrow p(n+1)&\text{induction step premise}&\text{e.g. if } 1 + 3 + \ldots + (2n-1)= n^2\text{ for some }n\ge 1\\&&\text {then }1 + 3 + \ldots + 2((n+1)-1)=(n+1)^2.\\ \hline \forall n\ge m: p(n)&\text{conclusion}&1 + 3 + \ldots + (2n-1)= n^2\text{ for all }n\ge 1.\\ \end{array} $$

This logical argument is called "complete" since it includes all (infinitely many) premises for the values $n=m, n+1, n+2\ldots$, and it is called "induction" since it derives the conclusion from the special cases $n=m, n+1, n+2\ldots,$ to the general case $n\ge m.$

Table of Contents

Proofs: 1 2

Mentioned in:

Chapters: 1 2
Definitions: 3 4
Explanations: 5
Parts: 6 7 8
Proofs: 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
Propositions: 79 80 81 82 83 84 85 86 87 88 89 90 91 92

Thank you to the contributors under CC BY-SA 4.0!

Github:

Footnotes