Skip to main content
edited body
Source Link
Anixx
  • 10.1k
  • 4
  • 39
  • 63
  • $\omega+1 = (2,3,4,5,...)$
  • $\omega \cdot 2 = (2,4,6,8,...)$
  • $\omega^2 = (1,4,9,16,...)$
  • $\omega^\omega = (1,2,27,256...)$$\omega^\omega = (1,4,27,256...)$
  • $\omega+1 = (2,3,4,5,...)$
  • $\omega \cdot 2 = (2,4,6,8,...)$
  • $\omega^2 = (1,4,9,16,...)$
  • $\omega^\omega = (1,2,27,256...)$
  • $\omega+1 = (2,3,4,5,...)$
  • $\omega \cdot 2 = (2,4,6,8,...)$
  • $\omega^2 = (1,4,9,16,...)$
  • $\omega^\omega = (1,4,27,256...)$
Source Link
Mike Battaglia
  • 4.9k
  • 19
  • 43

Surreal numbers, ultrapowers of $\Bbb R$, ordinal-valued functions and the slow-growing hierarchy

Philip Ehrlich's paper “The Absolute Arithmetic Continuum and the Unification of All Numbers Great and Small”, The Bulletin of Symbolic Logic 18 (1) 2012, pp. 1-45. claims as a theorem that, in NBG, $\mathbf{No}$ is the unique class-sized field compatible with Alling's hyperreal axioms. I was inspired to experiment a bit with ultrapowers of $\Bbb R$ to see what sorts of connections might be lying between the surreals and hyperreals, and came across an interesting construction that I'd like to know if has been well-studied before.

One can consider the usual hyperreals $^*\Bbb R$ as equivalence classes of infinite sequences $(n_1,n_2,n_3,n_4,...)$ of real numbers, where the equivalence class is given by a non-principal ultrafilter on $\Bbb N$. Each real embeds into the hyperreals via the diagonal embedding, so that we have $r \to (r,r,r,r,...)$. Addition and multiplication are done pointwise.

Notationally, we will then define $\omega$ as the sequence corresponding to $a(n) = n$, aka $(1,2,3,4,5,...)$, noting that I'm leave out 0 in the set of naturals.

We can use the transfer principle to extend any real function $f(r)$ to a hyperreal function $^*f(^*r) = (f(r_1), f(r_2), f(r_3), ...)$, where the $r_n$ are the entries in the tuple for $^*r$. So by the above, we can immediately get the following:

  • $\omega+1 = (2,3,4,5,...)$
  • $\omega \cdot 2 = (2,4,6,8,...)$
  • $\omega^2 = (1,4,9,16,...)$
  • $\omega^\omega = (1,2,27,256...)$

Since this gives us all finite expressions of polynomials and power towers, this immediately leads to an order-preserving embedding of all ordinals less than $\epsilon_0 = \omega^{\omega^{\omega^{...}}}$ into $^*\Bbb R$, and if we consider the ordinals as being a semiring under commutative addition and multiplication, this embedding is a semiring homomorphism. We can go further:

  • $\omega - 1 = (0,1,2,3,...)$
  • $\omega/2 = (1/2,1,3/2,2,...)$
  • $\sqrt{\omega} = (1,\sqrt{2},\sqrt{3},\sqrt{4},...)$
  • $\log{\omega} = (0,\log{2},\log{3},\log{4},)$,
  • $-\omega = (-1,-2,-3,...)$
  • $\sin(\omega) = (\sin(1), \sin(2), \sin(3), \sin(4)...)$
  • $1/\omega = (1,1/2,1/3,1/4,...)$
  • $\text{round} \left(\frac{\omega}{2} \right) = (1,1,2,2,3,3,...)$

If we define an infinite summation of reals to be its sequence of partial sums, and likewise with infinite products, we get some more nice structure:

  • $\sum_{1}^\infty 1 = \omega$, which is a countably infinite sum of 1's
  • $\sum \Bbb N = 1+2+3+4+... = (1,3,6,10,15,...) = \frac{\omega(\omega+1)}{2}$, with the terms being summed in ascending order
  • $\prod \Bbb N = 1\cdot2\cdot3\cdot4\cdot... = (1,2,6,24,...) = \omega!$, with the terms being multiplied in ascending order

Most of these can be identified with surreal numbers, though $\omega!$ is definitely a new one. Also interesting is that whether or not $\text{round} \left(\frac{\omega}{2} \right) = \frac{\omega}{2}$ is dependent on whether the odd or even indices are in the ultrafilter, so the question of whether $\omega$ is "odd" or "even" is undecidable. Likewise, since it isn't really clear where $\sin(\omega)$ lies on the real line, this also seems very likely to be undecidable.

If we want to be bold and define ordinal tetration, we can embed a few more ordinals as well. Let's identify $^\omega \omega$ with $\epsilon_0$. Then we get:

  • $\omega^{\omega^{\omega^{...}}} =$$^{\omega} \omega = (1,$$^{2}2,$$^{3}3,$$^{4}4,...) = (1,2^2,3^{3^{3}},4^{4^{4^{4}}}...)$, corresponding to $a(n) =$ $ ^{n}n$

All of the ordinals so far, including this one, lead to the same functions given by the slow-growing hierarchy. That is, for every ordinal $\alpha$ that we've encountered so far, its embedding into the ordinals (as constructed by the definition of $\omega$ and the transfer principle) is more or less the same as the sequence in the slow-growing hierarchy $g_\alpha(n)$, with a few insignificant details like how I didn't include zero in the naturals. If there are canonical fundamental sequences for ordinals greater than $\omega^{\omega^{\omega^{\omega^{...}}}}$, then it seems plausible that they could also be recovered in this way too.

So we've recovered all of this beautiful non-Archimedean structure just by defining $\omega = (1,2,3,...)$ and applying the transfer principle. My question, which is admittedly "big picture," is: has this sort of construction been studied before, either in non-standard analysis, or in surreal analysis, or in the study of growth rates of sequences and functions, or anywhere? What is going on, and why do these things sync up so nicely, and is there more information about this sort of connection between these different topics? It seems to touch on a lot of different things, but I'm having trouble finding a launching off point to see the big picture of all of this. Any more information would be much appreciated.