Skip to main content
1 of 2
Farmer S
  • 10k
  • 25
  • 43

I think by what you write, that by "$\Gamma$-Foundation" you mean that for each $\Gamma$ formula $\varphi$, we have the axiom "for all $p$, if $$\forall x\ \Big[(\forall y\in x\ \varphi(p,y))\Rightarrow\varphi(p,x)\Big],$$ then $$\forall x\ \varphi(p,x).\text{"}$$ I will anyway call scheme "$\Gamma$-Induction".

Depending on exactly what you mean by $\Gamma$-Foundation, the following claim and corollary might be relevant:

Claim: $\mathrm{KP}_{\omega_0}$+"$V=L$" proves $\Pi_1$-Induction.

Corollary: $\mathrm{KP}_{\omega_0}$ and $\mathrm{KP}_{\omega_0}+\Pi_1$-Induction have the same consistency strength.

Proof of corollary: If $M$ models $\mathrm{KP}_{\omega_0}$ then $L^M\models\mathrm{KP}_{\omega_0}+\Pi_1$-Induction.

Proof of claim: Let $M$ be a model of $\mathrm{KP}_{\omega_0}$+"$V=L$". Let $\varphi$ be $\Pi_1$ and $p\in M$ and suppose that $\forall x\in M$, if $M\models\forall y\in x\ \varphi(y,p)$, then $M\models\varphi(x,p)$. Suppose there is some $x\in M$ such that $M\models\neg\varphi(x,p)$, and fix such an $x_0$. Let $X_0=\{x_0\}$. Working in $M$, define a sequence $\left<X_n\right>_{n<\omega}$ of non-empty sets $X_n$ as follows. We will maintain by recursion that $X_n\in M$ and $M\models$"$\forall x\in X_n\ \neg \varphi(x,p)$". So, suppose we have $X_n$. Let $\psi(x,p)$ be the formula "$\exists y\in x\ [\neg\varphi(y,p)]$", which is $\Sigma_1$. Note that by KP, there is $\eta<\mathrm{OR}^M$ such that $M\models$"$\forall x\in X_n\ \Big[L_\eta\models\psi(x,p)\Big]$", so $M\models$"$\forall x\in X_n\ \exists y\in x\ \Big[L_\eta\models\neg\varphi(y,p)\Big]$". Let $\eta_n$ be the least such $\eta$ with also $\eta>\eta_{n-1}$ if $n>0$. Now let $X_{n+1}$ be the set of all $y$ such that for some $x\in X_n$, we have $y\in x$ and $L_{\eta_n}\models$"$\neg\varphi(y,p)$". By choice, $X_{n+1}\neq\emptyset$ and for all $y\in X_{n+1}$, since $L_{\eta_n}\models$"$\neg\varphi(y,p)$" and $\neg\varphi$ is $\Sigma_1$, also $M\models$"$\neg\varphi(y,p)$". This completes the recursion. Since $M\models$KP$_{\omega_0}$, which includes Infinity, and the whole construction is a $\Sigma_1$-recursion, we get that $\sup_{n<\omega}\eta_n<\mathrm{OR}^N$ and $\left<X_n\right>_{n<\omega}\in M$. But now let $X=\bigcup_{n<\omega}X_n$ and note that $X$ violates Foundation. It is, moreover, easy to see that Foundation follows from $\Delta_0$-Induction, which is included in the axioms.

Farmer S
  • 10k
  • 25
  • 43