Return to Question

Lemma 2.5. For each $\Delta_0$-formula $\varphi$($x_1$,...,$x_n$) [in the language of set theory] with free variables among $x_1$,..., $x_n$ and each variable $x_j$, 1$\le$$j$$\le$$n$, there is a term $\mathscr F$ on $n$ arguments built from $\mathscr F_1$,...,$\mathscr F_{10}$ [Jech's version of the G$\ddot o$del operations from his Millemium Edition, Chapt. 13] so that

$KP^{-}$ [Kripke-Platek set theory with Foundation replaced with Set Foundation] $\vdash$ $\mathscr F$($a$,$x_1$,...,$x_{j-1}$,$x_{j+1}$,...,$x_n$) = {$x_j$$\in$a| $\varphi$($x_1$,...,$x_n$)}

 

Proof: All of the functions $\mathscr F_1$,..., $\mathscr F_{10}$ can be obtained on the basis of $KP^{-}$. For instance, $KP^{-}$ is strong enough to prove the existence of the Cartesian product $a$ $\times$ $b$ of sets $a$ ans $b$ (see [Barwise: Admissible Sets ane Structures, Chapt. I, Theprem 3.2]). The result now follows from [Barwise, Ibid., Chapt II, Assumption 5.2(v)] because inspection of the proof of [Barwise, Ibid., Chapt. II, Assumption 5.2(v)] reveals that all of its steps can be done within $KP^{-}$.

Lemma 2.5. For each $\Delta_0$-formula $\varphi$($x_1$,...,$x_n$) [in the language of set theory] with free variables among $x_1$,..., $x_n$ and each variable $x_j$, 1$\le$$j$$\le$$n$, there is a term $\mathscr F$ on $n$ arguments built from $\mathscr F_1$,...,$\mathscr F_{10}$ [Jech's version of the G$\ddot o$del operations from his Millemium Edition, Chapt. 13] so that

$KP^{-}$ [Kripke-Platek set theory with Foundation replaced with Set Foundation] $\vdash$ $\mathscr F$($a$,$x_1$,...,$x_{j-1}$,$x_{j+1}$,...,$x_n$) = {$x_j$$\in$a| $\varphi$($x_1$,...,$x_n$)}

Proof: All of the functions $\mathscr F_1$,..., $\mathscr F_{10}$ can be obtained on the basis of $KP^{-}$. For instance, $KP^{-}$ is strong enough to prove the existence of the Cartesian product $a$ $\times$ $b$ of sets $a$ ans $b$ (see [Barwise: Admissible Sets ane Structures, Chapt. I, Theprem 3.2]). The result now follows from [Barwise, Ibid., Chapt II, Assumption 5.2(v)] because inspection of the proof of [Barwise, Ibid., Chapt. II, Assumption 5.2(v)] reveals that all of its steps can be done within $KP^{-}$.

Since $KP^{-}$ is a subtheory of $ZF$ $-$ Infinity, Lemma 2.5 holds for $ZF$ $-$ Infinity as well. Not that if one chooses to add Infinity back to $ZF$ $-$ Infinity one has that the proper class $V_{\omega}$ (= $L_{\omega}$) is now a set and is also constructible. Since $ZF$ $\vdash$ $\mathscr P_{L}$($\omega$) $\subseteq$ $\mathscr P$($\omega$) ($\mathscr P_{L}$ is the power-set for $L$ and is just $\mathscr P$($x$) $\cap$ $L$), Asaf's observation in his excellent answer (which is tantamount to saying that the constructibility or nonconstructibility of $\mathscr P$($\omega$) is independent of the axioms of set theory, i.e that though $\mathscr P$($\omega$) exists, it cannot be proven from the axioms of $ZF$ what subsets of $\omega$ are members of $\mathscr P$($\omega$)) seems to suggest (with the help of Rathjen's Lemma) that $ZF$ $\vdash$ $\mathscr P_{L}$ = $\mathscr P$ unless one adds the axiom "There exists a non-constructible set".

Since $KP^{-}$ is a subtheory of $ZF$ $-$ Infinity, Lemma 2.5 holds for $ZF$ $-$ Infinity as well. Not that if one chooses to add Infinity back to $ZF$ $-$ Infinity one has that the proper class $V_{\omega}$ (= $L_{\omega}$) is now a set and is also constructible. Since $ZF$ $\vdash$ $\mathscr P_{L}$($\omega$) $\subseteq$ $\mathscr P$($\omega$) ($\mathscr P_{L}$ is the power-set for $L$ and is just $\mathscr P$($x$) $\cap$ $L$), Asaf's observation in his excellent answer (which is tantamount to saying that the constructibility or nonconstructibility of $\mathscr P$($\omega$) is independent of the axioms of set theory, i.e that though $\mathscr P$($\omega$) exists, it cannot be proven from the axioms of $ZF$ what subsets of $\omega$ are members of $\mathscr P$($\omega$)) seems to suggest (with the help of Rathjen's Lemma) that $ZF$ $\vdash$ $\mathscr P_{L}$($\omega$) = $\mathscr P$($\omega$) unless one adds the axiom "There exists a non-constructible set of integers".

Since $KP^{-}$ is a subtheory of $ZF$ $-$ Infinity, Lemma 2.5 holds for $ZF$ $-$ Infinity as well. Not that if one chooses to add Infinity back to $ZF$ $-$ Infinity one has that the proper class $V_{\omega}$ (= $L_{\omega}$) is now a set and is also constructible. Since $ZF$ $\vdash$ $\mathscr P_{L}$($\omega$) $\subseteq$ $\mathscr P$($\omega$) ($\mathscr P_{L}$ is the power-set for $L$ and is just $\mathscr P$($x$) $\cap$ $L$), Asaf's observation in his excellent answer (which is tantamount to saying that the constructibility or nonconstructibility of $\mathscr P$($\omega$) is independent of the axioms of set theory) seems to suggest (with the help of Rathjen's Lemma) that $ZF$ $\vdash$ $\mathscr P_{L}$ = $\mathscr P$ unless one adds the axiom "There exists a non-constructible set".

Since $KP^{-}$ is a subtheory of $ZF$ $-$ Infinity, Lemma 2.5 holds for $ZF$ $-$ Infinity as well. Not that if one chooses to add Infinity back to $ZF$ $-$ Infinity one has that the proper class $V_{\omega}$ (= $L_{\omega}$) is now a set and is also constructible. Since $ZF$ $\vdash$ $\mathscr P_{L}$($\omega$) $\subseteq$ $\mathscr P$($\omega$) ($\mathscr P_{L}$ is the power-set for $L$ and is just $\mathscr P$($x$) $\cap$ $L$), Asaf's observation in his excellent answer (which is tantamount to saying that the constructibility or nonconstructibility of $\mathscr P$($\omega$) is independent of the axioms of set theory, i.e that though $\mathscr P$($\omega$) exists, it cannot be proven from the axioms of $ZF$ what subsets of $\omega$ are members of $\mathscr P$($\omega$)) seems to suggest (with the help of Rathjen's Lemma) that $ZF$ $\vdash$ $\mathscr P_{L}$ = $\mathscr P$ unless one adds the axiom "There exists a non-constructible set".