
Introduction to Logic

Tools for Thought

Induction is reasoning from the specific to the general. If various instances of a schema are true and there are no counterexamples, we are tempted to conclude a universally quantified version of the schema.
p(a) ⇒ q(a) 


p(b) ⇒ q(b)
 → 
∀x.(p(x) ⇒ q(x)) 
p(c) ⇒ q(c) 



Incomplete induction is induction where the set of instances is not exhaustive. From a reasonable collection of instances, we sometimes leap to the conclusion that a schema is always true even though we have not seen all instances. Consider, for example, the function f where f(1)=1, and f(n+1)=f(n) + 2n + 1. If we look at some values of this function, we notice a certain regularity  the value of f always seems to be the square of its input. From this sample, we are tempted to leap to the conclusion that f(n)=n^{2}. Lucky guess. In this case, the conclusion happens to be true; and we can prove it.
n  f(n)  n^{2} 


1  1  1 
2  4  2^{2} 
3  9  3^{2} 
4  16  4^{2} 
5  25  5^{2} 

Here is another example. This one is due to the mathematician Fermat (16011665). He looked at values of the expression 2^{2n} + 1 for various values of n and noticed that they were all prime. So, he concluded the value of the expression was prime number. Unfortunately, this was not a lucky guess. His conjecture was ultimately disproved, in fact with the very next number in the sequence. (Mercifully, the counterexample was found after his death.)
n  2^{2n}+1  Prime? 


1  5  Yes 
2  17  Yes 
3  257  Yes 
4  65537  Yes 

For us, this is not so good. In Logic, we are concerned with logical entailment. We want to derive only conclusions that are guaranteed to be true when the premises are true. Guesses like these are useful in suggesting possible conclusions, but they are not themselves proofs. In order to be sure of universally quantified conclusions, we must be sure that all instances are true. This is called complete induction. When applied to numbers, it is usually called mathematical induction.

The technique used for complete induction varies with the structure of the language to which it is applied. We begin this lesson with a discussion of domain closure, a rule that applies when the Herbrand base of our language is finite. We then move on to Linear Induction, i.e. the special case in which the ground terms in the language form a linear sequence. We look at tree induction, i.e. the special case in which the ground terms of the language form a tree. And we look at Structural Induction, which applies to all languages. Finally, we look at two special cases that make inductive reasoning more complicated  Multidimensional Induction and Embedded Induction.

Use the arrow keys to navigate.
