*This is a modified version of a question which was asked and bountied at MSE without success.*

Below, "$\mathsf{PA}$" refers to *first-order* Peano arithmetic.

There are various "schematic" theories out there, like $\mathsf{PA}$ and $\mathsf{ZFC}$, which basically consist of three components: a "base" set of axioms which are more-or-less taken for granted *(e.g. the discrete nonnegative ordered semiring axioms for $\mathsf{PA}$, and Pairing-Union-Extensionality-Foundation-Powerset-Infinity-Choice for $\mathsf{ZFC}$)*, an informal idea(s) for a further set of rules indexed by formulas *(e.g. induction for $\mathsf{PA}$, and separation/replacement for $\mathsf{ZFC}$)*, and a choice of logic for implementing the latter *(first-order logic for $\mathsf{PA}$ and $\mathsf{ZFC}$, and indeed in general)*. For any such theory we can hope to produce interesting variants by fixing the first two parts and varying the third - see e.g. here for a question about the case of $\mathsf{ZFC}$.

However, $\mathsf{PA}$ seems remarkably stubborn here: every natural logic *(= regular logic possibly without negation)* I can think of lands in one of two extremes. To be precise, given a logic $\mathcal{L}$ let $\mathfrak{PA}(\mathcal{L})$ be the class of models of $\mathsf{PA}$ with no $\mathcal{L}$-definable nontrivial proper cuts, and say that $\mathcal{L}$ is:

**strong for induction**if $\mathfrak{PA}(\mathcal{L})$ consists of just $\mathbb{N}$ up to isomorphism;**weak for induction**if every complete first-order extension of $\mathsf{PA}$ is satisfied by some element of $\mathfrak{PA}(\mathcal{L})$; and**intermediate for induction**if neither of the above cases holds.

My question is:

Is there any natural logic which is intermediate for induction?

(Here, by "natural" I mean "has appeared in at least two different papers whose respective authorsets are $\subseteq$-incomparable.")

In the MSE version I asked for an even stronger property, namely not pinning down $\mathbb{N}$ even up to elementary equivalence, but that seems overly optimistic in retrospect.

Here are some quick negative observations:

Uniformly across models of $\mathsf{PA}$, standardness is definable by a $\Pi^1_1$ formula or by a very simple infinitary formula. So neither $\Pi^1_1$ nor any reasonable infinitary logic will be intermediate for induction; in fact, they'll pin down $\mathbb{N}$ up to isomorphism, not just up to first-order-elementary-equivalence.

$\Sigma^1_1$ also pins down $\mathbb{N}$ up to isomorphism, although parameters now appear necessary; see here. For the same reason, first-order logic + the equicardinality quantifier pins down $\mathbb{N}$ up to isomorphism.

On the opposite end of things, $\Delta^1_1$ is weak for induction.

*(OK, $\Delta^1_1$ may not look like a logic since the $\Delta^1_1$-ness of a $\Sigma^1_1$ formula is structure-dependent, but we can handwave past this: define an abstract logic with a formula $\hat{\varphi}$ for each $\Sigma^1_1$ formula $\varphi$, where $\hat{\varphi}$ is interpreted in $\mathcal{M}$ as $\varphi$ if $\neg\varphi^\mathcal{M}$ is $\Sigma^1_1$ over $\mathcal{M}$ and as $\top$ otherwise.)*Similarly, $\mathsf{FOL}$ + the quantifier "At least as many $x$ satisfy $\varphi$ as satisfy $\neg\varphi$" is weak for induction, although its model class contains no

*countable*nonstandard models; to see weakness, consider the $\omega_1$-like models of $\mathsf{PA}$.

The most promising approach to me at the moment is to look for fragments of second-order logic between $\Delta^1_1$ and $\Sigma^1_1$, since we see a genuinely interesting and nontrivial change in behavior there. However, I can't at the moment think of a good candidate fragment.

(I've added the set theory tag since, while set theory isn't built into the question a priori, it seems relevant to all the ideas I've had so far.)

7more comments