9
$\begingroup$

Let $\mathsf{KP_0\omega}$ be Kripke-Platek set theory with Infinity but Foundation (or $\in$-Induction) restricted to $\Delta_0$-formulas. $\mathsf{ZF}$ proves $\in$-Induction holds for arbitrary formulas, but it is because we have Full Separation which is unavailable over $\mathsf{KP_0\omega}$, so $\in$-Induction on more complex formulas become a non-trivial statement over $\mathsf{KP_0\omega}$.

I wonder whether the following is known:

Question. Working over $\mathsf{KP_0\omega}$,

  1. Does $\Pi_1$-Foundation prove $\Sigma_1$-Foundation or vice versa?
  2. What about their consistency strength? Does $\Pi_1$-Foundation have a higher consistency strength than that of $\Sigma_1$-Foundation?

Added. $\Gamma$-Foundation is the following schema: For a formula $\phi(x)$ in $\Gamma$, if $[\forall x\in a \phi(x)]\to \phi(a)$ for all $a$, then $\forall a\phi(a)$.

$\endgroup$
6
  • $\begingroup$ By "$\Gamma$-Foundation", do you mean the scheme where for every $\Gamma$ formula $\varphi$, we have the axiom that says "For every $p$, if for every $x$, we have $\Big(\forall y\in x\ \varphi(p,y)\Big)\implies\varphi(p,x)$, then for every $x$, we have $\varphi(p,x)$"? $\endgroup$
    – Farmer S
    Commented Mar 27, 2023 at 1:41
  • $\begingroup$ @FarmerS Yes. This is what I meant. $\endgroup$
    – Hanul Jeon
    Commented Mar 27, 2023 at 3:38
  • $\begingroup$ @HanulJeon Just a notational suggestion for long term purposes: $\mathsf{KPI}_0$ instead of $\mathsf{KP}_{\omega_0}$ , which is more in tune with other existing notation. $\endgroup$
    – Ali Enayat
    Commented Apr 1, 2023 at 15:18
  • $\begingroup$ @AliEnayat I did not use it because some references use KPI to denote KP with cofinality many recursively inaccessible ordinals. $\endgroup$
    – Hanul Jeon
    Commented Apr 2, 2023 at 17:54
  • $\begingroup$ @HanulJeon Yes, there is no standard terminology here (for example in the older references $\mathsf{KP}$ includes the full scheme of foundation (equivalently, the full scheme of $\in$-induction). The problem I have with your current notation is that the subscript 0 visually seems to be attached to $\omega$, as opposed the whole package $\mathsf{KF}_{\omega}$, which is how you intend it. $\endgroup$
    – Ali Enayat
    Commented Apr 3, 2023 at 18:32

1 Answer 1

7
$\begingroup$

The original version of this answer contained a mistake, as pointed out by Hanul Jeon. The main issue was that I was assuming too much of the $\omega$ of the model. This version makes a weaker claim.

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".

Claim: (i) $\mathrm{KP}_{\omega_0}+\Pi_1$-Induction does not prove $\Sigma_1$-Induction.

However, (ii) the consistency strength of $\mathrm{KP}_{\omega_0}+\Sigma_1$-Induction is at least as strong as $\mathrm{KP}_{\omega_0}+\Sigma_1$-Induction + $\Pi_1$-Induction, as every model of the former has an inner model of the latter (its constructible universe $L$, defined in a natural manner).

Here "$\Gamma$-Induction" is the scheme where 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 also want to formulate a variant of the main claim. Working in KP$_{\omega_0}$, define (von Neumann) ordinals as usual (transitive sets which are linearly ordered by $\in$).

Lemma 1: KP$_{\omega_0}$ proves that ordinals are comparable (via $\in$), and that there is a least limit ordinal, which we denote $\omega$.

Proof: This is as usual, noting that KP$_{\omega_0}$ suffices. Here it is, for convenience: Given ordinals $\alpha,\beta$, let $\gamma=\alpha\cap\beta$, and note that $\gamma$ is an ordinal, but $\gamma\notin\alpha\cap\beta$. We must have $\gamma=\alpha$ or $\gamma=\beta$. For otherwise, by Foundation we can let $\delta\in\alpha\backslash\gamma$ be $\in$-minimal and $\varepsilon\in\beta\backslash\gamma$ be $\in$-minimal. We can't have $\delta=\varepsilon$ (by definition of $\gamma$), but we do have $\gamma\subseteq\delta\cap\varepsilon$. But this easily leads to a contradiction to the $\in$-minimalities of these two. So either $\gamma=\alpha$ or $\gamma=\beta$. Say $\gamma=\alpha$. We may assume $\gamma\neq\beta$. Now argue similarly as before to see that $\gamma=\alpha\in\beta$.

Now by Infinity, there is an inductive set, i.e. a set $w$ with $0\in w$ and $w$ closed under $+1$. Let $w'$ be the set of ordinals in $w$; note that this is also inductive. Let $w''$ be the set of all $x\in w'$ such that $x\subseteq w'$; note that this is also inductive. Note that $w''$ is a transitive set of ordinals, so $w''$ is an ordinal (using the comparability of ordinals). Note that $w''$ is a limit ordinal. If $w''$ contains no limit ordinals, then it is the least limit ordinal, by comparability. Otherwise, let $X$ be the set of limit ordinals in $w''$. Then by Foundation, there is an $\in$-minimal element $\eta$ of $X$. This is the least limit ordinal.

Now $\Gamma$-Induction over $\omega$ is the scheme where for each $\Gamma$-formula $\varphi$, we have the axiom "for all $p$, if $$ \varphi(p,0)\wedge \forall n\in\omega\ \Big[\varphi(p,n)\Rightarrow\varphi(p,n+1)\Big],$$ then $$ \forall n\in\omega\ \varphi(p,n).\text{"}.$$

Lemma 2: KP$_{\omega_0}$ + $\Sigma_1$-Induction proves $\Sigma_1$-Induction over $\omega$.

Proof: Let $\varphi$ be $\Sigma_1$ and $p$ be a set and suppose that $$ \varphi(p,0) $$ and for all $n\in\omega$, $$\text{ if }\varphi(p,n)\text{ then }\varphi(p,n+1).$$ Let $\varphi'$ be the formula in parameters $p,\omega$ asserting ``if $x\in\omega$ then $\varphi(p,x)$''. Note that for all sets $x$, if $\varphi'(p,y)$ holds for all $y\in x$, then $\varphi'(p,x)$ holds. So we can apply $\Sigma_1$-Induction, giving that $\varphi'(p,x)$ holds for all $x$, which clearly suffices.

Claim': (i) KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$ + $\Pi_1$-Induction does not prove $\Sigma_1$-Induction.

(ii) KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$ has consistency strength at least as strong as KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$ + $\Pi_1$-Induction. In fact every model of the former has an inner model satisfying the latter (its $L$).

We first prove (ii) of the Claim and Claim'.

Lemma 3: KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$ proves that transitive closures exist.

Proof: Let $x$ be any set. Define by recursion $\left<x_n\right>_{n<\omega}$, where $x_0=x$ and $x_{n+1}=x_n\cup \bigcup x_n$. This runs all the way through $\omega$, by $\Sigma_1$-Induction over $\omega$. Now apply KP to the fact that for all $n\in\omega$ there is a sequence $\left<x_i\right>_{i\leq n}$ satisfying the above recursion through to $n$, to get that there is a set $X$ such that for all $n<\omega$, we have $x_n\in X$ and $\left<x_i\right>_{i\leq n}x_n\in X$. Now just use $\Delta_0$-Separation with the set $X\cup\bigcup X$ to see that the transitive closure of $x$ exists (it is a subset of $\bigcup X$).\

Now I want to sensibly define $L^M$ for a model $M$ of KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$. Given $\alpha\in\mathrm{OR}^M$, say $\alpha$ is good if there is a sequence $\left<l_\beta\right>_{\beta\leq\alpha}$ satisfying the usual recursion for the levels of $L$. If $\alpha$ is good, then there is a unique witnessing sequence. So for good $\alpha$, define $L_\alpha^M$ as the unique witnessing $l_\alpha$. Now let $G$ be the class of all good $\alpha$ of $M$, and define $L^M=\bigcup_{\alpha\in G}L_\alpha^M$. Note that $G$ is closed downward by definition, and by $\Sigma_1$-Induction over $\omega$, it has no largest element (for each $L_\alpha^M$, the satisfaction relation for $L_\alpha^M$ exists as a set, so we can define $L_{\alpha+1}^M$).

Lemma 4: $\mathrm{KP}_{\omega_0}$+ $\Sigma_1$-Induction over $\omega$ + "$V=L$" proves $\Pi_1$-Induction.

Proof: Let $M$ be a model of $\mathrm{KP}_{\omega_0}$+ $\Sigma_1$-Induction over $\omega$ + "$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)$". Clearly we have this at $n=0$ already. 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 + "$V=L$", 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}$ + $\Sigma_1$-Induction over $\omega$, and the whole construction is a $\Sigma_1$-recursion of length $\omega$, we get that $\sup_{n<\omega}\eta_n<\mathrm{OR}^M$ 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.

Lemma 5: Let $M$ be a model of KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$. Then $L^M\models$ KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$ + "$V=L$", and hence (by Lemma 4) $L^M$ also models $\Pi_1$-Induction. Moreover, if $M\models\Sigma_1$-Induction then every ordinal of $M$ is good, and $L^M\models\Sigma_1$-Induction.

Proof: The main three things to verify are (a) $L^M\models$ KP$_{\omega_0}$, (b) $L^M\models$ Infinity, and (c) $L^M\models \Sigma_1$-Induction (possibly just over $\omega$).

We first consider (a). For this, the main issue is $\Sigma_1$-bounding.

Sublemma: There is no $x\in M$ such that for cofinally many good $\alpha\in G$, we have $L_\alpha^M\in x$.

Proof: Suppose otherwise. Then there is there is a set $x\in M$ such that $L_\alpha^M\in x$ for cofinally many good $\alpha$. Let $x'$ be the transitive closure of $x$, so then $L^M\subseteq x'$. In particular, every good $\alpha$ is in $L^M$. And note that the class $G$ of all good $\alpha$ is definable over $x'$, since the recursions needed to witness their goodness are all in $L^M$, so in $x'$. So $G\in M$. But then $G\in\mathrm{OR}^M$ and again using the properties of $x'$, it is easy to see that $G$ is also good, a contradiction.

This proves the sublemma. We can now verify $\Sigma_1$-bounding in $L^M$. So let $\varphi$ be $\Sigma_1$ and $d,p\in L^M$ and suppose (i) $L^M\models$ "For all $x\in d$ there is $y$ such that $\varphi(p,x,y)$". We must see that (ii) there is $w\in L^M$ such that $L^M\models$" For all $x\in d$ there is $y\in w$ such that $\varphi(p,x,y)$".

So assume (i) holds. Now $L^M$ is $\Sigma_1^M$, as is the class of good $\alpha$ and the function $\alpha\mapsto L_\alpha^M$ for good $\alpha$. So note that $M\models$"For all $x\in d$ there is a good $\alpha$ such that $L_\alpha^M\models\varphi(p,x,y)$". So by KP in $M$, there is a set $w$ such that $M\models$"For all $x\in d$ there is a good $\alpha\in w$ such that $L_\alpha^M\models\varphi(p,x,y)$". But then by the sublemma, the set $w$ can only contain boundedly many good $\alpha$s, so letting $\beta$ be good and containing all of those, we get that $L_\beta^M\models$"For all $x\in d$ there is $y$ such that $\varphi(p,x,y)$", which suffices.

Now consider (b), i.e. the Axiom of Infinity. For this, it is enough to see that $\omega\in L^M$. But $\omega\subseteq G$ by $\Sigma_1$-Induction over $\omega$ in $M$, and so $\omega\subseteq L^M$, and then clearly also $\omega\in G$, so $\omega\in L^M$.

Now we verify that $L^M\models\Sigma_1$-Induction over $\omega$. But this holds because $\omega^{L^M}=\omega$, and since $L^M$ is transitive and $\Sigma_1^M$-definable.

Finally suppose that $M\models\Sigma_1$-Induction. Then clearly $G=\mathrm{OR}^M$ and the fact that $L^M\models\Sigma_1$-Induction is like in the previous paragraph.

For (c): That $L^M\models$ $\Sigma_1$-Induction over $\omega$ is a straightforward relativization, using that $L^M$ is $\Sigma_1^M$-definable. For full $\Sigma_1$-Induction, suppose $M\models\Sigma_1$-Induction, and let $\varphi$ be $\Sigma_1$ and $p\in L^M$, and suppose that $L^M\models$"For all $x$, if for all $y\in x$, $\varphi(p,y)$ holds, then $\varphi(p,x)$ holds". Now suppose for contradiction that $x_0\in L^M$ but $L^M\models\neg\varphi(p,x_0)$. Let $\alpha$ be good and large enough that $p,x_0\in L_\alpha^M$. Let $\varphi'(p,x,L_\alpha^M)$ assert (of parameters $p,L_\alpha^M$ and variable $x$) "if $x\in L_\alpha^M$ then $L\models\varphi(p,x)$". Then note that $M\models$ "for all $x$, if for all $y\in x$, $\varphi'(p,y)$ holds, then $\varphi'(p,x)$ holds". (For let $x\in L_\alpha^M$ and suppose that $M\models\varphi'(p,y)$ for all $y\in x$. Then since $x\in L_\alpha^M$, we have $x\subseteq L_\alpha^M$, and therefore $L^M\models\varphi(p,y)$ for all $y\in x$, and so $L^M\models\varphi(p,x)$, which suffices.) Therefore by $\Sigma_1$-Induction in $M$, $M\models$ "For all sets $x$, $\varphi'(p,x)$ holds", so $L^M\models$ "For all sets $x\in L_\alpha^M$, $\varphi(p,x)$ holds", contradicting that $x_0\in L_\alpha^M$.

This completes the proof of Lemma 5, and therefore of Claim (ii) and Claim' (ii).

Claim (i) is a direct consequencde of Claim' (i). So it just remains to see:

Proof of Claim' (i): Let $M$ be any model of KP + "$V=L$" which is illfounded and having wellfounded part $L_{\omega_1^{\mathrm{ck}}}$. Let $\eta$ be an illfounded ordinal of $M$. Let $N=L_{\eta+\omega_1^{\mathrm{ck}}}^M$ (that is, $N$ is the "union" of all segments $L_{\eta+\alpha}^M$, for $\alpha<\omega_1^{\mathrm{ck}}$). Then (a) $N\models$ KP$_{\omega_0}$ + $\Sigma_1$-Induction over $\omega$ + "$V=L$", and hence models $\Pi_1$-Induction, but (b) $N\not\models\Sigma_1$-Induction.

To see (a): The main issue is $\Sigma_1$-bounding. So let $\varphi$ be $\Sigma_1$ and $p,d\in N$, and suppose that $N\models$"For all $x\in d$, there is $y$ such that $\varphi(p,x,y)$". Let $\gamma\in\mathrm{OR}^M$ with $\gamma$ illfounded. Then $M\models$"For all $x\in d$ there is $\alpha<\gamma$ such that $L_{\eta+\alpha}\models\varphi(p,x,y)$", and so the function $x\mapsto\alpha_x$, where $\alpha_x$ is the least $M$-ordinal such $\alpha$ such that $L_{\eta+\alpha}^M\models\varphi(p,x,y)$, is $\Sigma_1^M(M)$, and hence is an element of $M$. But $\alpha_x<\omega_1^{\mathrm{ck}}$ for each $x\in M$. Since $\omega_1^{\mathrm{ck}}\notin M$, this function must be bounded in $\omega_1^{\mathrm{ck}}$, which suffices.

Finally, to see (b), just use the fact that "ordinal" addition is $\Sigma_1$-definable, but the class of all $\alpha\in\mathrm{OR}^N$ such that $N\models$"$\eta+\alpha$ exists" is just the wellfouned part of $N$, i.e. $\omega_1^{\mathrm{ck}}$, so $N\models$"for all sets $x$, if $x$ is an ordinal and for all $y\in x$, $\eta+y$ exists, then $\eta+x$ exists", but $N\not\models$"for all sets $x$, if $x$ is an ordinal then $\eta+x$ exists".

$\endgroup$
9
  • $\begingroup$ Thank you for your answer, but I have a question about your answer; How can we ensure $\mathsf{KP\omega}_0$ proves $L$ is definable? The $L$-hierarchy is defined recursively and requires at least $\Sigma$-Recursion. I used to thought $\Sigma$-Recursion is provable from $\mathsf{KP\omega}_0$ with $\Sigma_1$-Induction, but a typical proof for $\Sigma$-Recursion uses TC-Recursion on $\Sigma$-formulas, and the existence of TC uses $\Pi_1$-Induction. (cf. Theorem I.6.1 of Barwise.) $\endgroup$
    – Hanul Jeon
    Commented Mar 27, 2023 at 3:53
  • $\begingroup$ Even if we assume the existence of the transitive closure as a separate axiom, we need to check whether $L$ is definable from $\Delta_0$-induction (to $\Delta_0$-formulas.) The other issue is that whether $\mathsf{KP\omega}_0$ proves if we have $L$, then $L$ satisfies $\mathsf{KP\omega}_0$. I guess the proof in Matthews-Rathjen should work, but I am not sure. Despite that, your proof is interesting as it still shows $\mathsf{KP\omega}_0$ + $\Sigma_1$-Induction + Transitive Closure proves $L$ satisfies $\Pi_1$-Induction, which seems new. $\endgroup$
    – Hanul Jeon
    Commented Mar 27, 2023 at 3:53
  • $\begingroup$ Interesting argument. Though I pretty much sure that it does not work in $\mathsf{KP}_{\omega_0}$. The problem is that $\mathsf{KP}_{\omega_0}$ doesn't prove $\Sigma_1$-recursion. And consistency strengths don't match: the $\mathsf{KP}_{\omega_0}$ is $\Pi_2$-conservative over Rudimetary Recursive Set Theory with infinity whose minimal constructive model is $L_{\omega 2}$. And over $\mathsf{KP}_{\omega_0}$, $\Pi_1$ membership induction implies $\Pi_1$-induction on natural, which in turn implies $\Sigma_1$-induction on naturals and the latter implies the existence of the ordinal $\omega 2$. $\endgroup$ Commented Mar 28, 2023 at 14:00
  • 1
    $\begingroup$ @HanulJeon Deriving $\mathsf{TC}$ from $\mathsf{KP}_{\omega_0}+\Sigma_1\textsf{-Ind}$ is not a problem. For any $x$, by $\Sigma_1$-induction on naturals you could prove that for each $n$ there is a set $y_n$ consising of pairs $\langle m,z\rangle$, $m\le n$ such that $(y_n)_0=\{z\mid \langle 0,z\rangle\in y\}$ is equal to $x$, and for $m<n$, $(y_n)_{m+1}=\{z\mid \exists w\in (y_n)_m(z\in w)\}$. Then you simply apply collection to $\omega$ to obtain the set of all $y_n$ and then obtain the transitive closure as $\bigcup\limits_{n<\omega,m<\omega}(y_n)_m$. $\endgroup$ Commented Mar 28, 2023 at 18:51
  • 1
    $\begingroup$ @HanulJeon Sorry wasn't very precise there. $\mathsf{RRST}$ should be $B_0^\mathsf{set}+\mathsf{TC}+\mathsf{Regularity}$, where $B_0^\mathsf{set}$ is from Simpson's book and is axiomatized by Extensionality, Infinity, and the axioms of Rudimentary Closure. The hierarchy $L_\alpha(x)=\mathsf{TC}(x)\cup\{x\}\cup\bigcup\limits_{\beta<\alpha}\{y\mid y \text{ is first-order definable in }L_{\beta}(x)\}$. $\endgroup$ Commented Mar 29, 2023 at 8:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .