Author |
Topic: 0! = 1 (Read 1267 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
Long time no post! 
I'm having a small problem with supposed proofs I see for the result that 0! = 1. I have no issue with defining it and I am quite happy to assert that fact(0) = 1, then using the recursive relation, fact(n) = n*fact(n-1) for n>=1 to define the factorial function. However, I do not believe that the result (0! = 1) can be proved without first assuming it.
The standard elementary "proof" goes something like this...
n! = n*(n-1)!, so if we let n = 1, we get 1! = 1*0!, hence 0! = 1/1 = 1. This seems quite neat, but...
It is flawed, as n! = n*(n-1)! only makes sense if either 0! is first defined. Otherwise it only holds for n > 1, in which case we are in violation by writing n = 1.
The more "rigorous proof" makes use of the Gamma function...
It is relatively easy to show, given G(x) = int(t^(x-1)*e^-t dt) between 0 and infinity, that G(x) = x*G(x-1), which allows us to show that G(n) = (n-1)!. It is also fairly easy to show that G(1) = 1; in fact the previous result requires this.
In which case, G(1) = (1-1)! = 0! = 1.
(Here is a link showing an outline of the proof:
http://mathforum.org/library/drmath/view/54563.html)
But I have issues with this proof. In showing that G(x) = x*G(x-1) we integrate the Gamma function by parts and substitute 0 and infinity into the first term: t^(x-1) = 0 when t = 0 and e^-t = 0 when t = infinity, so the product is elminated.
However, we note that t^(x-1) = 0 is only true when x > 1; 0^0 is indeterminate. Hence the recursive relation, G(x) = xG(x-1), which leads to G(n) = (n-1)!, is only valid for x > 1 (or n > 1), and writing G(1) = (1-1)! in violation of this.
Could someone shed some light on this?
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
 |
Re: 0! = 1
« Reply #1 on: Nov 29th, 2005, 5:32pm » |
 Quote  Modify
|
You've got good point there: the integration by parts is only valid for x>1. And (without extending G) so is the relation G(x) = (x-1)G(x-1), because the integral defining G(x-1) only converges for x>1.
But in fact G(z) is holomorphic in the region Re(z) > 0, and extends meromorphically to the whole plane. So, because G(x)=(x-1)G(x-1) for x>1, it follows by analytic continuation that the equality holds everywhere in their domain, i.e., for z not in {1,0,-1,-2,...}. So, for example, G(1/2) = -1/2 G(-1/2), but note that G(-1/2) is not defined by the integral, but by its (unique) meromorphic extension to C. And this still doesn't show that G(x)=(x-1)G(x-1) holds for x=1, except in the sense that both sides approach the same value as x->1 (note (x-1) goes to 0, while G(x-1) blows up).
But of course this only proves 0! = 1 if you first define 0! = G(1). Indeed, there's no way to prove 0! equals anything without first defining it! But it does provide a perfectly good way to extend the definition of z! to arbitrary z, in such a way that z! = z(z-1)!. (In fact, if you also require log (z!) to be convex for z>-1, then z! =G(z+1) is the only way.)
Combinatorially, the best argument for making 0! = 1 is because it makes the formulas work. Thus (n choose 0) = 1 because this makes the binomial theorem work, and 0! =1 because this makes (n choose r) = n!/(r!(n-r)!) work.
Personally, the most convincing argument for why 0! = 1 is because n! is defined to be the number of ways to order an n-element set, and there's simply nothing wrong with this definition when n=0. There is precisely 1 set with 0 elements, and there's precisely 1 way to order it. (An order on a set S is a subset of SxS satisfying conditions like, for all x,y in S, blah. If S is the empty set, so is SxS; it therefore has precisely one subset, which satisfies the definition of order vacuously.)
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 0! = 1
« Reply #2 on: Nov 29th, 2005, 11:33pm » |
Quote Modify
|
I tend to agree with Eigenray's combinatorial arguments.
What about a relevant definition 00 = 1?
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: 0! = 1
« Reply #3 on: Nov 30th, 2005, 12:50am » |
Quote Modify
|
Thank you for your reply, Eigenray.
Barukh, I would go with the other option: 00 = 0.
In the proof we cannot allow x to be equal to 1 because 00 is indeterminate. However, once we establish that 0! = 1, I wonder if it is valid to return to the proof and now look at what 00 must be in order to make it hold. If it were equal to 1, we would get G(x) = -1 + xG(x-1) which would then invalidate the result G(n) = (n-1)!.
So what is the position here in terms of 00? Does it show that in this domain it is equal to zero, or must we just put it down to an unfortunate (and potentially misleading) coincidence that G(n) = (n-1)! gives the correct result for n=1 and still insist that it is undefined for x=0?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 0! = 1
« Reply #4 on: Nov 30th, 2005, 2:52am » |
Quote Modify
|
I don't really get your idea what is wrong with 0!.
If 0! has any value at all, 0! = x, then 1! = x·1 = x, so either 0! has no meaning at all (a product of 0 terms) or it is 1. Unlike 00 I don't see any alternative value for 0!
The trouble starts with (-1)!
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 0! = 1
« Reply #6 on: Nov 30th, 2005, 9:24am » |
Quote Modify
|
on Nov 30th, 2005, 12:50am, Sir Col wrote:| In the proof we cannot allow x to be equal to 1 because 00 is indeterminate. |
|
No, that's actually irrelevent: when integrating a function from 0 to infinity, the value at the single point 0 doesn't matter at all, just the values in between (more generally, we can ignore the values on any set of 0 measure).
When x=1, if we try to integrate by parts we get
G(1) = [int] t0e-t dt
= t0(-e-t)]t=0oo - [int] 0*(-e-t)dt
= limt->oo -t0e-t - limt->0 -t0e-t
= 1.
So the problem is that instead of the boundary term being 0, and just getting (x-1)G(x-1) (giving us the recurrence), when x=1 the boundary term is 1, and the integral term is just zero, which we can't properly write as 0*G(0). G(0) isn't even defined, as the integral diverges when x=0:
[int] t-1e-tdt > e-1 [int]t<1 dt/t = infinity.
on Nov 29th, 2005, 11:33pm, Barukh wrote:| What about a relevant definition 00 = 1? |
|
By definition, xy is the number of functions f : Y->X, where |Y|=y, |X|=x. There is exactly one function f mapping the empty set to itself, for any reasonable definition of function.
Note that there are no functions from a non-empty set to the empty set, so 0x=0 for x > 0. But there's always a unique function from the empty set to any set, so x0 = 1 for all x.
And combinatorially, having x0=1 for all x makes the binomial theorem work (not to mention tons of other formulas).
|
| « Last Edit: Nov 30th, 2005, 9:25am by Eigenray » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 0! = 1
« Reply #7 on: Nov 30th, 2005, 9:16pm » |
Quote Modify
|
My thoughts on 0! = 1 do not differ substantially from Eigenray's comments, but I would like to try and explain it a little differently.
We generally start out with the definition, for n >=1, that n! = (1)(2)...(n).
From this it quickly follows that, for n>=2, n! = n(n-1)!
Next comes the question: "Can we extend our definition in such a way that the formula still holds?"
That is where your "proof" comes in. But it is not intended as a proof that 0! = 1. Instead, it is a proof that the only possible value that 0! could be defined to have, while having the formula remain true, is 1.
So, we note that if 0! were defined, and if the formula were still to hold for n=1, then we would have 1! = 1*0!, so that 0! = 1.
This being the case, we define 0! = 1, and note that the formula now holds for n>=1.
Then we find out that (-1/2)! = sqrt(pi) and go around scratching our heads trying to figure out how that fits in.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: 0! = 1
« Reply #8 on: Dec 1st, 2005, 12:46am » |
Quote Modify
|
I had wondered about that idea of extending too, but then I wasn't happy with what happens if we continue...
1! = 1*0! => 0! = 1 ... okay so far...
However, if 1 = 0! = 0*(-1)!, then we get zero multiplied by something giving 1. So does this undermine the result 0! = 1 obtained through extension, or does it simply demonstrate that any further extension would lead to nonsense?
Eigenray, could you, or someone, please expand that explanation of the definiton of xy? (I confess to not following it)
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 0! = 1
« Reply #9 on: Dec 1st, 2005, 5:42pm » |
Quote Modify
|
on Dec 1st, 2005, 12:46am, Sir Col wrote:| However, if 1 = 0! = 0*(-1)!, then we get zero multiplied by something giving 1. So does this undermine the result 0! = 1 obtained through extension, or does it simply demonstrate that any further extension would lead to nonsense? |
|
Neither. It shows that n! = n(n-1)! breaks down when n=0. So there's no obvious way to define (-1)! to be anything finite. And if we can't define (-1)!, we can't define (-2)!, or any n! when n is a negative integer. Before you just pick a value for (-1)!, and then extend in such a way that n!=n(n-1)! holds for all non-zero integers, consider the following. G(x) is perfectly well-defined when x>0, and G(x+1)=xG(x) for x>0. But if x<0, we can use this relation to define G(x) in the obvious way: If x>-1, and x non-zero, then G(x+1) is defined, so we can set
G(x) := G(x+1)/x.
Then we can use the same equation to define G(x) for x > -2, x not 0 or -1. Iterating, this defines G(x) for all x not a non-positive integer (in fact, the exact same definition works for any complex number z, replacing the condition x > -m by Re(z) > -m). Then G(z) ends up being a merophic function in the whole plane, with simple poles at {0, -1, -2, ...}. So in fact there's no (finite) value you could use for (-1)!, (-2)!, ..., to make G continuous. But for any other number z, you can define z!, and you'll still have (z+1)! = (z+1)z!.
Another way to define (the same extension of) G is to break the integral into two pieces: t<1 and t>1. For t<1, writing e-t = [sum] (-t)n/n! (yet another reason to take 0! = 00 = 1  ), and integrating term by term:
G(z) = [int]t=1oo e-ttz-1dt + [sum]n=0oo (-1)n/(n!(z+n)).
This manipulation is only valid for Re(z)>0, but the result is shown to be a meromorphic function on C, with a simple pole of residue (-1)n/n! at each z=-n, n=0,1,....
And of course there's also the product formula:
1/G(z) = egamma z z [prod]n=1oo (1+z/n)e-z/n,
where gamma = lim(Hn - log n) ~ .577 is Euler's constant. But how this relates to the integral definition is less clear; it sorts of magically ends up being the same since it has the same roots and the right growth condition.
Quote:| Eigenray, could you, or someone, please expand that explanation of the definiton of xy? (I confess to not following it) |
|
If X,Y are sets with x,y elements, then xy counts functions from Y to X, because you pick one of x things y times. This can be taken as the definition for natural numbers x,y, and 0 is the most natural number of all. (In fact it works for arbitrary cardinals, but ordinal exponentiation is a bit more subtle: xy is the order type of { f : y->x | f(t)=0 for all but finitely many t }, ordered by reverse lexicographical order.)
A function f : A -> B is a subset of AxB such that for all a in A, there exists a unique b in B such that (a,b) is in f, i.e., b=f(a). If S is the empty set, then 00 is the number of functions from S -> S. Any such function must be a subset of SxS = S, so S is the only possibility. And "for all x in S, foo" is vacuously true, because it can't possibly be false. So S is the unique function from S -> S.
A more general argument for why 0! = 1 is because it is the product of all positive integers less than or equal to 0. Empty products should be taken to be 1 (and similarly empty sums should be 0). This is so that if A,B are disjoint sets, then
[prod]x in A u B f(x) = [prod]x in Af(x) * [prod]x in B f(x).
As an example, what is the determinant of the 0x0 matrix? The determinant of an n x n matrix is
det A = [sum]s in S_n sign(s) [prod]i=1n ai,s(i).
When n=0, S0, permutations of the empty set, contains the single (empty) permutation. This permutation is obviously the identity, so its sign is 1. Then we have an empty product, so that's 1. Thus the determinant of a 0x0 matrix is 1. Another way to see this is when we compute the determinant of a 1x1 matrix A=(a) using cofactor expansion, det(A) = a*det(A'11), after crossing out the first row and first column from A, we get the zero matrix, which needs to have determinant 1.
This may seem silly, but the 0x0 matrix represents the identity transformation on the zero space, which is zero-dimensional (its basis is the empty set -- it's vacuously linearly independent, and its span is the set of all empty sums, which are each the 0 vector). So its determinant should be 1. Or, consider that if V is the direct sum of two T-invariant subspaces W1, W2, then det(T) is the product of the determinant of T restricted to each subspace, and we need to allow that any V is the direct sum of the zero space with itself.
A word of caution though about extending combinatorial definitions beyond their intended scope. For example, we could define 2n to be the number of compositions of n+1. That is, the number of ways to write n+1 as a sum of positive integers, counting order. This works fine for n >= 0, but for n = -1, the combinatorial definition makes perfect sense, and would make 2-1 = 0. (Compare with "2n is the number of subsets of a given set of size n"; then 2-1 would be just plain undefined, because there are no sets of size -1.)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 0! = 1
« Reply #10 on: Dec 1st, 2005, 8:07pm » |
Quote Modify
|
A way to relate the definition of xy to our more common understanding of exponentiation as repeated multiplication.
Suppose we have two disjoint sets A, B, with cardinality a, b. Of course, we know that card(A U B) = a + b.
And for arbitrary sets A, B, we know that the card(A x B) = ab.
Assume that a, b are finite. For each v c A, we can define the set Bv = { (v, w) : w c B }. For each v c A, Bv is in 1-1 correspondence with B, by w <--> (v, w). So card(Bv) = card(B) = b. Further all of the Bv are disjoint from each other. And A x B = UvcA Bv.
Therefore, ab = card(A x B) = card(UvcA Bv) = SvcA card(Bv) = b + b + ... + b (a times).
Thus the concept that multiplication is just repeated addition is contained within the set-theoretic definition.
Now we move on to exponentiation. If I take the product of B by itself a times, B x B x B x ... x B, an element of this set is an a-tuple (b1, b2, ... , ba). The indices 1..a do not necessarily have to be those numbers. Any other set of a elements could be used to index the tuple as well. In particular, we have this handy set A. So we replace (b1, ... , ba) by the "sequence" {bv}vcA. But that sequence represents a function from A --> B. Thus every element of B x B x B x ... x B induces a function from A --> B, and since each such function is a sequence, which corresponds to a tuple, every function induces a tuple (the same tuple that induces it). Thus the set B x B x ... x B (a times) is in 1-1 correspondence with the set BA of functions from A to B.
And ba = card(BA) = card (B x B x ... x B) = b*b*b*...*b (a times).
And so we find the concept that exponentiation is repeated multiplication is also built into the set-theoretic definition.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print