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

Let me offer a counterpoint to François's informative answer and explain how one also can look upon the nonstandard ∈ relation on pseudo finite sets as very rich indeed.

I claim that every countable model of set theory, including every countable model of full ZFC and every countable model of ZFC + large cardinals or whatever kind of countable model of set theory you may have, exists as a substructure of your ultrapower, the nonstandard finite sets HF' = HFω/U. Thus, even though the model HF' thinks everything is finite, there are substructures of HF' that exhibit full ZFC with large cardinals and whatnot. For example, one can find substructures with CH or with ¬CH and so on.

To see this, suppose that M = { an | n ∈ ω } is a set with a binary relation E satisfying that there are no finite cycles for E in M, a consequence of the Foundation Axiom. Define functions fn:ω to HF so that for each k, the structure ⟨ { an | n ≤ k }, E ⟩ is isomorphic to the structure ⟨ { fn(k) | n ≤ k }, ∈ ⟩. For any finite set and acyclic relation, we can always find HF sets so as to copy that finite structure, so such fn exist. What this means is that the map an mapsto [f]U will be an isomorphism of ⟨ M, E ⟩ to its image in HF'. Thus, ⟨ M, E ⟩ is a substructure of HF', as desired.

(More generally, HF' is exhibiting a kind of universal property for countable acylclic directed graphs, and models of set theory are merely instances of this.)

The argument boils down, I suppose, to a kind of saturation property.

-