7
$\begingroup$

We have the result that $\mathsf{ZFCfin}$, the usual $\mathsf{ZFC}$ axioms with the axiom of infinity replaced by its negation, is bi-interpretable with $\mathsf{PA}$, first order Peano Arithmetic. We also know of a natural way to weaken $\mathsf{PA}$ into fragments, by restricting the induction axiom schema to forumlae of a specific complexity, so $\mathsf{Q+I\Sigma_3}$ is the non inductive axioms of $\mathsf{PA}$ plus induction restricted to formulae of at most $\mathsf{\Sigma_3^0}$ complexity in the language of first order arithmetic.

Does weakening the axiom of separation and the axiom of replacement in $\mathsf{ZFCfin}$ result in the above outlined fragments of $\mathsf{PA}$? For example, does weakening the two axiom schema to formulae of $\mathsf{\Sigma_3}$ complexity in the language of set theory give a set theory bi-interpretable with $\mathsf{Q+I\Sigma_3}$? Or does the axiom of powerset also need to be dropped and then replacement replaced with collection?*

If restricting separation and replacement is the correct way of getting bi-interpretable theories, does a theory bi-interpretable with $\mathsf{Q}$, Robinson Arithmetic, result from dropping both axiom schemes entirely?

*The reason I say this is because I know that $\mathsf{KP}$, Kripke-Platek set theory, does away with powerset and without powerset collection and replacement are not equivalent. I am wondering if that plays a factor and if it isn't too much for one question, if anyone can explain the interplay between getting rid of powerset and the strength of fragments of arithmetic.

$\endgroup$
6
$\begingroup$

First let me note that one should be careful with formulation of $\mathsf{ZFCfin}$, for it to be bi-interpretable with $\mathsf{PA}$ (see the paper "On interpretations of arithmetic and set theory" by Richard Kaye and Tin Lok Wong and the paper "$\omega$-models of finite set theory" by Ali Enayat, James H. Schmerl, and Albert Visser). Basically the issue is that for this bi-interpretation to work fine one either need to explicitly add to $\mathsf{ZFCfin}$ the axiom that every set is contained in a transitive set ($\mathsf{TC}$), or alternatively start with the axiomatization of $\mathsf{ZFC}$ where we have scheme of foundation instead of the axiom of regularity.

For fragments the situation is roughly speaking that the scheme $\Sigma_n\mbox{-}\mathsf{Sep}$ in set theory corresponds to the scheme $\Sigma_n\mbox{-}\mathsf{Ind}$ in arithmetic and the scheme $\Sigma_n\mbox{-}\mathsf{Rep}$ in set theory corresponds to the scheme $\mathsf{B}\Sigma_n$ in arithmetic. More formally, let us choose the following base system of set theory $$\mathsf{ZFfin}_1=\mathsf{Ext}+\mathsf{Pair}+\mathsf{Union}+\mathsf{TC}+\mathsf{Reg}+\Sigma_1\mbox{-}\mathsf{Sep}+\Sigma_1\mbox{-}\mathsf{Rep}+\lnot\mathsf{Inf}.$$ Note that although I haven't included powerset axiom in $\mathsf{ZFfin}_1$, it is provable there. This system is interpretable in $\mathsf{I}\Sigma_1$ by the Ackermann membership $\in_{\mathsf{Ack}}$ that is defined as follows: $$n\in_{\mathsf{Ack}} m \mbox{ iff the $n$-th bit in the binary expansion of $m$ is equal to $1$}.$$ In the other direction $\mathsf{ZFfin}_1$ interpretes $\mathsf{I}\Sigma_1$ by the ordinal arithmetics. With some efforts one could show that this two interpretations form a bi-interpretation. Further, for $n\ge 1$, it is easy to show that the theory $\mathsf{I}\Sigma_n=\mathsf{I}\Sigma_1+\mathsf{I}\Sigma_n$ proves that $\Sigma_n\mbox{-}\mathsf{Sep}$ holds in Ackermann interpretation and that the theory $\mathsf{ZFfin}_1+\Sigma_n\mbox{-}\mathsf{Sep}$ proves that $\Sigma_n\mbox{-}\mathsf{Sep}$ holds in ordinal arithmetic. This verifies the fact that $\mathsf{I}\Sigma_n$ and $\mathsf{ZFfin}_1+\Sigma_n\mbox{-}\mathsf{Sep}$ are bi-interpretable. By the same kind of argument $\mathsf{I}\Sigma_1+\mathsf{B}\Sigma_n$ and $\mathsf{ZFfin}_1+\Sigma_n\mbox{-}\mathsf{Rep}$ are bi-interpretable.

Note that the connection that I have outlined above really required using relatively strong theories: we need totality of exponentiation in arithmetic to prove even very basic facts about $\in_{\mathsf{Ack}}$ and due to this the approach wouldn't work if our base set theory wouldn't be able to prove totality of exponentiation in ordinal arithmetic. With a more refined approach it is possible to show bi-interpretability $\mathsf{I}\Delta_0+\mathsf{Exp}$ ($\mathsf{Exp}$ states totality of binary exponentiation function) and certain set theory that includes powerset axiom (see R. Pettigrew "On Interpretations of Bounded Arithmetic and Bounded Set Theory"). Although, strictly speaking, I don't know whether $\mathsf{Q}$ is bi-interpretable with $\mathsf{ZFCfin}-\mathsf{Sep}-\mathsf{Rep}$, it would be very strange for it to be the case.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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