Pucc-H:Pucc-I:ags@CS-Mordred.UUCP (02/28/84)
If A and B are arbitrary sets, then A ** B is defined to be the set of all
mappings f: B --> A. For example, if A = {a, b} and B = {x, y, z}, then
one of the possible mappings is the one which sends x |--> a, y |--> a,
and z |--> b.
In my previous article I described the Zermelo-Fraenkel model for the natural
numbers. In this model, numbers are sets. We can therefore use the notion
of exponentiation of sets to define exponentiation of numbers. Of course,
what we get is a set of mappings, rather than a set of numbers. No problem:
If M and N are numbers, we define M ** N to mean the CARDINALITY of M ** N,
viewed as a set.
For example, let's compute 2 ** 3. Since 2 is the set {0, 1} and 3 is the
set {0, 1, 2}, we need to list the mappings f: 3 --> 2. Let us denote the
mapping f by listing the images of 0, 1 and 2 in brackets: [f(0) f(1) f(2)].
The enumerated list of mappings is:
0 <--> [0 0 0] 4 <--> [1 0 0]
1 <--> [0 0 1] 5 <--> [1 0 1]
2 <--> [0 1 0] 6 <--> [1 1 0]
3 <--> [0 1 1] 7 <--> [1 1 1].
We have placed the members of 2 ** 3 in one-to-one correspondence with the
members of the set "8" (i.e. {0, 1, 2, 3, 4, 5, 6, 7}). This shows that
2 ** 3 = 8.
Exercise: Show that N ** 0 = 1 for every N. [Hint: How many mappings can
you think of with domain equal to the empty set?] In particular,
note that 0 ** 0 = 1.
Exercise: Define "binary notation" for the Zermelo-Fraenkel Numbers, based
on the table above. Can you (non-circularly) describe the ordering
used in listing the mappings? What about decimal notation?
Exercise: Next time you declare an array in a C program, think about what
you are writing. When you say "int a[4];" you are naming a set,
"4", whose elements are exactly the allowable subscripts:
{0, 1, 2, 3}. I'll bet K & R never thought of that!
Next: Power Sets and Cantor Diagonalization Revisited.
--
Dave Seaman
..!pur-ee!pucc-i:ags
"Against people who give vent to their loquacity
by extraneous bombastic circumlocution."