3
$\begingroup$

If we remove the axiom that zero doesn't have a predecessor, and stipulate that every natural number has a predecessor, and that no number is the successor of itself. And keep all other axioms of $\small \sf PA$, and introduce a new primitive relation symbol $``<"$ to signify strictly smaller than relation, and axiomatize that each $n^{th}$ successor of zero [for a meta-theoretic $n$] is strictly smaller than its successor, and that $<$ is asymmetric and transitive.

Formally this is the first order theory with axioms of:

axioms of first order $\small \sf PA$ minus $\not \exists x (S(x)=0)$ plus:

  1. $\forall x \exists y: S(y)=x$
  2. $S(x) \neq x$

Define recursively: $S_0(0) = 0 \\ S_{i+1}(0)=S(S_i(0))$

  1. For $n=1,2,3,....\\ S_n(0) < S_{n+1}(0)$

  2. $x < y \to \neg \ y < x$

  3. $ x < y < z \to x < z$

This is what I term as $\small \sf cyclic \ PA$ or $\small \sf cPA$

Question: is there an interpretation of $\small \sf cPA$ in $\small \sf PA$?

$\endgroup$
2
  • 3
    $\begingroup$ Yes. This is a locally finitely satisfiable, recursively axiomatized theory, hence by a result of Albert Visser, it is interpretable even in Robinson’s theory $R$. Of course, interpretations in PA can be obtained more easily in a more direct way using the fact that any interval $[0,a]$ in a model of PA (or $I\Delta_0$) with $a$ nonstandard satisfies the theory. There have been many questions about this theory without ordering posted on MO a couple of years ago (under the name “modular arithmetic”), by the way. $\endgroup$ Jul 8, 2019 at 10:28
  • $\begingroup$ @EmilJeřábek, can you post this as an answer with some detail?! $\endgroup$ Jul 8, 2019 at 10:50

1 Answer 1

6
$\begingroup$

The theory cPA is interpretable already in Robinson’s theory $R$ by a result of Albert Visser [1], because it is recursively axiomatized and locally finitely satisfiable, meaning that every finite subtheory of cPA has a finite model. Indeed, a finite subtheory of cPA only mentions finitely many axioms 3, hence it is satisfied for sufficiently large $n\in\mathbb N$ in the model $(\{0,\dots,n-1\},0,S,{+},{\cdot},{<})$, where the arithmetic operations are computed modulo $n$.

An explicit interpretation of cPA in PA (or even in $I\Delta_0$, which is itself well-known to be interpretable in $Q$) can be constructed as follows. First, PA interprets its own extension $\mathrm{PA}+\phi$ which proves the existence of a nonstandard definable element $a$: for example, we may take $\phi=\neg\mathrm{Con_{PA}}$, and let $a$ be the least code of a proof of contradiction in PA. Then we interpret cPA by making the domain of interpretation be the interval $\{x:x<a\}$ with the induced ordering, and operations computed modulo $a$.

Reference:

[1] Albert Visser: Why the theory R is special. In: Foundational Adventures: Essays in Honor of Harvey M. Friedman (N. Tennant, ed.), Tributes vol. 22, College Publications, London, 2014. LGPS preprint no. 279.

$\endgroup$
2
  • $\begingroup$ if we add $ P_{n+1}(0) < P_n(0) $ Where $P$ is for Predecessor, and $P_i$ is defined recursively in a similar manner to $S_i$ but with respect to predecession. Would the same proof hold $\endgroup$ Jul 8, 2019 at 15:51
  • $\begingroup$ Yes, you just change the interpretation of the ordering (say, put elements of $\{\lceil a/2\rceil,\dots,a-1\}$ below $0$ so that they represent negative numbers $\{\lceil a/2\rceil-a,\dots,-1\}$). $\endgroup$ Jul 8, 2019 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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