Is Categoricity preserved under equi-interpretability?

Question

Is PA + Omega rule categorical?

Is the theory ZF-Inf.+Fin+ Omega rule categorical?

According to the posting here, ZF-Inf.+Fin+Omega rule is proved equiv-interpretable with PA + omega rule, both of which are complete theories. So would that equi-interpretability also prove the former theory to be categorical?

The main concern is if theory ZF-Inf.+Fin+Omega rule can allow for non-standard models of it, i.e. if it allows for existence of sets that are not well founded hereditarily standard finite sets.

Answer 1

First I'll address the background question: neither theory is categorical. I'll treat first the specific case of PA + $\omega$-rule, then state a more general result (which shows that we never get categoricity in this way - and so in particular the answer to the "main concern" is yes). Finally I'll give a strong negative answer to the title question.

---

Here's a proof that PA + $\omega$-rule is not categorical:

Claim: if $M$ satisfies true arithmetic (= $Th(\mathbb{N})$), then $M$ satisfies PA + $\omega$-rule.

This immediately implies that PA + $\omega$-rule has nonstandard models, since no first-order theory with at least one infinite model is categorical (by compactness, in the form of the upwards Lowenheim-Skolem theorem).

Proof: The only nontrivial piece is to show that $M$ satisfies the $\omega$-rule. We prove this by elementarity. (I'll conflate standard natural numbers and their corresponding numerals for simplicity.)

• Suppose $M\models\varphi(n)$ for each $n\in\mathbb{N}$.

• By elementarity, we have $\mathbb{N}\models\varphi(n)$ for each $n$.

• So $\mathbb{N}\models\forall x\varphi(x)$.

• By elementarity again, we have $M\models\forall x\varphi(x)$.

And we're done. $\quad\Box$

(In fact, using this we can prove that PA + $\omega$-rule "is" just true arithmetic, albeit a particularly nice presentation of it. And the theory ZF - Inf + "HF-rule" similarly "is" just $Th(HF)$, the proof being basically identical.)

Note that this does not mean that the $\omega$-rule is valueless! "PA + $\omega$-rule" is an interesting different description of true arithmetic and suggests a number of related non-a-priori-first-order variations which turn out to be quite interesting and important.

It also suggests studying the logical aspects of problems of the form "Find the least fixed point of such-and-such closure operator." This leads to a bit of higher recursion theory - namely metarecursion theory, or in more modern language $\alpha$-recursion theory in the special case of $\alpha=\omega_1^{CK}$ - since the least fixed points of "computable" closure operators on the naturals are exactly the $\Pi^1_1$ (or meta-r.e., or $\omega_1^{CK}$-r.e.) sets of natural numbers. (For the left-to-right direction of this claim, note that the least fixed point of $\mathcal{R}$ is the set of $x$ satisfying "For all $\mathcal{R}$-closed $A$ we have $x\in A$;" the other direction is a bit more complicated and uses ranking functions.)

(It also leads to the study of inductive definitions in proof theory, but I know basically nothing about that. It is important, though!)

---

Note that we used very little in the above - all that mattered was that each instance of the $\omega$-rule was "triggered" by a collection of first-order sentences, so we could argue via elementarity that "triggered in $M$ $\implies$ triggered in $\mathbb{N}$ $\implies$ goal is true in $\mathbb{N}$ $\implies$ goal is true in $M$."

This argument lets us prove the following general result. Say that an infinitary rule $\mathcal{R}$ is a set of pairs of the form $\langle \Gamma,\varphi\rangle$ for $\Gamma$ a set of sentences and $\varphi$ a sentence (intended meaning: "from $\Gamma$ infer $\varphi$"). For a structure $M$ and an infinitary rule $\mathcal{R}$, say that $M$ satisfies $\mathcal{R}$ iff for all $\langle\Gamma,\varphi\rangle\in\mathcal{R}$, if $M\models\Gamma$ then $M\models\varphi$. Then:

$(*)\quad$ The set of structures satisfying an infinitary rule $\mathcal{R}$ is always an elementary class - so we never get categoricity via infinitary rules.

Note that this really does imply the particular cases of interest in the OP: we can always add a first-order theory $T$ to a rule $\mathcal{R}$ by considering the new infinitary rule $$\mathcal{R}[T]=\mathcal{R}\cup\{\langle\emptyset,\varphi\rangle:\varphi\in T\}.$$ So just apply $(*)$ above to "$\omega$-rule$[{PA}]$."

---

As to the answer in the above question, it depends precisely what you mean by "equi-interpretability" (note that here we're talking a priori about non-first-order theories, in order for this to be nontrivial).

The simplest interpretation of this term is fairly loose: say that $T$ and $S$ are simply equi-interpretable iff every model of one interprets some model of the other. This does not preserve categoricity: consider $T=$ second-order PA versus $S=$ "second-order PA + a structureless set" (that is, a model of $S$ consists of a model of second-order PA plus an infinite structureless set). $T$ and $S$ are trivially simply equi-interpretable, but $S$ is clearly not categorical (just change the cardinality of the structureless set part).

• In fact, note that this shows that simple equi-interpretability doesn't even preserve completeness - the structureless set part of a model of $S$ could have one element, or two elements, or ...

One level up is bi-interpretability - roughly speaking, this means that given any model $M$ of $T$ we can find a model $N$ of $S$ interpreted in $T$ and a model $M'$ of $T$ interpreted in $S$ "definably in $M$" (and vice versa). But the idea above shows that this also does not preserve categoricity or even completeness - consider now a (non-first-order) theory $T$ pinning down some uncountable structure $M$ up to isomorphism, and the new theory $S$ = "$T$ + a structureless set."

Instead you need something even stronger - that there is a "definable" (in some sense) bijection between the classes of isomorphism types. But that trivially preserves categoricity, since the existence of any bijection between the classes of isomorphism types tells us that the theories have the same number of models.