2. Induction and the Well-ordering Principle
The meaning of the word `induction' within mathematics is very dierent from the collo quial sense!
First, let
P
(
n
) be a statementinvolving the integer
n
, whichmay b e true or false. That is, at this p oint
wehavea
grammatical ly
correct sentence, but are making no general claims about whether the sentence is
true, true for
one
particular value of
n
, true for
al l
values of
n
,oranything. It's just a sentence.
Now we introduce some notation that is entirely compatible with our notion of
function
, even if the
present usage is a little surprising. If the sentence
P
(
n
)
is
true of a particular integer
n
, write
P
(
n
)= true
and if the sentence asserts a
false
thing for a particular
n
, write
P
(
n
)= false
That is, we
can
view
P
as a
function
, but instead of producing
numbers
as output it pro duces either
`true'
or
`false'
as values. Such functions are called
b oolean
.
This style of writing, even if it is not what you already knew or learned, is entirely parallel to ordinary
English, is parallel to programming language usage, and has many other virtues.
Caution:
There is an
another
, older tradition of notation in mathematics which is somewhat dierent,
which is and which is harder to read and write unless you know the trick, since it is
not
like ordinary English
at all. In that
other
tradition, to write `
P
(
n
)' is to assert that the sentence `
P
(
n
)' is
true
. In the
other
tradition, to say that the sentence is
false
you write `
:
P
(
n
)' or `
P
(
n
)'.
So, yes, these twoways of writing are not compatible with each other. Too bad. We need to makea
choice, though, and while I
once
would havechosen what I call the `older' tradition,
now
I like the rst way
better, for several reasons. In any case, you should be alert to the p ossibility that other people maychoose
one or the other of these writing styles, and you have to gure it out from context!
Principle of Induction
If
P
(1) = true, and
if
P
(
n
) = true
implies
P
(
n
+ 1) = true for every p ositiveinteger
n
,
then
P
(
n
) = true for
every
positiveinteger
n
.
Caution:
The second condition do es
not
directly assert that
P
(
n
) = true, nor do es it directly assert
that
P
(
n
+ 1) = true. Rather, it only asserts a
relative
thing. That is, more generally, with some sentences
A
and
B
(involving
n
or not), an assertion of the sort
(
A
implies
B
) = true
does not
assert that
A
= true nor that
B
= true, but rather can b e re-written as
conditional
assertion
if (
A
= true) then
B
= true
In other words we prove that an
implication
is true.
5
