Roy's Fortnightly Puzzle: Volume 3
Okay, this one has been keeping me up at night for at least two decades.
What is the value of 0^0?
Mathematicians seem to agree that if it has a unique value at all, the value is 1 (there seems to be less consensus on the antecedent here, however).
The puzzle, of course, is not merely figuring out the answer. The puzzle is to say something about what the criteria for deciding such a question might be. In particular:
Is mathematical practice and convenience the only arbiter here?
Might the philosopher of mathematics have something interesting to say about cases like this?
Is this an uncomfortable situation for the platonist (since the choice of 1 over 0 seems like a case where the facts are just stipulated for convenience, and not 'discovered' via examination of the platonic forms or whatnot)?
Have at it.
Dear Roy,
ReplyDeleteMy first thought is to think that there is no value for 0^0, and so it is proper to think of the expression as undefined. Suppose something like this appeared lurking behind limit terms driving to zero. Wouldn't then the RHS and LHS limits be different, by necessity?
Pointing to bad behavior of 0^0 might yield a non-Platonist, non-conventionalist middle ground. (Mumble, mumble...)
I like the puzzles! Thanks for posting them!
Here is a particularly interesting (from my own philosophical perspective, at least) argument for 0^0 having a value (and that value being 1):
ReplyDelete"Some textbooks leave the quantity 0^0 undefined, because the functions 0^x and x^0 have different limiting values when x decreases to 0. But this is a mistake. We must define x^0=1 for all x , if the binomial theorem is to be valid when x=0 , y=0 , and/or x=-y . The theorem is too important to be arbitrarily restricted! By contrast, the function 0^x is quite unimportant." (Graham, Knuth, and Patachnik, Concrete Mathematics: A Foundation for Computer Science 2nd ed., Addison and Wesley, 1994, p. 162)
The relevant bits of data, in a nutshell:
(a) Limit of x^0 = 1 as x approaches 0 (supporting the 0^0 = 1 reading).
(b) Limit of 0^x = 0 as x approaches 0 (supporting the 0^0 = 0 reading).
(c) Letting 0^0 = 1 (in accord with (a)) avoids restrictions to the binomial theorem.
(d) 0^x is an unimportant function anyway, so we don't need to worry about giving up (b).
Two particular things to note:
(i) First, the idea that treating 0^0 as undefined is a "mistake" and that we "must" set 0^0 as identical to 1. What sense of "must" is intended here?
(ii) Second, the claim that 0^x (as opposed to x^0) is an "unimportant" function. What notion of importance is at issue here?
Interesting.
ReplyDeleteI was putting (a) and (b) together and gesturing toward a discontinuity argument as something that might, in the end, sit on more neutral philosophical grounds.
Perhaps the authors are simply showing their enthusiasm for discrete mathematics, although I can imagine someone interested in learning problems disagreeing strongly with (ii). In any event, viewed on their own terms, I fail to see how 0^0 restricts the binomial theorem any more than 0/0 does.
To Gregory:
ReplyDeleteIf by "fail to see how 0^0 restricts the binomial theorem", you mean "how leaving 0^0 undefined restricts the binomial theorem", then here is why.
The BT gives the expansion of (x+y)^n for all x,y and all integers n. The key here is the word all. If you leave 0^0 undefined, then you have to restrict the applicability of the theorem, eliminating the cases x=0, y=0, (and x=-y) with n=0.
Hi Sergi,
ReplyDeleteBy "any more than" I meant that, if one considers the general form (x+y)^n, key to the general expansion is n choose k, which is 0/0.
By a similar argument, are we to then stipulate that 0/0=1? If not, why not?
Pardon me, Sergei. I lost track of your second 'e'.
ReplyDeleteI think I prefer 1. Another argument, similar to the binomial theorem argument: the function f(x) = x^x approaches 1, if x is a small positive real.
ReplyDelete[On the topic of defining a value for undefined quantities, Ramanujan showed that 1 + 2 + 3 + 4 + ... = -(1/12).]
...and the LHS limit (i.e., when x is a small negative real), f(x) = x^x approaches -1!
ReplyDeleteMore generally, if f(x) and g(x) are analytic functions, then the limit of f(x)^g(x) is 1 (limit from the right - i.e. as positive x gets 'smaller').
ReplyDeleteThis seems to be the most general fact cited in favor of 1 being the 'correct' value (as it includes both limit of x^0 and limit of x^x as special cases).
Likewise, if f(x) and g(x) are analytic functions, then the limit of f(x)^g(x) is -1 (limit from the left - i.e. as negative x gets 'smaller').
ReplyDeleteDefine h(x) = f(x)^g(x). Then, because the left limit of h(x) is not equal to the right limit of h(x) (as x goes to 0), h(x) is discontinuous at x=0. This is the reason for treating 0^0 as undefined.
As for unpacking the 'must' of (i) and the 'unimportant' of (ii) above, 'must' requires a good reason for ignoring the left limit (the source of the discontinuity evaluating h(0)), and 'unimportant' a good reason for considering discrete mathematics as sufficient foundations for computer science (and setting aside a second discontinuity between (a) and (b) above). In fairness, a strong case could be made for thinking of discrete maths as the foundations for computer science in the mid 1990s BG (Before Google), but with the explosion and dominance of machine learning since then, this would be a harder case to make now.
The common consensus between posts seems to indicate that 0^0=1. So if 1^0=1 and x^x as x approaches zero converges at 1 when approaching zero from the right, then it makes sense and doesn't seem to be arbitrary. However, 2^2=2*2=4, therefore 0^0 should be undefined because it isn't a matter of degrees of multiplication, but undefined due to nothing being multiplied.
ReplyDeleteGregory,
ReplyDeleteI think we can separate the question from considerations of the role of discrete mathematics and computer science. Instead, the argument can be taken to hinge on the relative importance of the binomial theorem being defined for all cases versus the supposed relative unimportance of the function 0^x in mathematics generally. And while I do share the intuition that the binomial theorem is somehow more important and central to mathematics than is x^0, I am not sure how this plays out in justifying claims about how we 'must' understand the value of 0^0. Some options:
(a) These mathematical observations provide compelling evidence that platonic reality plays out that way. That is, if we 'find' the genuine, unique exponential function x^y out in Plato's heaven, then it will be defined at <0, 0> and its value will be 1. Obviously, this sort of view can be reworded in terms of one's favored non-platonic understanding of mathematics if need be - the point is that there is an independent fact of the matter and these sorts of facts constitute evidence for believing that we have figured out the right answer.
(b) These mathematical observations provide compelling evidence that mathematical practice will work out better - i.e. more conveniently or whatever - if we treat 0^0 as being identical to 1. Here there is no question of there being a fact of the matter that we might get right or wrong - instead there is the freedom to choose whatever value turns out to be most convenient for our current mathematical practices and, further, presumably we could choose to change the agreed on value of 0^0 if our practices changed over time in a way that would make a different value more convenient).
(a) smacks a bit of mysticism or something to me (and I am about as rabidly platonist as someone can be - I think in most cases we are discovering truths about some independent mathematical reality. Nevertheless, there is something fishy feeling about the idea that there is a unique exponent function that we identify and then inspect to see what it does at <0, 0>.
If we go with option (b), however, then there are all sorts of other strange consequences. In particular, we then need some account of when we can, and when we cannot, freely choose the value of functions at problematic values. For example, it might turn out that we can treat 0^0 as any of 0, 1, -1, or undefined as is convenient, but surely we cannot let 0^0 = 37! Likewise, we have no freedom over 2^2. The question, then, is to determine the criteria separating those cases where we have this sort of freedom from those where we don't. In this specific case, there is a plausible answer: If we give 0^0 a value, then it better be a value that makes it continuous with some limit of x^y or other, but this doesn't give us a criterion for when we can make this sort of arbitrary decision in mathematics in general, keeping in mind that the values of functions might not be the only relevant case.
Dear Roy,
ReplyDeleteWhat do you think of the argument that the expansion of the binomial theorem for 0^0, in general form, would also require that 0/0 be defined?
I have trouble understanding how things would work out better from defining a value for 0^0, for I think Graham, Knuth, and Patachnik are simply wrong about this. I floated the enthusiasm hypothesis judging from the 'Concrete' and 'foundations' and '1994' in the reference book's title. But, the idea was to explain how they could be in a position to feel licensed to selectively ignore mathematical facts about this expression, all of which quickly point to (purely mathematical) troubles.
This was very nice to think about; I had initially mixed together the two different discontinuities in my head, so it was very nice for me to bat this back and forth to get that separated. Many thanks, Roy, all.
Well Roy, you finally dragged me into posting here.
ReplyDeleteHow about this for a trivial answer supporting that 0^0=1:
For integers, x^y is equal to the cardinality of the set of functions from a set of cardinality y to a set of cardinality x. It is trivial from the definition of function to see that for any set A, there is a unique function from the empty set to A: the empty function! (note: category theorists would say the same thing by saying that the empty set is initial in the category of sets.)(note also that we can get the general exponential function from this by analytic continuation. I'm not sure of the philosophical reason behind the move to analyticity, but analytic functions sure are nice, so I'm ok with it.)
Thus, unless we have good reason to question the empty function, it would seem, since the cardinality of the set of functions from the null set to the null set is exactly 1, that 0^0=1.
Shay
Sorry to follow up on my own comment, but I think that this bears further explanation.
ReplyDeleteThe reason for $0^0$ being 1 and for $0^x$ for any other $x$ being 0 is quantifier order in the definition of a function.
Given that $x^y$ is defined as the cardinality of the set of functions from a set of cardinality $y$ to a set of cardinality $x$, $0^x$ is then equal to the cardinality of the set of functions from a set of cardinality $x$ to the empty set. Now, supposing we adopt the set-theorist's convention of identifying a function with its graph, we can say that a function from a set $A$ to a set $B$ is just a collection $C$ of ordered pairs whose first elements are all from $A$, second elements are all from $B$, and (here's the important part) for all $x\in A$, there is exactly one $y\in B$ such that $(x,y)\in C$. Perhaps another nice way to say this is the following:
(1) if $x\in A$, then there is exactly one $y\in B$ such that $(x,y)\in C$.
Using (1), then, we see that the empty set is indeed a function from itself to itself (the empty set is autoendomorphic!), albeit vacuously.
On the other hand, given that there is at least one element in the set $A$, there is no function from $A$ to the empty set, since in order for such a function to exist, there would have to be an element of the empty set to pair with the element in $A$. Thus, $0^x=0$ for $x\neq 0$, and $0^0=1$.
I believe this settles the problem about what the value should be, and resolves the apparent arbitrariness of choice due to the differing limits. There is something interesting to this case still, though.
The definition of $x^y$ that reads ``multiply $x$ by itself $y$ times'' and the definition of $x^y$ that reads it cardinality-wise as I've encouraged should be seen as, in fact, different functions. This is made clear by the fact that we find $0^0$ so confusing -- as a statement about multiplication, it makes no sense. The function defined by the first definition of $x^y$ ought to be undefined at 0. However, in practice, we encounter many situations where it seems that $0^0$ ought to have a value -- the binomial theorem is a good example of this -- and it seems that the value should be 1. What this suggests is not that we ought to stipulate that the function has value one there, and not even that we ought to create another function that mimics $x^y$ elsewhere and takes the value 1 at $0^0$ (this feels too ad-hoc). Instead, what seems to be suggested by this is a closer examination of the context in which various exponential-looking sequences occur might differentiate between when we are using the multiply-a-bunch function and when we are using the cardinality-of-the-set-of-functions function. The coefficients of expansions of binomials are given by enumerating numbers of collections of certain sizes (this is why we normally write it using the choose function). A collection of a certain size (say $x$) from within another collection $D$ of size $y$ is picked out by a function from a set of size $x$ to $D$. This suggests to us that in the binomial formula, what we are using is the cardinality-of-the-set-of-functions function, and thus that (in this context) we should say that $0^0=1$.
Sorry that that was long winded.