(How) do theories of higher-order arithmetic have non-$\beta$ models?

Question

I was reading this question about $\beta$-models of $\mathsf{NFU}$ and noticed that models theories of higher-order arithmetic can be or not be $\beta$-models. My understanding is that a $\beta$-model is a model where $\in$ really is a well-order. Well-orderness is a second-order property, so a given model might have it or might not. However, higher-order theories of arithmetic are (at least) second-order theories, so I'm wondering how you'd end up with a non-$\beta$ model of a theory of higher order arithmetic.

Most set theories have a single non-logical predicate $\in$. Even a hypothetical set theory that axiomatizes, say, the unordered pair $\{\cdot, \cdot\}$ and unary union $\cup(\cdot)$ still has a single obvious candidate for "$\in$".

The Wikipedia article on second-order arithmetic has a relation symbol $<$, which is a well-order in the standard model of arithmetic. I'm assuming $\beta$-ness refers to whether $<^M$ is a well-order for some model $M$ when talking about arithmetic.

The version of second-order arithmetic has a second-order induction scheme... which presumably can prove that all sections of the first-order domain $\mathbb{N}$ are Kuratowski-finite ... I'm struggling to see how we could end up with a non-$\beta$ model (assuming standard semantics).

Answer 1

"$\beta$-model" is really a term which lives most happily in the context of theories of second-order arithmetic such as $\mathsf{Z_2}$ or $\mathsf{RCA_0}$, so I'll start by treating it there. Note that despite the terminology, theories of second-order arithmetic are first-order theories (yes, this is really annoying).

Suppose I have a structure $\mathcal{M}$ in the (first-order!) language of second-order arithmetic. This $\mathcal{M}$ consists of:

• A numbers sort $\mathbb{Num}_\mathcal{M}$.

• A sets sort $\mathbb{Set}_\mathcal{M}$.

• Some structure on the above sorts - distinguished elements $0_\mathcal{M},1_\mathcal{M}\in\mathbb{Set}_\mathcal{M}$, binary functions $+_\mathcal{M},\times_\mathcal{M}$ on $\mathbb{Num}_\mathcal{M}$, a binary relation $<_\mathcal{M}\subseteq\mathbb{Num}_\mathcal{M}\times\mathbb{Num}_\mathcal{M}$, and a binary relation $\in_\mathcal{M}\subseteq\mathbb{Num}_\mathcal{M}\times\mathbb{Set}_\mathcal{M}$. (There's some flexibility here of course.)

• We'll additionally require that $\mathcal{M}$ satisfy some basic properties (e.g. extensionality, commutativity of $+$ and $\times$, etc.). If you're familiar with the basic terminology of reverse math, it's more than enough for what follows to demand that $\mathcal{M}\models\mathsf{RCA_0}$; if you're not familiar with that, just assume that $\mathcal{M}$ isn't too weird. Finally, it will be convenient to assume that elements of $\mathbb{Set_\mathcal{M}}$ literally are subsets of $\mathbb{Num}_\mathcal{M}$ and that $\in_\mathcal{M}$ is just $\in$.

We can ask how "correct" $\mathcal{M}$ is in comparison to the standard model. There are various ways to do this. The simplest is to just look at the "numbers sort." We say that $\mathcal{M}$ is an $\color{red}{\mbox{$\omega$-model}}$ iff $$(\mathbb{Num}_\mathcal{M};0_\mathcal{M},1_\mathcal{M},+_\mathcal{M},\times_\mathcal{M},<_\mathcal{M})\cong(\mathbb{N};0,1,+,\times,<).$$ Note that there are lots of non-isomorphic $\omega$-models out there since this is only a restriction on the numbers sort of the model; an $\omega$-model is determined, up to isomorphism, by a set of sets of natural numbers. For example, the set $\mathsf{REC}$ of recursive sets yields one $\omega$-model (satisfying $\mathsf{RCA_0}$ but not $\mathsf{ACA_0}$, for example) while the set $\mathsf{ARITH}$ of arithmetical sets yields another (satisfying $\mathsf{ACA_0}$ but not $\mathsf{ATR_0}$, for example).

However, we often want a lot more correctness than this. $\mathcal{M}$ is a $\color{red}{\mbox{$\beta$-model}}$ iff $\mathcal{M}$ is correct about well-foundedness: hiding an implicit appeal to an ordered pairing function, if $A\subseteq\mathbb{Num}_\mathcal{M}^2$ is ill-founded and $A\in\mathbb{Set_\mathcal{M}}$ then there is some $B\in\mathbb{Set}_\mathcal{M}$ which is nonempty and has no $A$-least element.

Taking $A=<_\mathcal{M}$ we see that every $\beta$-model is an $\omega$-model. The converse however is false: $\mathsf{REC}$ for example is not a $\beta$-model since there are computable linear orders which are not well-ordered but do not have computable descending sequences. In fact, every $\beta$-model satisfies the rather strong (but still first-order!) theory $\mathsf{ATR_0}$. This can all be found in the relevant section of Simpson's book Subsystems of second-order arithmetic.

---

What if we want to talk about $\beta$-models outside the context of two-sorted arithmetic?

Well, in general we need to specify:

• What base sets are we looking at putative well-orderings of?

• How precisely should we make sense of "correct about well-foundedness"?

There are some subtleties here! For example, if $\mathcal{M}$ is a well-founded model of $\mathsf{KP}$ (a particular fragment of $\mathsf{ZFC}$), then a binary relation $A\in \mathcal{M}$ is a genuine well-ordering iff it admits in $\mathcal{M}$ an isomorphism with some ordinal; on the other hand, ill-founded binary relations in $\mathcal{M}$ need not have descending sequences in $\mathcal{M}$. I've said more about this here.

So in general we have to be careful how we use the term "$\beta$-model" outside of its original context. Indeed, note that the discussion linked in your post led to the realization that there are at least two candidates for what "$\beta$-model of $\mathsf{NF}$" should mean (see the follow-up here).

Answer 2

It's rather simple to do so for set theory. Let $S$ be the set of axioms of ZF(C). Add to these axioms constant symbols $x_n$, $n \in \mathbb{N}$, and the axioms $x_{n + 1} \in x_n$ for each $n$.

If ZF(C) has a model, then by the compactness theorem, so does our extension of ZFC (since clearly if we include only finitely many of the axioms $x_{n + 1} \in x_n$, we can pick a variable assignment in the model of ZF(C) which models this finite subset).

But in this model, we have an infinite chain $x_0 \ni x_1 \ni ...$. So the relation $\in$ in this model is not well-founded.

This logic can extend to the 1st-order theory of the naturals in the same way (with axioms $x_0 > x_1 > ...$).

However, the compactness theorem does not apply to 2nd-order logic. In fact, if we have a predicate $<$ which is well-founded in the 2nd-order sense, then in any model with the standard semantics, the predicate will be well-founded under the usual semantics.

However, higher-order arithmetic can also be interpreted in toposes using the Kripe-Joyal semantics. Here, a relation which is well-founded in the topos may be externally non-well-founded because the theory of toposes is a 1st-order theory and hence we can use compactness.

Thus, there is a topos with an object $O$ and a relation $< \subseteq O \times O$ which the topos proves is a well-order, but where there is a decreasing chain of global elements $x_i : 1 \to O$, $x_0 > x_1 > ...$. In fact, such a topos can be constructed from the "bad model" of ZFC we constructed above.

So it depends on the allowed models whether a $\beta$-model can or can't be constructed.