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,4,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.

• Aside: that infinite sum is better thought of as $\sum_1^\omega 1 = \omega$. – user13113 Jan 4 '18 at 20:10

This kind of analysis is very well understood in ultrapowers, and one often sees this kind of thinking with ultrapowers, where one performs calculations with the representing function for an object. What you call $\omega$ is in fact just a particular nonstandard natural number in $\mathbb{N}^*$, and one may perform the same kind of calculations with any nonstandard number. That is, if you had used some other sequence than $(1,2,3,\ldots)$, then you could have done the same kind of calculations.

To probe a bit further, one might ask: is your $\omega$ prime in the nonstandard natural numbers $\mathbb{N}^*$? Well, the answer depends on the ultrafilter $\mu$ that you use in your ultrapower. If $\mu$ happens to concentrate on the set of prime numbers, then it follows by the Los theorem that $\omega$ will be a prime non-standard number. But if $\mu$ concentrates on the composite numbers, then $\omega$ will be composite. More generally, $\omega$ has all and only the properties that hold on a $\mu$-large set, for if $\mu$-almost every $n$ has property $p$, expressible in the language with respect to which you took the ultrapower, then by Los it follows that $\omega$ also has property $p$, and conversely.

So the properties of your element $\omega$ are tightly connected with the particular ultrafilter $\mu$ that you use, and indeed, those properties determine $\mu$, since every set of natural numbers $A\subset\mathbb{N}$ can be regarded as a property and the situation will be that $\omega\in A^*$ just in case $A\in\mu$. This is the sense in which $\omega$ has property $A$ just in case $\mu$ concentrates on $A$.

Actually, there is a strong sense in which your construction has not really determined a specific value for $\omega$. Consider any ultrapower $\mathbb{N}^*=\mathbb{N}^{\mathbb{N}}/\nu$ of $\mathbb{N}$ by any ultrafilter $\nu$, and let $N$ be any nonstandard natural number in this version of $\mathbb{N}^*$. Then I claim that there is another ultrafilter $\mu$, whose ultrapower $\mathbb{N}^{\mathbb{N}}/\mu$ maps elementarily into the original $\mathbb{N}^*$, but where the $\omega$ as determined by $\mu$ maps exactly to $N$, the original arbitrary nonstandard number $N$. To build $\mu$, observe simply that $N=[f]_\nu$ for some function $f:\mathbb{N}\to\mathbb{N}$, and let $\mu=f*\nu$, so that $X\in\mu\iff f^{-1}(X)\in\nu$. It follows that $[g]_\mu\mapsto [g\circ f]_\nu$ is an elementary embedding of the ultrapower by $\mu$ into the ultrapower by $\nu$, and furthermore since $[id]_\mu\mapsto [f]_\nu$, we see that the $\omega$ defined with respect to $\mu$ maps to $N$, as I claimed. In this sense, what you call $\omega$ is simply an arbitrary nonstandard natural number, whose properties are left to be determined by the particular ultrafilter that you use to form the ultrapower.

• Thank you for your response! I see what you mean about $\omega$ being undetermined. I don't know whether this makes sense or is just an errant intuition of mine, but I've been thinking of it as though that its primeness vs compositeness as something which is "undecidable" simply given the basic axioms of the hyperreals, e.g. that you have these sequences of reals with "an ultrafilter" on them without specifying anything beyond that. (cont'd) – Mike Battaglia Feb 8 '14 at 18:36
• You can then add the axiom that $\omega$ is composite if you like, which narrows down the set of ultrafilters you can choose from; the different ultrafilters then become like different "models" of the theory in some sense in which every proposition about $\omega$ has a definitive answer. (cont'd again) – Mike Battaglia Feb 8 '14 at 18:40
• I was quite curious if an analogous situation might exist with the surreals, e.g. the primeness of $\omega$ is simply undecidable and you can choose your own adventure regarding it. Or, alternatively, perhaps those things really are decidable in the surreals, with $\omega$ being decided prime by some undeniably natural way, and then a field embedding of $^*\Bbb R$ into them which maps $[(1,2,3,...)] \to \omega$ would decide some equally natural ultrafilter or set of ultrafilters which makes it all work out. Just a thought. – Mike Battaglia Feb 8 '14 at 18:51
• Isn't $\sqrt{\omega}$ in the omnific integers? – Mike Battaglia Feb 9 '14 at 0:06
• I'm pretty sure it's a theorem that r·ω is an omnific integer for any real r, but either way it's definitely true that ω/2 is an omnific integer. – Mike Battaglia Feb 9 '14 at 23:27

Alec, I'm afraid your construction does not work. You claim you obtain the surreals by forming the Dedekindean Completion of what you call the surrationals. However, since No--the surreals-- is not Dedekindean Complete, your claim is false. In fact, the Dedekindean Completion of No has "cardinality" $2^{\aleph_{On}}$, which is not even well-defined in NBG (with Global Choice).

No is a (fully) saturated model for the theory of real-closed ordered fields and it has long been known that no such model is Dedekindean complete. On the other hand, there are real-closed fields that are $\kappa$-saturated but not (fully) saturated that are Dedekindean Complete. See, for example, H. J. Keisler and J. Schmerl Making the hyperreal line both saturated and complete. J. Symbolic Logic 56 (1991), no. 3, 1016–1025.

• Ah, my mistake! Thank you for catching this -- I originally built my theory in MK which possibly avoided this issue without my knowledge. Is there any method obvious to you which would 'fill out' this field of fractions in the correct manner? If you would like to email me regarding this, please feel free to. – Alec Rhea Jul 28 '17 at 3:51
• Alec, I'm afraid the same problem arises in MK. If I can think of anything helpful, I'd be happy to email you. – Philip Ehrlich Jul 28 '17 at 3:56
• To produce a specific bridgeable class cut in the surreals with no least upper bound, one can successively cut an interval in two, alternately taking the upper or the lower half for the next interval, and at limit stages, taking the interval determined by the surreal filling the set-sized cut determined at that stage and continuing. The resulting cut is bridgeable, since the sizes of the intervals goes to 0, but it is not filled in the surreals. And no set of surreals ever has a least upper bound. So it is not Dedekindian complete. – Joel David Hamkins Jul 28 '17 at 11:12
• Fascinating distinctions -- would it possibly work to real-close the field of fractions, i.e. make its first-order theory identical to the real numbers? I feel like this isn't 'enough' in the sense that we'll just end up with a proper class sized version of $\overline{\mathbb{Q}}$. – Alec Rhea Jul 29 '17 at 5:50

(beginning of post deleted due to a missed error, thanks to Philip Ehrlich)

It is possible to extend the usual hyperoperation sequence $\mathcal{H}_\omega$ on $\mathbb{N}$ to a recursive sequence of operations $\mathcal{H}$ on $O_n$, with the following result:

$$\mathcal{H}_{_\Omega}(\alpha,\beta)=\begin{cases} \mathcal{S}\alpha, & \text{if} \ \Omega=0. \\ \alpha, & \text{if} \ \Omega=1 \ \text{and} \ \beta=0. \\ \mathcal{S}\alpha,& \text{if} \ \Omega=1 \ \text{and} \ \beta=1. \\ 0, & \text{if} \ \Omega=2 \ \text{and} \ \beta=0. \\ \alpha, & \text{if} \ \Omega=2 \ \text{and} \ \beta=1. \\ 1, & \text{if} \ \Omega\geq3 \ \text{and} \ \beta=0. \\ \alpha, & \text{if} \ \Omega\geq3 \ \text{and} \ \beta=1. \\ \mathcal{H}_{_{\Omega-1}}\big(\alpha,\mathcal{H}_{_\Omega}(\alpha,\beta-1)\big), & \text{if} \ \Omega=\mathcal{S}\bigcup\Omega \ \text{and} \ 1<\beta=\mathcal{S}\bigcup\beta. \\ \bigcup_{\delta<\beta}\mathcal{H}_{_\Omega}(\alpha,\delta), & \text{if} \ \Omega=\mathcal{S}\bigcup\Omega \ \text{and} \ \ 1<\beta=\bigcup\beta . \\ \bigcup_{\rho<\Omega}\mathcal{H}_{_\rho}(\alpha,\beta), & \text{if} \ 0\neq\Omega=\bigcup\Omega \ \text{and} \ 1<\beta=\mathcal{S}\bigcup\beta. \\ \bigcup_{\rho<\Omega}\bigcup_{\delta<\beta}\mathcal{H}_{_\rho}(\alpha,\delta), & \text{if} \ 0\neq\Omega=\bigcup\Omega \ \text{and} \ 1<\beta=\bigcup\beta. \\ \end{cases}$$

This 'transfinite hyperoperation sequence' is a very 'large' object in the sense that each hyperoperation in the sequence is a proper class, but it is well defined under the appropriate reflection principle or under ETR and satisfies nice relations like $\mathcal{H}_4(\omega,\omega)=^\omega\omega=\omega^{\omega^{\omega^{\dots}}}$ in your question, and $\mathcal{H}_5(\omega,\omega)=^{^{^{\dots}\omega}\omega}\omega$, so on and so forth. I hope this assists with understanding what is happening with the hyperoperation-related piece of the questions you've mentioned, as I find them fascinating as well!