7
$\begingroup$

Is it known that $\Pi^1_1$-induction is independent of ATR$_0$? Simpson's book shows this for $\Pi^1_1$ transfinite induction ($\Pi^1_1$-TI), but I'm only interested in inducting on $\omega$.

I can show that ATR$_0$ + $\Pi^1_1$-induction implies $\Sigma^1_1$-TI, but unlike simpler inductions, it's not clear that the $\Pi$ and $\Sigma$ forms are equivalent here.

$\endgroup$
2
  • 2
    $\begingroup$ If I'm understanding everything correctly, then I think $\Pi^1_1$-TI is not implied by $\Pi^1_1$ induction over $\mathsf{ATR}_0$ and hence is not equivalent to $\Sigma^1_1$-TI. In Simpson's book, it is actually shown that there is an $\omega$-model of $\mathsf{ATR}_0$ where $\Pi^1_1$-TI fails. But $\Pi^1_1$ induction holds in every $\omega$-model so this gives a model of $\mathsf{ATR}_0$ where $\Pi^1_1$ induction holds but $\Pi^1_1$-TI does not. $\endgroup$ Mar 21, 2021 at 15:37
  • $\begingroup$ Ah, nice. So that approach to showing independence won't work. $\endgroup$ Mar 21, 2021 at 21:58

1 Answer 1

4
$\begingroup$

Let me sketch the proof that $\mathsf{ATR}_0+\Pi^1_1\textsf{-Ind}\vdash\mathsf{Con}(\mathsf{ATR}_0)$ (by Gödel's 2-nd incompleteness this implies that $\mathsf{ATR}_0$ doesn't prove $\Pi^1_1\textsf{-Ind}$).

We reason in $\mathsf{ATR}_0+\Pi^1_1\textsf{-Ind}$. Assume for a contradiction that $\mathsf{ATR}_0$ isn't consistent. Recall that $\mathsf{ATR}_0$ could be axiomatized over first-order logic by a single $\Pi^1_2$ sentence (i.e. sentence of the form $\forall \vec{X}\exists \vec{Y}\;\varphi$, where $\varphi$ doesn't contain second-order quantifiers). By our assumption there is a FOL proof of $\lnot \forall \vec{X}\exists \vec{Y} \;\varphi$. So we have a cut-free Tait calculus proof $P$ of the sequent $\exists \vec{X}\forall \vec{Y} \;\lnot \varphi$. We prove by $\Pi^1_1$-induction on the $P$-subproofs $$\displaystyle\frac{\ldots}{\Gamma}$$ that the universal closure of $\bigvee (\Gamma\cap \Pi^1_1)$ is true. The main point in this proof by induction is that when some new non-$\Pi^1_1$ arise the last rule should have been of the form $$\displaystyle \frac{\Delta,\forall \vec{Y}\;\lnot \varphi}{\Delta,\exists X_n\forall \vec{Y}\;\lnot \varphi}$$ and since we know that actually $\forall \vec{X}\exists \vec{Y} \varphi$, in fact $\forall \vec{Y}\;\lnot \varphi$ was false on any value of parameters $\vec{X}$ and hence the universal closure of $\bigvee (\Delta \cap \Pi^1_1)$ was true. For the case of the whole derivation $P$ we see that the universal closure of the empty disjunction is true, contradiction.

Note that the same argument shows that over $\mathsf{RCA}_0$ the principle $\Pi^1_1\textsf{-Ind}$ is equivalent to uniform $\Pi^1_3$-reflection for $\mathsf{RCA}_0$.

$\endgroup$
1
  • $\begingroup$ That's great, thank you. $\endgroup$ Apr 16, 2021 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.