2, e, omega
Apr. 6th, 2018 02:22 amThis is not the entry I said I would write -- I'll get to that some other day -- but I want to write about this too. (This entry is based on some notes I sent to Andreas Weiermann, but I think it deserves to be posted somewhere a bit more public. :) )
What do the numbers 2, e, and ω -- as in, the first infinite ordinal -- have in common?
(Yes, those aren't all "numbers" in the same sense. But we'll ignore that for now. And yes they do all make sense as surreal numbers, but I'm not thinking here in terms of surreal numbers but rather being deliberately informal with my use of the word "number". Although, surreal numbers will come in eventually...)
Well, they're all particularly important bases for exponents, of course. But there's more to it than that.
What is ex? Why, it's the sum over k of xk/k!, of course. You know what's approximately xk/k! -- specifically, a little less than it? That's right! It's (x choose k). (Or it's no larger for x≥0, anyway; but I'm basically considering whole numbers as my "prototypical" values of x here.)
And if we take the sum over k of (x choose k), we get... 2x. Well, OK -- certainly this works for whole numbers, but for, say, real numbers it only works if x>-1 (although it still works for all real numbers as an Abel sum). Nonetheless, the point is clear -- whether we consider it for general x or restrict ourselves to whole numbers, the sum of (x choose k) is, morally, 2x.
But there's a third thing in this family. What if instead of (x choose k), we were to use ((x multichoose k)), which is also approximately xk/k!, but a little bit above instead of a little bit below? Now ((x multichoose k)) is equal to (-1)k(-x choose k), so by the binomial theorem, the sum is... 0-x? And indeed, for x<0 this converges to 0, for x=0 we have 1, and for x>0 this series diverges.
What I want to claim is that this 0-x should, in some sense, be interpreted, as ωx. Here I'm kind of cavalierly mixing real numbers and ordinals, I know (and not doing so properly via surreal numbers, just deliberately being informal). Now at this point this clearly sounds crazy. But there's more to it than that.
We turn to the work of Andreas Weiermann on finite multisets in well partial orders. Let X be a well partial order; we can put a well partial order on M(X), the set of finite multisets in X, by saying that S≤T if there is an injection ι:S→T such that ι(s)≥s for all s∈S. Weiermann determined a function f such that, for any well partial order X, o(M(X))=f(o(X)).
What is this f? Well, it's multiplicative, so to define it we need only describe its output on powers of ω. Specifically, we have:
Now, Weiermann didn't mention this in his paper -- quite possibly he didn't notice it at the time, though of course I've since pointed it out to him -- but this is almost exactly the formula for the surreal exponential of an ordinal, as found by Harry Gonshor. (I told you surreals would show up eventually!) The only difference, of course, is that exp(1) is e, not omega. But otherwise they're the same; if α is zero or a limit ordinal (not necessarily a power of omega, note!), we have f(α)=exp(α).
But there is that difference for 1. For the exponential we get e; for multisets we get ω.
Do you see the connection to what we had before? If we want to think about finite multisets of a set of size n, we could think of that as the sum over k of ((n multichoose k)). And so Weiermann's work tells us that, in some sense, this some is morally equal to ωn. And more generally instead of n we could put in an ordinal α; we wouldn't get out ωα, mind you, but we'd get out something that was the same as exp(α) but with e replaced by ω.
Whereas if we were to sum up nk/k!, why, obviously that is the exponential, exp(n). Which here corresponds for more general ordinal α to exp(α), just left as it is.
But of course we need that third possibility -- 2. Where is that? Well, 2x of course comes from summing up (n choose k), i.e., 2n represents (finite) subsets of n. As in, actual sets, rather than multisets. So if X is a WPO, and we let M'(X) be the WPO of finite sets in X, what is o(M'(X))?
Well, Weiermann didn't compute this. And I haven't attempted to prove it. But I think it's pretty easy to see what it should be -- and I'll bet it's probably not hard to prove if you just go back to Weiermann's proof and modify it appropriately. (EDIT 26 May 2018: I have now in fact proven this.) Specifically, we should get an f' just like f above, except that instead of f(ω0)=f(1)=ω, we get f(ω0)=f(1)=2. So, just like the surreal exponential, but now with 2 instead of e, instead of with ω instead of e. And now the analogy is complete -- assuming this is correct, we would have that, for an ordinal α, the sum of (α choose k) is, morally, the same as exp(α) except with e replaced by 2.
In short, we get this same formula three times -- once with 2, for sets and choose; once with e, for the exponential and divided powers; and once with ω, for multisets and multichoose.
Again, formally much of the above is nonsense. But informally, I think it's really something. 2, e, ω, the three most important bases, corresponding to choose, divided power, and multichoose; with this analogy working in somse sense for whole numbers, for real numbers, and for ordinals. (And maybe one can in some sense make it work for surreals, for all I know, but I'm not going to attempt that, and to my mind there's enough here without that.)
Striking, isn't it?
What do the numbers 2, e, and ω -- as in, the first infinite ordinal -- have in common?
(Yes, those aren't all "numbers" in the same sense. But we'll ignore that for now. And yes they do all make sense as surreal numbers, but I'm not thinking here in terms of surreal numbers but rather being deliberately informal with my use of the word "number". Although, surreal numbers will come in eventually...)
Well, they're all particularly important bases for exponents, of course. But there's more to it than that.
What is ex? Why, it's the sum over k of xk/k!, of course. You know what's approximately xk/k! -- specifically, a little less than it? That's right! It's (x choose k). (Or it's no larger for x≥0, anyway; but I'm basically considering whole numbers as my "prototypical" values of x here.)
And if we take the sum over k of (x choose k), we get... 2x. Well, OK -- certainly this works for whole numbers, but for, say, real numbers it only works if x>-1 (although it still works for all real numbers as an Abel sum). Nonetheless, the point is clear -- whether we consider it for general x or restrict ourselves to whole numbers, the sum of (x choose k) is, morally, 2x.
But there's a third thing in this family. What if instead of (x choose k), we were to use ((x multichoose k)), which is also approximately xk/k!, but a little bit above instead of a little bit below? Now ((x multichoose k)) is equal to (-1)k(-x choose k), so by the binomial theorem, the sum is... 0-x? And indeed, for x<0 this converges to 0, for x=0 we have 1, and for x>0 this series diverges.
What I want to claim is that this 0-x should, in some sense, be interpreted, as ωx. Here I'm kind of cavalierly mixing real numbers and ordinals, I know (and not doing so properly via surreal numbers, just deliberately being informal). Now at this point this clearly sounds crazy. But there's more to it than that.
We turn to the work of Andreas Weiermann on finite multisets in well partial orders. Let X be a well partial order; we can put a well partial order on M(X), the set of finite multisets in X, by saying that S≤T if there is an injection ι:S→T such that ι(s)≥s for all s∈S. Weiermann determined a function f such that, for any well partial order X, o(M(X))=f(o(X)).
What is this f? Well, it's multiplicative, so to define it we need only describe its output on powers of ω. Specifically, we have:
- f(ω0)=f(1)=ω;
- If α>0 is not of the form ε+k for some epsilon number ε and some finite k, then f(ωα)=ωωα;
- And if α is of the form ε+k as described above, then f(ωα)=ωωα+1.
Now, Weiermann didn't mention this in his paper -- quite possibly he didn't notice it at the time, though of course I've since pointed it out to him -- but this is almost exactly the formula for the surreal exponential of an ordinal, as found by Harry Gonshor. (I told you surreals would show up eventually!) The only difference, of course, is that exp(1) is e, not omega. But otherwise they're the same; if α is zero or a limit ordinal (not necessarily a power of omega, note!), we have f(α)=exp(α).
But there is that difference for 1. For the exponential we get e; for multisets we get ω.
Do you see the connection to what we had before? If we want to think about finite multisets of a set of size n, we could think of that as the sum over k of ((n multichoose k)). And so Weiermann's work tells us that, in some sense, this some is morally equal to ωn. And more generally instead of n we could put in an ordinal α; we wouldn't get out ωα, mind you, but we'd get out something that was the same as exp(α) but with e replaced by ω.
Whereas if we were to sum up nk/k!, why, obviously that is the exponential, exp(n). Which here corresponds for more general ordinal α to exp(α), just left as it is.
But of course we need that third possibility -- 2. Where is that? Well, 2x of course comes from summing up (n choose k), i.e., 2n represents (finite) subsets of n. As in, actual sets, rather than multisets. So if X is a WPO, and we let M'(X) be the WPO of finite sets in X, what is o(M'(X))?
Well, Weiermann didn't compute this. And I haven't attempted to prove it. But I think it's pretty easy to see what it should be -- and I'll bet it's probably not hard to prove if you just go back to Weiermann's proof and modify it appropriately. (EDIT 26 May 2018: I have now in fact proven this.) Specifically, we should get an f' just like f above, except that instead of f(ω0)=f(1)=ω, we get f(ω0)=f(1)=2. So, just like the surreal exponential, but now with 2 instead of e, instead of with ω instead of e. And now the analogy is complete -- assuming this is correct, we would have that, for an ordinal α, the sum of (α choose k) is, morally, the same as exp(α) except with e replaced by 2.
In short, we get this same formula three times -- once with 2, for sets and choose; once with e, for the exponential and divided powers; and once with ω, for multisets and multichoose.
Again, formally much of the above is nonsense. But informally, I think it's really something. 2, e, ω, the three most important bases, corresponding to choose, divided power, and multichoose; with this analogy working in somse sense for whole numbers, for real numbers, and for ordinals. (And maybe one can in some sense make it work for surreals, for all I know, but I'm not going to attempt that, and to my mind there's enough here without that.)
Striking, isn't it?
