# structure of the hypernaturals

I want to understand the structure of the hypernaturals a little better. Let me recall the ultraproduct construction of the hypernaturals. On the set of all sequences of $\mathbb{N}$, we define an equivalence relation $(x_n)_n\sim (y_n)_n$ by $\{n~\vert~x_n = y_n\}\in \mathcal{U}$, where $\mathcal{U}$ is some free ultrafilter on $\mathbb{N}$. Anyway, my questions are these:

1) What's the cardinality of $\mathbb{N}^*$?

2) What does the lattice structure look like? More specifically, if I take the equivalence relation $x\sim y$ as $x$ and $y$ are in the same galaxy, then what does the ordered set $\mathbb{N}^*/\sim$ look like? Is it a dense total ordering? Is it isomorphic to something known?

3) It is possible to order-embed some ordinals in $\mathbb{N}^*$. For example, we can put $\omega$ as $(1,2,3,...)$. And $\omega^2$ as $(1,4,9,...)$. How much ordinals can we order-embed in the hypernaturals? Can we order-embed all countable ordinals?

Any good references to answer these questions are also appreciated!

• What do you mean by "in the same galaxy"? – tomasz Dec 14 '13 at 2:36
• @tomasz: Their difference is finite. – Brian M. Scott Dec 14 '13 at 2:39
• It’s always true that $\Bbb N^*$ has an order type $\omega+(\omega^*+\omega)\cdot\theta$, where $\theta$ is a dense linear order without endpoints, so when you mod out by the same galaxy relation, you get $1+\theta$. Not all DLOWE occur; e.g., $\Bbb R$ does not. – Brian M. Scott Dec 14 '13 at 2:40
• I'm not sure right now and I'm going to bed for now, but my guess would be that the answers to all these questions, in general, depend heavily on the choice of $\mathcal U$. Though with some assumptions, like CH, the choice of $\mathcal U$ is immaterial... – tomasz Dec 14 '13 at 2:42

## 2 Answers

This is a partial answer.

This answer shows that $|\Bbb N^*|=2^\omega$.

It’s easy to see that $\Bbb N^*$ must have an order type of the form $\omega+(\omega^*+\omega)\cdot\theta$, where $\theta$ is a dense linear order without endpoints, and hence that $\Bbb N^*/\sim$ must have an order type of the form $1+\theta$. Not all dense linear orders without endpoints can occur as $\theta$; e.g., it’s known that $\Bbb R$ cannot.

• Following what Brian M. Scott says, one sees every countable linear order, and in particular every countable ordinal, can be embedded into $^*\mathbb N$. This is because by a back-and-forth, every countable linear order embeds into every dense-linear-order-without-endpoints. One cannot require these embeddings to be definable in $^*\mathbb N$ though. – Lawrence Wong Dec 14 '13 at 10:17

The hypernaturals have the same cardinality as the hyperrationals by the usual argument. But every real $x$ is infinitely close to a suitable hyperrational: for example, truncate $x$ at decimal rank $H$, where $H$ is a fixed hypernatural.

In fact, this is Martin Davis's favorite construction of the reals (starting with limited hyperrationals; see his 1977 book Davis, Martin Applied nonstandard analysis. Pure and Applied Mathematics. Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1977).

At any rate, it follows that the map from limited hyperrationals to the reals is onto. This shows that the hypernaturals have the cardinality at least of the continuum. The ultraproduct construction you described starts with integer sequences hence no more than the continuum.

All the ordinals

ω, ω + 1, ω + 2, …, ω·2, ω·2 + 1, …, ω2, …, ω3, …, ωω, …, ωωω, …,

are represented in a straightforward fashion by the corresponding hypernaturals using the transfer principle. By the time you get to

ε0

you have a problem that needs to be overcome in a different way. Here you can use saturation to represent $\epsilon_0$ by a hypernatural larger than the countably many ordinals below it.

Moreover, saturation allows one to prove that all countable ordinals are representable in this way. Indeed, if there is a countable ordinal $\sigma$ such that ordinals up to $\sigma$ are not representable in the hypernaturals, then by well-ordering we can assume that $\sigma$ is the smallest such. Since there are countably many ordinals below $\sigma$, saturation on the hypernaturals allows one to find a hypernatural $n_\sigma$ greater than all the hypernaturals representing lower ordinals. Therefore $\sigma$ can also be represented in the hypernaturals in a way that respects the order, yielding a contradiction. Now use a suitable version of AC to find a maximal chain of such representatives in $\mathbb{N}^\ast$ to get the result.

• What is your correspondence between the ordinals below $\varepsilon_0$ and the hypernaturals? – Lawrence Wong Dec 15 '13 at 16:45
• I certainly did not say "correspondence". I am just saying that the ordinals as above can be mapped to hypernaturals using the transfer principle: any such formula is a finite formula that can be applied to a base hypernatural. – Mikhail Katz Dec 15 '13 at 16:49
• Sorry, I did not phrase my question well enough. I think I know why I was confused: by $\omega^\omega$ you (including the person who asked the question?) do not mean the standard $\omega^\omega$ but the $\omega^\omega$ interpreted (in some way) in the hypernaturals. I have always had the standard ordinals in mind, and have also probably misunderstood other parts of the question. – Lawrence Wong Dec 16 '13 at 10:14
• @LawrenceWong, I just posted an answer on representing countable ordinals that uses saturation instead of back-and-forth. Perhaps this can be simplified even further. – Mikhail Katz Dec 16 '13 at 13:22