NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/crypt/2899

Internet Message Format | 1992-08-14 | 3.2 KB

Path: sparky!uunet!wupost!uwm.edu!rutgers!dziuxsolim.rutgers.edu!zodiac.rutgers.edu!leichter
From: [e-mail]
Newsgroups: sci.crypt
Subject: Re: Math Induction (was Re: tabulation of primes)
Message-ID: <[e-mail]>
Date: 14 Aug 92 02:29:54 GMT
References: <[e-mail]> <[e-mail]>
Sender: [e-mail]
Organization: Rutgers University Computing Services
Lines: 61
Nntp-Posting-Host: cancer.rutgers.edu

In article <[e-mail]>,
[e-mail] (Michael Fischer) writes:
| [e-mail] (Mark A Biggar) writes:
| : I have seen two different definitions of induction:
| :
| : method 1
| :       prove p(0)
| :       prove (p(0) & p(1) & ... & p(n)) -> p(n+1)
| :       therefore p(x) holds for all positive integers
| :
| : method 2
| :       prove p(0)
| :       prove p(n) -> p(n+1)
| :       therefore p(X) holds etc.
| :
| : Are these of equal strength, in other words can I prove some things with 1
| : that I can't prove with just 2?
|
| They're equivalent.  [Proof omitted]

I suspect this is a case of getting the right answer to the wrong question.

I'll bet Mr. Biggar has misstated his Method 1, based on a misunderstanding.
There IS an alternative definition of induction, which reads like this:

method 1'
:       prove p(0)
:       prove (if m < n then p(m)) -> p(n)
:       therefore p(x) holds for all values x

For the integers, methods 1 and 1' are equivalent.  However, there are larger
sets of values over which induction works for which they are VERY different.
The details are too complex to go into here, but there is a theory of ordinal
numbers which starts with the integers.  Then there is the first limit
ordinal, called omega, which has the property that omega is greater than any
integer.  But it doesn't stop there; omega+1 is greater than omega, and so
on.

The important thing about omega - which is why it is called a limit ordinal -
is that it can only be reached as the limit of a sequence; there is no n such
that n+1 equals omega.  (2*omega is the "next" limit ordinal, beyond all
omega + n, for any integer n.  And so on.)

Now, consider the predicate p(n) = (n < omega).  Clearly, p(0) is true.
Further, it's true (since adding one to an integer gives you another integers)
that, if p(n), then p(n+1).  This is sufficient to prove what we started with:
That for all integers n, p(n).  But it is NOT enough to prove the (false)
statement that p(omega)!  So method 2 (and the equivalent method 1) work fine
for the integers, but they stop there.

On the other hand, method 1' works even for the non-finite ordinals.  You
can see that you can't apply method 1' to p, because even though p(n) is true
(trivially) for all n < omega, it's false that p(omega).  So 1' is stronger.
In fact, it's MUCH stronger, and is the basis of "transfinite induction",
which can be used to prove statements about some VERY large objects.  (In
particular, transfinite induction can be applied to non-countable sets,
while "normal" induction cannot.  Oh, of course, mathematicians who have
problems with inductive proofs (actually, in proofs by contradition over
infinite sets) don't even want to talk about these "big" ordinals.

                            -- Jerry