Induction is reasoning from
the specific to the general.
If we believe many instances of a schema,
and we know of no counter examples,
then we are often tempted to conclude
that the schema is true in general.
Suppose we believe that a schema holds for
every term in our language.
For example p of a implies q of a.
P of b implies q of b and so forth.
Then we're entitled to
conclude a universally quantified
version of our schema.
For example, for all x,
p of x implies q of x.
Incomplete induction is induction where
this set of instances is not complete.
In reasonable collection we sometime
slink to a universal conclusion even
though we have not seen all instances.
Consider for
example the function shown here.
F of 1 equals 1 and f of n plus
1 equals f of n plus 2 n plus 1.
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're tempted to
leap to the conclusion that f of
n equals n squared.
It's a lucky guess.
In this case, that conclusion happens
to be true, and we can prove it.
Here's another example.
This one is due to
the mathematician Fermat,
he looked at various values of the
expression, 2 to the 2, to the n, plus 1,
for various values of n, and
noticed that they were all prime.
So, he concluded, or
at least conjectured, that the value
of the expression was a prime number.
Unfortunately, this was not a lucky guess.
This conjecture was ultimately disproved.
And in fact, it was disproved to
the very next number in the sequence.
He just didn't have the computing
capacity to realize it.
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 can be useful when
suggesting possible conclusions, but
are not themselves proofs.
In order to be absolutely sure of
universally quantified conclusions.
We have to be sure that
all instances are true.
This is called complete induction.
The techniques for
complete induction vary with the structure
of the language to which they're applied.
We begin this lesson with
the discussion of domain closure,
a rule that applies when the Huron
base of a language is finite.
We then move on to linear induction.
That is the special case
where the ground terms in
the language form a linear sequence.
After that we look at tree induction,
the special case in which the ground
terms of the language form a tree.
And finally, we look at structural
induction, which applies to all languages.