ags@pucc-i (Seaman) (02/25/84)
There is a way to define exponentiation which sidesteps some of the problems
I outlined in my previous note. I think it is worth mentioning, because it
leads to a simple proof that n < 2**n for all n, using a variation of
Cantor Diagonalization, which is what started the whole discussion.
For openers, let's consider the Zermelo-Fraenkel model of the natural numbers.
According to this model,
(0) Zero is the empty set, 0 = {}.
(1) One is the set {0} = {{}}.
(2) Two is the set {0,1} = {{}, {{}}}.
(3) Three is the set {0,1,2} = {{} ,{{}} ,{{{},{{}}}}.
...
(n) Is the set {0,...,n-1}.
In this model, numbers are sets of a particular form. The successor of a
number n is the set n+{n}, "n union singleton n", where + represents set union.
It is rather pleasant to see how everything can be built out of nothing.
Exercise: Show that the Peano Axioms are satisfied by this model.
Exercise: Show that any finite set can be placed in one-to-one correspondence
with exactly one of the natural numbers, viewed as a set. This
number is called the CARDINALITY of the set. The concept of
cardinality can be carried to transfinite sets, but we don't
need that here.
Exercise: Show that multiplication of natural numbers can be defined in
terms of the cardinality of the CARTESIAN PRODUCT of the two
numbers, viewed as sets. (If you don't know what a Cartesian
product is, skip this exercise. It's just a curiosity which
won't be needed.)
Exercise: Think of a similarly clever way to define exponentiation in terms
of sets. Answer to follow in next article.
--
Dave Seaman
..!pur-ee!pucc-i:ags
"Against people who give vent to their loquacity
by extraneous bombastic circumlocution."