1
00:00:05,419 --> 00:00:08,940
Induction is reasoning from
the specific to the general.

2
00:00:10,290 --> 00:00:15,560
If we believe many instances of a schema,
and we know of no counter examples,

3
00:00:15,560 --> 00:00:19,139
then we are often tempted to conclude
that the schema is true in general.

4
00:00:20,960 --> 00:00:24,700
Suppose we believe that a schema holds for
every term in our language.

5
00:00:24,700 --> 00:00:26,580
For example p of a implies q of a.

6
00:00:26,580 --> 00:00:29,350
P of b implies q of b and so forth.

7
00:00:30,560 --> 00:00:31,470
Then we're entitled to

8
00:00:31,470 --> 00:00:33,600
conclude a universally quantified
version of our schema.

9
00:00:33,600 --> 00:00:38,970
For example, for all x,
p of x implies q of x.

10
00:00:38,970 --> 00:00:43,420
Incomplete induction is induction where
this set of instances is not complete.

11
00:00:43,420 --> 00:00:48,470
In reasonable collection we sometime
slink to a universal conclusion even

12
00:00:48,470 --> 00:00:50,290
though we have not seen all instances.

13
00:00:51,720 --> 00:00:53,440
Consider for
example the function shown here.

14
00:00:54,530 --> 00:00:59,820
F of 1 equals 1 and f of n plus
1 equals f of n plus 2 n plus 1.

15
00:01:01,770 --> 00:01:03,850
We look at some values of this function.

16
00:01:03,850 --> 00:01:06,430
We notice a certain regularity,

17
00:01:06,430 --> 00:01:08,830
the value of f always seems to
be the square of its input.

18
00:01:11,020 --> 00:01:14,400
From this sample we're tempted to
leap to the conclusion that f of

19
00:01:14,400 --> 00:01:15,210
n equals n squared.

20
00:01:15,210 --> 00:01:17,180
It's a lucky guess.

21
00:01:17,180 --> 00:01:21,320
In this case, that conclusion happens
to be true, and we can prove it.

22
00:01:23,990 --> 00:01:25,630
Here's another example.

23
00:01:25,630 --> 00:01:27,350
This one is due to
the mathematician Fermat,

24
00:01:27,350 --> 00:01:32,240
he looked at various values of the
expression, 2 to the 2, to the n, plus 1,

25
00:01:32,240 --> 00:01:37,220
for various values of n, and
noticed that they were all prime.

26
00:01:38,780 --> 00:01:39,550
So, he concluded, or

27
00:01:39,550 --> 00:01:43,580
at least conjectured, that the value
of the expression was a prime number.

28
00:01:45,360 --> 00:01:47,270
Unfortunately, this was not a lucky guess.

29
00:01:47,270 --> 00:01:50,740
This conjecture was ultimately disproved.

30
00:01:50,740 --> 00:01:53,410
And in fact, it was disproved to
the very next number in the sequence.

31
00:01:53,410 --> 00:01:56,370
He just didn't have the computing
capacity to realize it.

32
00:01:59,480 --> 00:02:01,350
For us, this is not so good.

33
00:02:01,350 --> 00:02:03,910
In logic,
we are concerned with logical entailment.

34
00:02:03,910 --> 00:02:06,510
We want to derive only conclusions
that are guaranteed to

35
00:02:06,510 --> 00:02:09,250
be true when the premises are true.

36
00:02:09,250 --> 00:02:12,530
Guesses like these can be useful when
suggesting possible conclusions, but

37
00:02:12,530 --> 00:02:13,630
are not themselves proofs.

38
00:02:14,960 --> 00:02:18,760
In order to be absolutely sure of
universally quantified conclusions.

39
00:02:18,760 --> 00:02:20,610
We have to be sure that
all instances are true.

40
00:02:20,610 --> 00:02:23,140
This is called complete induction.

41
00:02:25,540 --> 00:02:26,230
The techniques for

42
00:02:26,230 --> 00:02:29,500
complete induction vary with the structure
of the language to which they're applied.

43
00:02:30,600 --> 00:02:33,920
We begin this lesson with
the discussion of domain closure,

44
00:02:33,920 --> 00:02:36,680
a rule that applies when the Huron
base of a language is finite.

45
00:02:38,100 --> 00:02:40,440
We then move on to linear induction.

46
00:02:40,440 --> 00:02:42,230
That is the special case
where the ground terms in

47
00:02:42,230 --> 00:02:43,380
the language form a linear sequence.

48
00:02:45,180 --> 00:02:46,510
After that we look at tree induction,

49
00:02:46,510 --> 00:02:51,270
the special case in which the ground
terms of the language form a tree.

50
00:02:51,270 --> 00:02:55,044
And finally, we look at structural
induction, which applies to all languages.