8
$\begingroup$

Here is the text from Knuth's The Art of computer programming, 1.2.6 F formula 14:

enter image description here

Knuth doesn't give the proof of the statement. So, I tried to write it myself.

To make binomial formula equal to $0^0$, it must satisfy the following conditions:

$ \left\{ \begin{aligned} x = -y\\ r = 0\\ \end{aligned} \right. $

By definition:

$ {n\choose k}=\frac{n!}{k!(n-k)!} $

If $k < 0$ or $k > n$, the coefficient is equal to 0 (provided that n is a nonnegative integer) - 1.2.6 B.

and if $r = 0$, we have:

$ {0\choose k} $

which is non-zero only when k = 0:

$ {0\choose 0} = \frac{0!}{0!(0-0)!} = \frac{1}{1} = 1 $

So, putting our conditions into the formula, we get:

$ (x + (-x))^0 = {0\choose 0} x^0(-x)^0 = 1\cdot1\cdot1 = 1 $

Therefore, $0^0 = 1$

Is my proof correct?

Also this page: http://mathworld.wolfram.com/Power.html says, that $0^0$ itself is undefined, although defining $0^0=1$ allows some formulas to be expressed simply (Knuth 1992; Knuth 1997, p. 57).

But he is not defining it to be equal to 1, he is deducing this fact from binomial theorem. Plus Knuth doesn't say on page 57 (which is provided), what formulas can be expressed simply. Is the statement about Knuth on mathworld not fully correct?

$\endgroup$
  • 1
    $\begingroup$ $0^0$ is truly undefined, but this is saying "choose zero objects from a set of size $n$" and "choose $n$ objects from a set of size zero" will both be expressible as $0^0$ for $n=0$. That is to say, $0^0$ is a result from many branches of mathematics, and although ${0 \choose 0} = 1$ may be re-expressed as "$0^0$ can take on the value $1$", there is information about ${0 \choose 0}$ that is lost in the re-expression. This is similar to what happens when you rearrange the terms of a conditionally-convergent series. $\endgroup$ – abiessu Aug 24 '13 at 21:23
  • 2
    $\begingroup$ Even in computer science, defining $0^0 = 1$ is dangerous as there may be situations in which this is the incorrect result. Consider interval arithmetic, for example. $\endgroup$ – abiessu Aug 24 '13 at 21:33
  • 1
    $\begingroup$ @abiessu Could you collect your comments into an answer, so this question does not show up on the unanswered queue? $\endgroup$ – Potato Aug 25 '13 at 0:11
  • $\begingroup$ @abiessu: Cold you explain what is the problem with $0^0=1$ and interval arithmetic? Doing interval arithmetic (or ordinary computation for that matter) one would replace a function $x^y$ with variable exponent by $\exp(y\ln x)$, and $x^0$ with constant exponent by$~1$, and in either case no problem arises. (In the former case one cannot set $x=0$, and this is appropriate, and taking the limit $x\to0$ gives the proper behaviour for that case; in the latter case one correctly gets $0^0=1$ without having to compute it.) $\endgroup$ – Marc van Leeuwen Aug 25 '13 at 6:35
  • $\begingroup$ $0^0$ is not a problem in interval arithmetic; interval arithmetic provides one mechanism to properly evaluate (within the limits of known error) functions which contain the term $0^0$ $\endgroup$ – abiessu Aug 25 '13 at 14:00
12
$\begingroup$

I think you do not interpret the text as it was intended. What Knuth is saying is that the binomial formula as stated cannot be valid unless one defines $0^0=1$. He says so more clearly in his 1992 article Two notes on notation (page 6, equation (1.18)):

Anybody who wants the binomial theorem $$(x + y)^n =\sum_{k=0}^n\binom nk x^ky^{n−k}$$ to hold for at least one nonnegative integer $n$ must believe that $0^0 = 1$, for we can plug in $x = 0$ and $y = 1$ to get $1$ on the left and $0^0$ on the right.

Indeed one has for instance $1=(0+1)^2=\binom20.0^0.1^2+\binom21.0^1.1^1+\binom22.0^2.1^0$, and the right hand side reduces to $0^0$ because the last two terms vanish because of the non-controversial evaluations $0^1=0^2=0$.

So in particular, this does not just involve the case of the binomial theorem for exponent$~0$; the point is that exponents$~0$ occur on the in the right hand side for every instance of the binomial formula.

Note that one usually does not encounter this case explicitly because of our habit of contracting the term $\binom n0x^0y^n$ to $y^n$ whenever we write explicit instances of the binomial formula. Your citation illustrates this, as Knuth writes terms $x^4$ and $y^4$ in his explicit instance of the binomial formula for $r=4$. (It also illustrates another common peculiarity: in explicit instances of the binomial formula we tend to take the summation index decreasing from $n$ to $0$, or what amounts to the same use a variant of the formula in which the exponents of $x$ and $y$ are interchanged.)

Indeed, the most important reason we are not confronted with instances of $0^0$ (and therefore with the need to have it well defined) all the time is, that we have learned the habit, similar to that of suppressing explicit terms$~0$ in a summation or factors$~1$ in a product, of immediately replacing any expression $x^0$ by$~1$ (or simply omitting it if occurring in a product). I consider this a nice paradox of human psychology:

The fact that people can maintain that $0^0$ should be left undefined depends on the circumstance that instances of the expression almost never occur when doing mathematics. This state of affairs is a consequence of the habit of systematically suppressing multiplicative factors of the form$~x^0$ when writing formulas. This notwithstanding the fact that the equation $x^0=1$ implicitly applied during this suppression can only be justified if $x^0$ is always defined, in particular for $x=0$.

$\endgroup$
  • $\begingroup$ I agree with your summation of the common use of $0^0$, however I leave my answer as is to show why this use is valid for certain contexts but may not be valid in all contexts. $\endgroup$ – abiessu Aug 25 '13 at 14:38
  • 1
    $\begingroup$ Re your final remark: $0^0$ shows up in two very different contexts. In one context, we are doing discrete things (e.g. things like "repeatedly multiply $n$ times where $n$ is an integer"), in which case $0^0$ makes sense and should be $1$. In the other context, we are doing continuous things, and the presence of $0^0$ indicates that things break down, and we very much don't want $0^0=1$. These are really two different contexts where we do different things; it's mildly remarkable they agree in as many cases as they do. (which, of course, is why we use the same notation for both) $\endgroup$ – Hurkyl Aug 25 '13 at 14:40
  • $\begingroup$ Note if I wanted to be similarly condescending, I could say that the only reason people can maintain $0^0=1$ is as a consequence of systematically avoiding the continuous edge cases where it gets you into trouble. This actually applies to more than just $0^0$ -- negative bases with rational exponents, for example. But really, it just boils down to different people being focused on different areas of mathematics, and thus being lead to different conventions, and not being exposed to the difference between them being treated fairly. $\endgroup$ – Hurkyl Aug 25 '13 at 14:46
  • $\begingroup$ @Hurkyl: thank you for that, I was forgetting this more direct piece of "discrete vs. continuous" context. $\endgroup$ – abiessu Aug 25 '13 at 14:50
  • 2
    $\begingroup$ @Hurkyl: (1) In a expression $0^0$, nobody is asking for limits, (2) with $x^0=1$ for all $x$ and $x^y=\exp(y\ln x)$ for real $x>0$, the function $(x,y)\mapsto x^y$ is discontinuous at $(0,0)$, (3) computing limits of discontinuous functions by plugging in the limit values is a bad idea. So if you are using $0^0=1$ to compute limits of the form $x^y$, you are looking for trouble. But this is no reason to undefine $0^0$ "depending on the context"; just for people evaluating limits to be more careful. $\endgroup$ – Marc van Leeuwen Aug 25 '13 at 14:53
8
$\begingroup$

To the best of my knowledge, the convention that $0^0$ is undefined serves one purpose, namely to avoid a discontinuity of the function $x\mapsto 0^x$ at $0$ (or the function $x^y$ at $(0,0)$). This has value when people (primarily calculus students) think that limits like $\lim_{t\to a}f(t)^{g(t)}$ should be evaluated by plugging $a$ in place of $t$ in $f(t)^{g(t)}$. A discontinuity will cause this method to give the wrong answer when the plugging-in gives $0^0$. Ideally, our calculus students would learn that you have to ascertain continuity before using the plug-in method. In our non-ideal world, a good number of them don't learn that, and so we teach them that $0^0$ is undefined. That way, the result of plugging in will not give them a wrong answer; it will refuse to give them an answer, so it will force them to do something better than plugging in (e.g., take logarithms and try L'Hopital's rule).

But I think the "undefined" convention is useful only for people who might (unknowingly) assume continuity where there is in fact a discontinuity. For the rest of us, $0^0$ should be $1$.

Note, by the way, that the point of discontinuity is at the edge of the domain of definition of $0^y$ (or $x^y$), so it's not particularly surprising (to me) that something strange, from the point of view of analysis, happens there.

$\endgroup$
  • $\begingroup$ Well, it is convenient to take $0^0 = 0$ in the definition of the zero-norm. $\endgroup$ – Ayesha Jul 4 '14 at 2:42
  • 1
    $\begingroup$ But the use of $\sum_{i} |x_i|^0$ as the definition of the zero "norm" seems to me to have basically nothing to do with exponentiation since it's actually computing the Hamming distance to $0$. And if one argues that it can be realised as the limit of $p$-norms as $p$ goes to zero, then continuity and limits are coming back in to the picture and it's no surprise that all bets are off. $\endgroup$ – kahen Jul 9 '14 at 22:47
1
$\begingroup$

By choosing this way of arriving at $0^0$ and assigning it the value $1$ without any other qualifying statements, Knuth has in fact made a definition of sorts. So the Mathworld article is correct.

Also, I see your proof as valid for the given result. By choosing the mechanisms you have, you arrived at that particular value of $0^0$. This is similar to what happens when the terms of a conditionally convergent series are rearranged: it is almost always possible to get any value desired as the result. A better term for this is "indeterminate" rather than "undefined" as the Mathworld article notes.

Basically, by choosing the Binomial Formula as the context, you have chosen the value that $0^0$ will have. This does not change the fact that $0^0$ is indeterminate when considered without context.

$0^0$ is truly indeterminate in general, but Knuth and your proof are saying $(0+x)^0 = 1$ is expressible as $0^0 = 1$. You have chosen a specific context, and within that context $0^0$ evaluates to $1$.

Another way to say this is that $1^0 = 1$ may also be expressed as "$0^0$ can take on the value $1$", but this does not convey any more information than saying that "${\infty \over \infty}$ can take on the value $1$".

Even in Computer Science, defining $0^0 = 1$ is dangerous as there may be (read: there are always) situations in which this is an incorrect result. Consider interval arithmetic as a way of handling the expression $0^0$ properly within a computer.

Consider the following examples: what is the value of $\lim_{x \to 1} (1-x)^{x-1}$? $\lim_{x \to 0} (\cos(x) - 1)^x$?

$\endgroup$
  • 1
    $\begingroup$ I you say that "$0^0$ is truly undefined", you must also consider that the binomial formula (13) in the question fails to be true for $r=2,x=0,y=1$: the left hand side is unambiguously $1^2=1$, but the right hand side is undefined due to the factor $x^k$ in the summand for $k=0$ (the other factors in the product are nonzero, so the $0^0$ survives). That is Knuth's main point, not the case $r=0$; see my answer. $\endgroup$ – Marc van Leeuwen Aug 25 '13 at 14:36
  • $\begingroup$ I agree, and I am considering how to reword what I have said to reflect that the binomial formula has no ambiguity, while $0^0$ as a term by itself with no context cannot be evaluated. $\endgroup$ – abiessu Aug 25 '13 at 14:40
0
$\begingroup$

I would have thought it's a consequence of a prior definition.

Namely 0! = 1

And generally this definition is taken to be a definition of convenience rather than anything having true mathematical value. So I would have thought $0^0$ should have the same status?

$\endgroup$
  • 2
    $\begingroup$ Actually, it is the other way around. $0^0$ is the number of maps from the empty set to the empty set, namely $1$. $0!$ is the number of permutations of the empty set, namely $1$. The latter follows from the former since the permutations of the empty set are a subset of the maps from the empty set to the empty set. It turns out, the set of mappings are the same. $\endgroup$ – robjohn Jul 10 '14 at 0:34
  • $\begingroup$ $0^0$ is undefined, but it is often convenient to take $0^0 = 1$, e.g. when writing a polynomial as $a_0 z^0 + \dotsb + a_n z^n$ you want $z^0 = 1$ even when $z = 0$ (as Knuth does). Otherwise $0^k = 0$, so you want $0^0 = 0$ if the exponent varies. $\endgroup$ – vonbrand Sep 29 '15 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.