Theory Synonymous with PA – Set Theory Examination

lo.logicset-theorytheories-of-arithmetic

Language: Mono-sorted first order logic with equality.

Extralogical Primitives: $<, \in$

Define: $x \leq y \iff x < y \lor x=y$

  • $\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land y < z \to x < z \\ \textit{Connective:} \ x \neq y \leftrightarrow (x < y \lor y < x) \\ \textit{Well founded:} \ \exists n \in x \to \exists n \in x \forall m \in x (n \leq m)$

  • $\textbf{Finiteness: }\exists n \in x \to \exists n \in x \forall m \in x (m \leq n)$

  • $\textbf{Sets: } \forall n \exists! x \forall m (m \in x \leftrightarrow m \leq n \land \phi)$, if $x$ is not free in formula $\phi$.

Is this theory synonymous with $\sf PA$?

Best Answer

$\def\pa{\mathsf{PA}}\def\zff{\mathsf{ZF_{fin}}}\def\zffm{\mathsf{ZF_{fin}^-}}$Your theory (let me denote it $T$ for the moment) is mutually interpretable with $\pa$, but it is not bi-interpretable with $\pa$, and a fortiori not synonymous.

On the one hand, it is easy to see that $\pa$ interprets $T$ using Ackermann’s interpretation ($n\in x$ iff the $n$th bit in the binary expansion of $x$ is $1$), as mentioned in Joel’s answer.

For an interpretation of $\pa$ in $T$, it is easiest to make a short detour through classical results (by now folklore) on finite set theory, due to Mycielski, Vopěnka, and Sochor (apparently). $\pa$ is bi-interpretable with the theory $\zff$ of finite sets, which can be axiomatized by

  1. Extensionality

  2. Existence of $\varnothing$

  3. Existence of $x\cup\{y\}$ for all $x$ and $y$

  4. Induction: $\phi(\varnothing)\land\forall x,y\,\bigl(\phi(x)\to\phi(x\cup\{y\})\bigr)\to\forall x\,\phi(x)$

  5. $\in$-induction: $\forall x\,\bigl(\forall y\in x\,\phi(y)\to\phi(x)\bigr)\to\forall x\,\phi(x)$

Moreover, the theory $\zffm$ axiomatized by 1–4 interprets $\zff$ (hence $\pa$), namely it proves axioms of $\zff$ relativized to the class WF of hereditarily well-founded sets: $x$ is in WF iff there is a transitive set $y\supseteq x$ such that every nonempty subset of $y$ has an $\in$-minimal element. (It is a longish but straightforward exercise to show that $\zffm$ proves all the usual axioms of $\def\zfc{\mathsf{ZFC}}\zfc$ except infinity and foundation; some of these may be useful for verification of this interpretation.) (NB: In recent literature stemming from a rediscovery of some of these results, the notation $\zff$ is used for a weaker theory that only has $\zfc$-style foundation axiom in place of $\in$-induction, and our $\zff$ is denoted $\zff+\mathsf{TC}$ or the like. I will keep the notation $\zff$ for the stronger theory as I have no use for the weaker one in my answer.)

Now, I claim that $T$ proves $\zffm$. Axioms 1–3 are straightforward. For 4, first note that $T$ proves that every element $x$ other than the minimal element $0$ has a predecessor (as $\{y:y<x\}$ has a maximal element) and successor $S(x)$ (in particular, as mentioned in paste bee’s answer, there is no largest element, as otherwise $\{x:x\notin x\}$ would exist, leading to Russell’s paradox). Using Sets and Well-founedness, $T$ proves order induction $$\forall x\,\bigl(\forall y<x\,\phi(y)\to\phi(x)\bigr)\to\forall x\,\phi(x),$$ which together with predecessor implies usual induction $$\phi(0)\land\forall x\,\bigl(\phi(x)\to\phi(S(x))\bigr)\to\forall x\,\phi(x).$$ Let $\|x\|<n$ denote $\forall y\in x\,y<n$. Then given a formula $\phi(x)$, $T$ proves the formula $\psi(n)\equiv$ $$\phi(\varnothing)\land\forall x,y\,\bigl(\phi(x)\to\phi(x\cup\{y\})\bigr)\to\forall x\,\bigl(\|x\|<n\to\phi(x)\bigr)$$ by induction on $n$: if $\|x\|<0$, then $x=\varnothing$, which satisfies $\phi$ by the premise. Assuming $\psi(n)$, if $\|x\|<S(n)$, then either $\|x\|<n$ and $\phi(x)$ holds by the induction hypothesis; or $n\in x$ and $x'=x\smallsetminus\{n\}$ satisfies $\|x'\|<n$, thus $\phi(x')$ by the induction hypothesis, thus $\phi(x'\cup\{n\})$ using the premise, i.e., $\phi(x)$. Then $\forall n\,\psi(n)$ implies 4 as every $x$ satisfies $\|x\|<n$ for some $n$ using Finiteness.

$\def\N{\mathbb N}$Finally, to show that $\pa$ is not bi-interpretable with $T$, the key observation is that $T$ has lots of nonisomorphic (and not elementarily equivalent) standard models. Here, I call a model $(M,<,\in)\models T$ standard if $(M,<)$ is well founded (necessarily of order-type $\omega$). For every permutation $\sigma\colon\N\to\N$, we have $\N_\sigma=(\N,<,\in_\sigma)\models T$, where $$n\in_\sigma x\iff\text{the $n$th bit of $\sigma(x)$ is $1$.}$$

Now, assume for contradiction that $F$ is an interpretation of $\pa$ in $T$ and $G$ is an interpretation of $T$ in $\pa$ such that $F\circ G$ is definably isomorphic to the identity self-interpretation of $T$. Fix permutations $\sigma\ne\tau$. Then $F$ induces models $\N_\sigma^F$ and $\N_\tau^F$ of $\pa$, and $G$ induces a copy of $\N_\sigma$ definable in $\N_\sigma^F$ and a copy of $\N_\tau$ definable in $\N^F_\tau$, using the same definitions. Since $\N_\sigma^F$ has full induction schema, it can define an embedding $f$ of the universe into the internal copy of $\N_\sigma$ such that $f(0)$ is the least element of $\N_\sigma$, and $f(n+1)$ is the successor (as computed in $\N_\sigma$) of $f(n)$. Since $f$ is an order embedding into a well-ordered set, its domain must be well ordered as well: that is, $\N_\sigma^F$ must be isomorphic to the standard model $\N$ of $\pa$.

The same argument applies to $\N_\tau^F$, thus in particular, $\N_\sigma^F\simeq\N_\tau^F$. But then their internal models of $T$, viz. $\N_\sigma$ and $\N_\tau$, must be isomorphic as well, as they are defined by the same formulas. This is a contradiction, as $\N_\sigma$ and $\N_\tau$ are not even elementarily equivalent (they disagree on some sentences of the form $\overline n\in\overline m$, where $\overline n$ denotes the $n$th least element according to $<$).

Note that we have used only one half of the definition of bi-interpretability, thus the argument above actually shows that $T$ is not an interpretation retract of $\pa$.


Let me add that in order to get a theory synonymous with $\pa$ (or equivalently, $\zff$), it is enough to extend $T$ with the two axioms $$\let\eq\leftrightarrow\begin{align} \tag1n\in x&\to n<x,\\ \tag2x<y&\eq\exists n\,\bigl(n\in y\land n\notin x\land\forall m>n\,(m\in x\eq m\in y)\bigr). \end{align}$$ (In fact, it is sufficient to keep only one implication (either one) of the outer bi-implication in (2); the other one then follows using axioms of $T$. On the other hand, it’s quite possible some of the axioms of $T$ can be simplified in the presence of (1) and (2).)

Since $T$ proves order induction, (1) ensures that the theory includes $\in$-induction, and therefore all of $\zff$. Then (2) ensures that $x<y$ is equivalent to an inductive definition in terms of $\in$ alone (coinciding with the usual order on $\omega$ lifted by Ackermann’s bijection between $\omega$ and $V_\omega$). Thus, the resulting theory is equivalent to an extension of $\zff$ by a definition.

Note that (1) alone is not enough to make the theory bi-interpretable with $\pa$, as $\N_\sigma\models(1)$ whenever $\sigma$ satisfies $\sigma(x)<2^x$ for all $x\in\N$, thus the argument above still applies.

Related Question