Peculiar Question on Unlimited Hypernaturals

Consider the usual ultra-power construction of the hyperreals $^*\mathbb R$ with ultrafilter $\mathcal F$. Let $K = [k_n] \in ^*\mathbb N$ be an unlimited hypernatural. My question is does there always exists a (strictly?) monotonically increasing sequence $(a_n)$ such that also $[a_n] = K$. And if this is the case, can $(a_n)$ be chosen as a sub-sequence of $(k_n)$?

I came up with this question after making the following observation: Consider the strictly monotonically increasing sub-sequence $(k_{n_m})$ constructed by setting $n_1 = 1$ and $n_{m+1} = \min\{n\in\mathbb N \mid k_n >k_{n_i} \text{ for all } i=1\ldots m\}$.

E.g. for the sequence $$1,3,2,4,3,6,5,7,6,\ldots$$ generated by alternatingly adding $2$ and substracting $1$, the subsequence would be $1,3,4,6,7,\ldots$ Now let $A = \{n_m \mid m\in\mathbb N\}$. Then there are 2 possibilities: either $A\in\mathcal F$ or $A^c = \mathbb N \setminus A \in\mathcal F$. In the first case we can simply set $a_n = k_n$ if $n\in A$, and fill up the gaps such that $(a_n)$ is monotonially increasing, e.g. in the example sequence we could choose $$1,3,3,4,4,6,6,7,7,\ldots$$

In the latter case, we would repeat the construction, ignoring any terms in $A$ giving us again a strictly monotonically increasing sub-sequence with indices in $B\subseteq A^c$ such that $A^c = B \uplus B^c$ (with $B^c = A^c \setminus B$). Then either $B$ or $B^c$ must be in $\mathcal F$ (standard property of ultra-filters), at which point we can apply the same arguments as above again. It seems plausible that this iterative process should stop at some point since after every iteration we ignore another infinite number of terms (maybe Zorn's Lemma could help?).

You certainly can't make $$(a_n)$$ be strictly monotonic, since that would mean that $$a_n\geq a_0+n$$ for all $$n$$. So, for instance, if $$k_n=\lfloor\sqrt{n}\rfloor$$ we cannot choose any such $$a_n$$, since for any value of $$a_0$$ we have $$k_n for all sufficiently large $$n$$.

The non-strict case is much more subtle. First, the answer is no for some choices of ultrafilter. Consider a sequence $$k_n$$ defined as follows. For $$m^2, $$k_n$$ goes through the integers from $$m^2+1$$ to $$(m+1)^2$$ in reverse order (so $$k_{m^2+1}=(m+1)^2$$, $$k_{m^2+2}=(m+1)^2-1$$, and so on). Let $$S$$ be the set of subsets of $$\mathbb{N}$$ on which this sequence $$(k_n)$$ is increasing. If $$A\in S$$, then $$A$$ contains at most one point in the interval $$(m^2,(m+1)^2]$$ for each $$m$$. Since the lengths of these intervals are unbounded, it follows that no finite union of sets in $$S$$ can cover all of $$\mathbb{N}$$. Thus the set of complements of elements of $$S$$ generate a proper filter on $$\mathbb{N}$$, which can be extended to an ultrafilter $$\mathcal{F}$$.

Now I claim that if we construct the hypernaturals using this ultrafilter $$\mathcal{F}$$, there is no increasing sequence which is equivalent to $$(k_n)$$. Indeed, by our choice of $$\mathcal{F}$$, if $$a_n=k_n$$ for all $$n\in A$$ for some $$A\in\mathcal{F}$$, then $$k_n$$ is not increasing on $$A$$ and hence $$a_n$$ cannot be increasing either. On the other hand, the sequence $$(k_n)$$ goes to $$\infty$$, so it must represent an unlimited hypernatural.

So the question remains: are there any ultrafilters for which the answer is yes? It turns out that this is independent of ZFC. First, by a theorem of Shelah, it is consistent with ZFC that no ultrafilter is a P-point, meaning that for any nonprincipal ultrafilter $$\mathcal{F}$$, there exists a partition of $$\mathbb{N}$$ into sets $$A_i$$ with $$A_i\not\in\mathcal{F}$$ for all $$i$$ such that for any $$B\in\mathcal{F}$$, $$B \cap A_i$$ is infinite for some $$i$$. Now given an ultrafilter $$\mathcal{F}$$ and such a partition $$\mathbb{N}=\bigcup A_i$$, define $$k_n=i$$ for $$n\in A_i$$. Since $$A_i\not\in\mathcal{F}$$ for all $$i$$, $$(k_n)$$ represents an unlimited hypernatural number with respect to $$\mathcal{F}$$. But for any $$B\in\mathcal{F}$$, there is some number which repeats infinitely often even after restricting $$(k_n)$$ to $$B$$, so $$(k_n)$$ cannot be equivalent to an increasing sequence (it is not even equivalent to a sequence that goes to $$\infty$$!). So it is consistent that the answer is no for all ultrafilters.

On the other hand, if the ultrafilter $$\mathcal{F}$$ is a Ramsey ultrafilter, the answer is yes. The existence of Ramsey ultrafilters is consistent with ZFC (for instance, it follows from the continuum hypothesis). There are several equivalent definitions of Ramsey ultrafilters, but the easiest to use here is the following: a nonprincipal ultrafilter $$\mathcal{F}$$ is Ramsey if for any set $$R$$ of two-element subsets of $$\mathbb{N}$$, there is a set $$A\in\mathcal{F}$$ such that either for all distinct $$x,y\in A$$, $$\{x,y\}\in R$$, or else for all distinct $$x,y\in A$$, $$\{x,y\}\not\in R$$. In this case, given a sequence $$(k_n)$$, let $$R$$ be the set of pairs $$\{x,y\}$$ such that $$k_x$$ and $$k_y$$ are in the correct order (that is, $$x iff $$k_x). For $$A\in\mathcal{F}$$, if $$\{x,y\}\not\in R$$ for all distinct $$x,y\in A$$, that means that $$(k_n)$$ is decreasing on $$A$$, which is impossible if $$(k_n)$$ represents an unlimited hyperreal. So there must be $$A\in\mathcal{F}$$ such that $$\{x,y\}\in R$$ for all distinct $$x,y\in A$$, which means the restriction of $$(k_n)$$ to $$A$$ is increasing. We can then define $$(a_n)$$ to agree with $$(k_n)$$ on $$A$$ and interpolate in between to be increasing on all of $$\mathbb{N}$$.

• Thank you very much for your response Eric! What a brilliant argument. – Hyperplane Jun 3 '17 at 19:47
• All the good ultrafilters only show up on ZFC blackmarkets... – nombre Jun 3 '17 at 22:04

A slightly more elementary answer: the answer is negative in general because of the following nice characterisation of P-point ultrafilters: an ultrafilter is a P-point if and only if every infinitesimal in $\mathbb{R}^{\mathbb N}/\mathcal F$ is representable by a sequence tending to zero. Thus if the ultrafilter happens not to be a P-point (a property indepedent of ZFC), then there is an "inaccessible" infinitesimal $\epsilon$, i.e., not representable by a sequence tending to zero. In particular, the reciprocal $\frac{1}{\epsilon}$ cannot be represented by a monotone sequence. More details on inaccessible infinitesimals can be found in this article.

• To be honest I was quite surprised that the answer to this question goes so deep into the logic/model theoretic aspect. Coming from an applied maths background myself I had been drawing this picture in my mind that unlimited hyperreals correspond to the growth rates of the sequences generating them. If these inaccessible entities exist however, this intuition goes out of the window. – Hyperplane Jun 4 '17 at 14:34
• @Hyperplane, a sequence going to infinity definitely defines an infinite hyperreal in the ultrapower construction, so your intuition can stay indoors :-) Also, modulo mild foundational material, you can assume that a P-point ultrafilter exists, and then every infinite number will be represented by a sequence tending to infinity. – Mikhail Katz Jun 4 '17 at 15:28
• I would add that the real problem is not with infinitesimals but with the axiomatic system ZFC itself, which was designed specifically to exclude infinitesimals, which indeed makes them a bit tricky to put back in. Friendlier axiomatic foundations were developed by Edward Nelson and are known as Internal Set Theory. – Mikhail Katz Jun 4 '17 at 15:32