# Behavior of externally-infinite elements in ultrapowers of $\langle HF,\epsilon\rangle$

Consider the structure $\langle HF,\epsilon\rangle$ (the hereditarily finite sets with the epsilon-relation). An ultrapower of this structure will have externally-infinite elements -- elements not generated by a finite number of applications of the (definable) singleton+binary-union operations.

Can anybody give me a starting point for literature on the properties of these externally-infinite sets?

Thanks!

-
Note that $(HF,{\in})$ is biinterpretable with $\mathbb{N}$. Ultrapowers of $\mathbb{N}$ are very well studied in non-standard arithmetic. –  François G. Dorais Mar 16 '10 at 23:55
True, HF is biinterpretable with N, but I'm pretty sure their respective ultrapowers aren't once you start adding names for the new nonstandard elements. –  Adam Mar 17 '10 at 0:39
They are! The interpretation is first-order, which is preserved by ultrapowers. –  François G. Dorais Mar 17 '10 at 0:58
I don't necessarily want to limit my attention to first-order properties -- for example I care about things like: cardinality, order type, well-foundedness, and so forth. –  Adam Mar 17 '10 at 5:16
Ah, it appears that those might be preserved as well... see my comment on François' answer. This is starting to become more clear. –  Adam Mar 17 '10 at 5:29

As I pointed out in the comments, $(HF,{\in})$ is biinterpretable with $\mathbb{N}$, which means that the corresponding ultrapowers are biinterpretable too. So you will find all you need in the vast literature on nonstandard arithmetic.

A nice interpretation of $(HF,{\in})$ in $\mathbb{N}$ is given by defining $m \in n$ if the $m$-th binary digit of $n$ is $1$. For example, here are the first few coded sets:

• $0$ codes $\varnothing$
• $1 = 2^0$ codes $\{\varnothing\}$
• $2 = 2^1$ codes $\{\{\varnothing\}\}$
• $3 = 2^0 + 2^1$ codes $\{\varnothing,\{\varnothing\}\}$

You can similarly interpret the ultrapower $HF^\omega/\mathcal{U}$ in the ultrapower $\mathbb{N}^{\omega}/\mathcal{U}$. If $\bar{m},\bar{n} \in \mathbb{N}^\omega$, the $\bar{m}$-th binary digit of $\bar{n}$ is first interpreted term-by-term giving a sequence $\bar{b} \in \{0,1\}^\omega$ where each $b_i$ is the $m_i$-th binary digit of $n_i$. In $\mathbb{N}^\omega/\mathcal{U}$, $\bar{b}$ is evaluated as either $0$ or $1$, depending on which value occurs $\mathcal{U}$-often. This value tells you whether $\bar{m} \in \bar{n}$ according to the above interpretation.

Of course, you can simply compute things directly. Given sequences $\bar{x},\bar{y} \in HF^\omega$, we have $\bar{x} \in \bar{y}$ in the ultrapower $HF^\omega/\mathcal{U}$ if and only if $\{i : x_i \in y_i \} \in \mathcal{U}$. This gives exactly the same structure as interpreting sets in $\mathbb{N}^\omega/\mathcal{U}$ as described above.

It just occurred to me that you may be looking for a more set-theoretic description of the nonstandard elements of $HF^\omega/\mathcal{U}$.

The wellfounded part of $HF^\omega/\mathcal{U}$ is precisely $HF$ and no more. A sequence $\bar{x} \in HF^\omega$ will represent a wellfounded set in $HF^\omega/\mathcal{U}$ if and only if it has bounded rank mod $\mathcal{U}$, i.e. $\{i : \mathrm{rk}(x_i) < n\} \in \mathcal{U}$ for some $n < \omega$, in which case it will be constant mod $\mathcal{U}$ since there are only finitely many sets of rank less than $n$. If this is not the case, then $\langle\mathrm{rk}(x_i)\rangle$ evaluates to a nonstandard ordinal $N$ in $HF^\omega/\mathcal{U}$. This means that in $HF^\omega/\mathcal{U}$, we can (externally) find an infinite descending ${\in}$-chain starting with the evaluation of $\bar{x}$. So it is impossible to describe the evaluation of $\bar{x}$ as a real set.

Without peering into the depths of the nonstandard ${\in}$ relation, there is not much to elements of $HF^{\omega}/\mathcal{U}$. Every element of $HF^\omega/\mathcal{U}$ has a bijection with a (possibly nonstandard) ordinal, so it looks exactly like an internal initial segment of the nonstandard ordinals.

-
Thanks François; the third paragraph of your answer is fascinating (I'd seen the stuff before it). If I understand correctly, does this mean that whenever structure A has a definable substructure which is isomorphic to B, then for any ultrafilter U it will be the case that A/U has a definable substructure isomorphic to B/U? I know the preceding is true if you replace "isomorphic" with "elementarily equivalent". –  Adam Mar 17 '10 at 5:29
Also, regarding your second-to-last paragraph, why is it that $HF^\omega/U$ has no well-founded elements with (externally-)infinitely many members? For example, why can't there be some element sort of like $\omega$ in the ultrapower model which has every natural number as an element? HF satisfies the first-order statement "there is no infinite set", but that's phrased as "for any set there does not exist an injection from it to a proper subset of itself" so it might be that the ultrapower model is simply missing those injections. –  Adam Mar 17 '10 at 5:45
Yes, if the definition is first-order then the same definition will give a structure isomorphic to B/U inside A/U. –  François G. Dorais Mar 17 '10 at 12:01
This is what the next-to-last sentence describes. If $x$ has nonstandard rank $n$, then for each you can internally find an $n$-sequence $s$ such that $s(n-1) = x$ and $s(i-1) \in s(i)$ for $i < n$. Then $x = s(n-1) \ni s(n-2) \ni s(n-3) \ni \cdots$ shows that membership is not wellfounded below $x$. –  François G. Dorais Mar 17 '10 at 12:12
Adam, it may help you to imagine that you didn't just take the ultrapower of HF, but actually took the ultrapower of the entire set-theoretic universe V, forming V^omega/U. All ultrapowers of individual structures A, B exist as points A^omega/U, B^omega/U in this structure, and since we have Los for the big set-theroetic ultrapower, any expressible property about A, B in set theory turns into the corresponding statement about their ultrapowers. In particular, if B is a definable substructure A, even second order (!), then B^omega/U will be the corresponding definable substructure of A^omega/U. –  Joel David Hamkins Mar 17 '10 at 13:38