3

It is interesting that to prove the transfer principle for the definable hyperreal field, one requires no more choice than for proving, for instance, the countable additivity of the Lebesgue measure. The usual ultrapower construction of a hyperreal field $\mathbb{R^N}/\mathcal{F}$ is not functorial due to the dependence on $\mathcal{F}$. Kanovei and Shelah developed a functorial alternative to this, by providing a construction of a definable hyperreal field.

The idea is as follows. One starts with the set (possibly empty; this will depend on the background model of set theory) of free ultrafilters $\mathcal{F}$ on $\mathbb{N}$ parametrized by the least ordinal that can map surjectively onto such an $\mathcal{F}$. One orders them lexicographically. One introduces a tensor product operation that enlarges the index set to Cartesian products of finitely many $\mathbb{N}$. One exploits the tensor product to organize the various ultrapowers into a direct limit, whose elements are ``threads'' generated as unions. Since finitely many elements already coalesce at a finite stage in the direct limit, the proof of the transfer principle only uses the axiom of countable choice (ACC).

The Kanovei-Shelah (KS) construction can therefore be viewed as a functor which, given a model of set theory, produces a hyperreal field. A transfer theorem here can apparently be proved using only the axiom of countable choice (ACC). It would be interesting to separate the issue of the satisfaction of transfer from the issue of properness of the extension.

Question. What would be a collection of minimal foundational conditions to guarantee that (1) the KS construction goes through, and (2) the resulting extension satisfies a transfer principle?

This seems of philosophical interest because apparently very little is required here, contrary to popular belief that the full power of AC is needed to make transfer work. The latter may be true in the model-theoretic approach using the compactness theorem, but passing via ultrapowers seems to reduce the foundational requirements. Whatever model of ZF+ACC one starts with, one hopes to get a KS hyperreal field that will satisfy transfer. Here some models will be proper extensions and others not, but the proof should work in general. The point is to prove transfer without committing oneself to any free ultrafilters yet. To guarantee that the extension is proper of course requires an ultrafilter.

The KS construction requires in addition to ZF, the existence of a least ordinal mapping surjectively to $\mathcal{P}(\mathbb{N})$. Such an ordinal is used in the KS construction. The minimality of the ordinal apparently serves to ensure that the construction is definable, by virtue of the uniqueness of the said ordinal. Once one has the KS extension, transfer apparently follows from ACC, or alternatively from WO since ACC is apparently only applied to subsets of $\mathcal{P}(\mathbb{N})$.

Mikhail Katz
  • 15,081
  • 1
  • 50
  • 119
  • @AndreasBlass could you possibly comment on this? – Mikhail Katz Jun 29 '16 at 16:23
  • 2
    The answer to your question is in the last sentences, once you realize that "the existence of a least ordinal mapping surjectively to $\mathcal{P}(\mathbb{N})$" is equivalent to the existence of a wellordering of $\mathcal{P}(\mathbb{N})$. ACC is a red herring. – François G. Dorais Jun 30 '16 at 11:48
  • @FrançoisG.Dorais, I agree with the first part of your comment but reserve judgment as to the second before I believe that the well-ordering is really sufficient to prove transfer. Can you give a source for this in the literature? – Mikhail Katz Jun 30 '16 at 12:19
  • Well, I'm not sure. Kanovei and Shelah seem to iterate their construction $\omega_1$ times to get countable saturation, I am neither sure you want this nor am I sure a wellordering for $\mathcal{P}(\mathbb{N})$ is sufficient. – François G. Dorais Jun 30 '16 at 23:09

2 Answers2

3

Since ACC is only applied to subsets of $\mathcal{P}(\mathbb{N})$ - that is, to families of sets of reals - the answer is that only the well-ordering of $\mathbb{R}$ is needed. Indeed, if $\mathbb{R}$ is well-ordered by $\prec$, then given any family of nonempty sets of reals $F=\{A_i: i\in I\}$, we may define a choice function for $F$ by picking the $\prec$-least element of each $A_i$: $$f(i)=r\iff [r\in A_i\wedge\forall s\in A_i(s\not=r\implies r\prec s)].$$ So no additional choice is needed.

Meanwhile, the following are equivalent over ZF (in fact, over much less):

  • (i) $\mathbb{R}$ is well-orderable.

  • (ii) There is some ordinal $\alpha$ which surjects onto $\mathbb{R}$.

  • (iii) There is a least ordinal $\alpha$ which surjects onto $\mathbb{R}$.

Proof: (i) implies (ii): every well-ordered relation on a set is in bijection with some ordinal.

(ii) implies (iii): every nonempty set of ordinals has a smallest element; apply this to the set of ordinals surjecting onto $\mathbb{R}$.

(iii) implies (i): Suppose $\alpha$ surjects onto $\mathbb{R}$ via $f$ (we need not assume $\alpha$ is the least such - this is equally a proof from (ii), which is trivially implied by (iii)). For $r\in\mathbb{R}$, let $g(r)$ be the least $\beta<\alpha$ such that $f(\beta)=r$; $g(r)$ is always defined since any set of ordinals has a least element. Now let $r\prec s$ iff $g(r)<g(s)$; it is easy to see that this is a well-ordering on $\mathbb{R}$.

Noah Schweber
  • 18,932
  • I don't fully understand why in the proof of transfer for ultrapowers, AC will only be used for subsets of P(N). Could you elaborate? – Mikhail Katz Jun 30 '16 at 14:05
  • Also, in which foundational framework precisely are the three assertions (i), (ii), and (iii) equivalent? – Mikhail Katz Jun 30 '16 at 14:06
  • @MikhailKatz Re your second comment, see my edit; ZF is more than enough (indeed the only nontrivial fact which is used is that any well-ordered relation on a set is isomorphic to an ordinal, which I think requires replacement. EDIT: originally I also thought foundation was needed, but now I realize that's false.). Re: your first comment, I was taking the last sentence of your post at face value: ". . . since ACC is only applied to subsets of $\mathcal{P}(\mathbb{N})$." I am not very familiar with the KS construction myself. – Noah Schweber Jun 30 '16 at 14:08
  • You can take it at face value because earlier in the sentence I already mentioned the adverb "apparently". I added another one to make things even clearer. – Mikhail Katz Jun 30 '16 at 14:09
  • I will try to add a summary of the construction. It really isn't that complicated. – Mikhail Katz Jun 30 '16 at 14:10
  • @MikhailKatz I edited my comment - foundation is not, in fact, needed, since the fact I mention follows just from replacement (but do you care about these more technical distinctions, or is equivalence over ZF enough?). Do the arguments I've posted make sense? Meanwhile, re: ACC, I think this just boils down to the fact that in the existential case of Los' Theorem (the only case that requires choice), I need to pick witnesses from the ultrafactors, and this amounts to picking elements from sets of reals. – Noah Schweber Jun 30 '16 at 14:14
  • ZF is fine. Can you elaborate a bit why picking witnesses from ultrafactors "amounts to" picking elements from sets of reals? These ultrafactors can't have cardinalty more than $c$ but why is that enough? They are not literally subsets of the reals. – Mikhail Katz Jun 30 '16 at 14:18
  • @MikhailKatz As I said, I don't know the KS construction so I can't be sure this is accurate, but: what I was referring to was the standard proof of transfer for a structure of the form $\prod_{i\in I}\mathbb{R}/\mathcal{U}$. In the proof of Los' Theorem, the crucial step is: suppose $\exists x\varphi(x, a_i)$ holds at $\mathcal{U}$-many factors (where $a_i$ is a real from the $i$th copy of $\mathbb{R}$); and inductively every formula simpler than $\exists x\varphi$ transfers. To show $\exists x\varphi(x, (a_i)_{i\in I})$ holds in the ultrapower, we need to construct (cont'd) – Noah Schweber Jun 30 '16 at 14:21
  • But that's only the ultrapower of the reals. If you want to get a meaningful transfer applying at least to functions (which involve ordered pairs, which already get you to the fourth level in the superstructure) you need more. – Mikhail Katz Jun 30 '16 at 14:24
  • a sequence $(b_i){i\in I}$ of reals such that $\varphi(b_i, a_i)$ holds for $\mathcal{U}$-many $i$. So for each $i$, we look at the set $B_i$ of reals defined as: $B_i$ is the set of $x$ satisfying $\varphi(x, a_i)$ if such an $x$ exists, and $B_i={7}$ (say) otherwise. Now we use the well-ordering of reals to pick representatives (or ACC if $I$ is countable); this defines our sequence $(b_i){i\in I}$. Of course, I don't know that this is the same reasoning underlying the KS construction, but that's my guess. – Noah Schweber Jun 30 '16 at 14:24
  • @MikhailKatz I thought that in the usual ultrapower construction used for nonstandard analysis, we just expand $\mathbb{R}$ with a symbol for every function? If so, the ultrafactors are still $\mathbb{R}$s, and everything I've said still goes through (the additional symbols are just used in the non-logical part of $\varphi$). – Noah Schweber Jun 30 '16 at 14:25
  • Thanks, let me think about it. I was thinking in terms of the bounded ultrapower for the superstructure. – Mikhail Katz Jun 30 '16 at 14:26
  • No problem; let me stress again, though, that I haven't read KS, so I have no idea if what I've written is accurate to the specific case you care about. (I'm traveling, and I don't have time to read the KS paper now, so for now I'll leave my answer as-is, that is, modulo your "apparently". Maybe someone else can resolve this, or I will eventually get a chance to read KS.) – Noah Schweber Jun 30 '16 at 14:27
  • 2
    I may add that for the K-Shelah construction to really yield a proper elementary extension of the reals $R$, it suffices to assume ZF (sans AC) plus countable AC for sets of reals plus there is a free ultrafilter over $N$ with a wellorderable base. Note that these assumptions do not imply the wellorderability of $R$. To define a model which demonstrates this let $M$ be an $\omega_2$-iterated Sacks extension of $L$ and let $M'$ be the hereditarily real-ordinal definable sets in $M$. – Vladimir Kanovei Jul 02 '16 at 17:46
1

Fairly minimal requirements seem to be ZF plus countable choice plus existence of a free ultrafilter with well-orderable base, as noted by Vladimir in a comment above. See also this answer.

Mikhail Katz
  • 15,081
  • 1
  • 50
  • 119