CSE396, Spring 2010             Why 0^0 = 1             Recitation Notes 

In set theory, for *any* sets A and B, the number of different functions 
f: A --> B is |B| to the power of |A|.  This is called the "power rule".
(Here, by the way, mathematical convention does not require that the range
Ran(f) of f be *all of B*, just that Ran(f) is *contained in B*.)
For instance , a function f: A --> {0,1} is the same as a binary string of
length a = |A|, and there are 2^a different binary strings of length a.
(E.g. if A = {0,1,2,3,4} then the string "01101" corresponds to the function
f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 0, and f(4) = 1.)  /Therefore/:

    0^0 equals the number of different functions f: \emptyset --> \emptyset.

So the question becomes: can there be any functions f with Dom(f) = \emptyset
and Ran(f) = \emptyset?  We examine the formal definition:

    A function f: A --> B is a relation R on A x B that meets the property
    "(for all a \in A)(there exists a unique b \in B): (a,b) \in R."

Now a relation R on A x B is the same as a subset of A x B, and since the
Cartesian product of the empty set with itself is the empty set (note also
the consequence 0 x 0 = 0), it follows that
the only possible subset R is the empty set itself.  So if R (that is, f) is
the empty set, is it a function---does it meet the stated property?  
Note that since R is empty, the "(a,b) \in R" part at the end is always false,
so we seem to be headed for a "no" answer.  But, we are "saved" by the
/convention/ that a leading "for all" quantifier on a domain that is *empty*
in this case (since A = \emptyset) /makes the whole statement true/!
Hence the empty function /is/ a function from \emptyset to \emptyset.
The *set* of such functions thus has exactly *one* member, namely \emptyset
itself.  Thus by the power rule, 0^0 = |{\empstset}| = 1.

    Q.E.D.: accepting the convention that a leading universal quantifier on
an empty domain makes a statement true, combined with the "standard embedding
of numerical mathematics within set theory", forces 0^0 to equal 1.


The story gets even richer.  The embedding inductively defines zero to *be*
the empty set and then defines a number n >= 1 to be the *set* {0,...,n-1},
where the members of that set are really the set-theory translations of the
previous natural numbers.  If you let me write 0 for \emptyset, then
1 = {0}, 2 = {0,1} = {0,{0}}, 3 = {0,1,2} = {0,{0},{0,{0}}}, and so forth
into quite ugly-looking numbers.  Also, the set of functions f: A --> B
is written B^A, so the power rule becomes |B^A| = |B|^|A|, which looks nice
compared to |B x A| = |B|x|A| from the homework.  Under these identifications,

    the set of all functions f: \emptyset --> \emptyset
    = emptyset^\emptyset
    EQUALS 0^0, which = {\emptyset} from above, which EQUALS 1.

Thus the identity 0^0 = 1 is interpreted as an identity of sets themselves,
not just of numbers.  Another example is that since n EQUALS {0,...,n-1},
the set of functions f: {0,...,n-1} --> {0,1} EQUALS {0,1}^n, which is already
the notation we have been using for the set of binary strings of length n!
Thus it all comes together in a neat harmonic convergence...
(It also gives a sense in which strings should be numbered from 0 as in
C/C++/Java after all.:-)
				---KWR