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

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).

## 2 Answers

"$$\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).

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.

• This isn't really on point - "$\beta$-model" and "well-founded model" mean quite different things in the context of theories of arithmetic. E.g. $\mathsf{REC}$ is a well-founded model (= $\omega$-model) of the subtheory of second-order arithmetic $\mathsf{RCA_0}$ (which, despite the terminology, is a first-order theory) but is not a $\beta$-model (in fact every $\beta$-model of $\mathsf{RCA_0}$ satisfies $\mathsf{ATR_0}$). Aug 8, 2021 at 3:14