Below, "logic" means "regular logic containing first-order logic" in the sense of Ebbinghaus/Flum/Thomas.
Setup
For a logic $\mathcal{L}$, let $\mathcal{PA}(\mathcal{L})$ be the set of $\mathcal{L}$-sentences in the language of arithmetic consisting of:
-
the ordered semiring axioms, and
-
for each $\mathcal{L}$-formula $\varphi(x,y_1,...,y_n)$ the induction instance $$\forall y_1,...,y_n[[\varphi(0,y_1,...,y_n)\wedge\forall x(\varphi(x,y_1,...,y_n)\rightarrow\varphi(x+1,y_1,...,y_n))]\rightarrow\forall x\varphi(x,y_1,...,y_n)].$$
(Note that even if the new logic $\mathcal{L}$ has additional types of variable - e.g. "set" variables - the corresponding induction instances will only allow "number" variables $y_1,...,y_n$ for the parameters.)
For example, $\mathcal{PA}(FOL)$ is just the usual (first-order) PA, and $\mathcal{PA}(SOL)$ characterizes the standard model $\mathbb{N}$ up to isomorphism. Also, we always have $\mathbb{N}\models_\mathcal{L}\mathcal{PA}(\mathcal{L})$.
- Note that it's not quite true that $\mathcal{PA}(SOL)$ "is" second-order PA as usually phrased - induction-wise, we still have a scheme as opposed to a single sentence. However, induction applied to "has finitely many predecessors" gets the job done. (If we run the analogous construction with ZFC in place of PA, though, things seem more interesting ....)
Question
Say that a logic $\mathcal{L}$ is PA-intermediate if we have $PA<\mathcal{PA}(\mathcal{L})<Th_{FOL}(\mathbb{N})$ in the following sense:
-
There is a first-order sentence $\varphi$ such that $PA\not\models\varphi$ but $\mathcal{PA}(\mathcal{L})\models\varphi$.
-
There is a first-order sentence $\theta$ such that $\mathbb{N}\models\theta$ but $\mathcal{PA}(\mathcal{L})\not\models\theta$.
Is there a "natural" PA-intermediate logic?
(This is obviously fuzzy; for precision, I'll interpret "natural" as "has appeared in at least two different papers whose respective authorsets are incomparable.")
Partial progress
-
A couple non-examples:
-
Infinitary logic $\mathcal{L}_{\omega_1,\omega}$ is not PA-intermediate, since in fact $\mathcal{PA}(\mathcal{L}_{\omega_1,\omega})$ pins down $\mathbb{N}$ up to isomorphism (consider $\forall x(\bigvee_{i\in\omega}x=1+...+1\mbox{ ($i$ times)}$). So both second-order and infinitary logic bring in too much extra power.
-
Adding an equicardinality quantifier ($Ix(\varphi(x);\psi(x))$ = "As many $x$ satisfy $\varphi$ as $\psi$") also results in pinning down $\mathbb{N}$ up to isomorphism (consider "$\neg$ As many $x$ are $<k$ as are $<k+1$"). If we add the weak equicardinality quantifer $Qx\varphi(x) = Ix(\varphi(x);\neg\varphi(x))$, on the other hand, we wind up with a conservative extension of $PA$. That said, the latter is stronger semantically: no countable nonstandard model of $PA$ satisfies $\mathcal{PA}(FOL[Q])$ (to prove conservativity over $PA$ we look at the $\omega_1$-like models).
-
-
The proof of Lindstrom's theorem yields a weak negative result: if $\mathcal{L}$ is a logic strictly stronger than first-order logic with the downward Lowenheim-Skolem property, then we can whip up an $\mathcal{L}$-sentence $\varphi$ and an appropriate tuple of formulas $\Theta$ such that $\varphi$ is satisfiable and $\Theta^M\cong\mathbb{N}$ in every $M\models\varphi$. So an example for the above question would have to either allow nasty implicit definability shenanigans or lack the downward Lowenheim-Skolem property. This rules out a whole additional slew of candidates. That said, there is a surprising amount of variety among logics without the downward Lowenheim-Skolem property even in relatively concrete contexts - e.g. there is a compact logic strictly stronger than FOL on countable structures.
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment