ags@pucc-i (Seaman) (02/24/84)
This is a continuation of the "Pedantic question" discussion. Here is
a brief sketch of the proof that if n has finitely many digits, then the
successor of n also has finitely many digits. The proof uses the Fifth
Peano Axiom (i.e. Mathematical Induction).
For convenience, let's use base two. A "digit" is "0" or "1". A digitstring
is a (possibly empty) sequence of digits. If a is a digitstring, then
l(a) is the last digit of a and r(a) is a with the last digit removed.
Concatenation is represented by writing one string after the other.
For example, if a = "10101" then l(a) = "1", r(a) = "1010", and a"1" =
"101011".
We are ready to give interpretations to the basic terms "zero", "number"
and "successor".
Zero is "0".
A number is a non-empty digitstring.
The successor of a number a is s(a), given by:
(1) If l(a) = "0" then s(a) = r(a)"1". [s("xyz0") = "xyz1"]
(2) s("1") = "10".
(3) If l(a) = "1" then s(a) = s(r(a))"0". [s("xyz1") = s("xyz")"0"]
It is trivial to verify (using induction) that "successor" is well-defined
for all numbers. The first few numbers are "0", "1", "10", "11", "100", ....
It is also trivial to verify (by induction on the length of a) that s(a) is
at most one digit longer than a, for all a. In particular, the induction
hypothesis allows us to assert, in part (3) of the definition of "successor,"
that s(r(a)) is at most one digit longer than r(a).
I haven't filled in all the details, since this discussion was already
pedantic when it began and it has been getting steadily worse.
I challenge anyone to approach this level of detail in proving that
"n is less than 2**n, for all n". The obvious steps are:
(1) Prove that every number other than zero has a unique predecessor.
(2) Define addition. [Hint: if a<>0 then a+b = successor of
((predecessor of a) + b).
(3) Define "less than".
(4) Define multiplication.
(5) Define exponentiation.
... (You get the idea).
Even when you get through all this, you still have to prove the rather
questionable statement:
"Suppose M has an infinite number of leading ones. Then M is greater
than 2**n for all n."
I have trouble even assigning a meaning to that statement, let alone
trying to prove it. In order to show that M is greater than N, don't
you first have to show that M and N are numbers?
--
Dave Seaman
..!pur-ee!pucc-i:ags
"Against people who give vent to their loquacity
by extraneous bombastic circumlocution."