15
$\begingroup$

The title is slightly misleading, since the theory I'm looking at is an extension of PA; however, the question is "morally" about very weak arithmetic.

Specifically, consider the following theory PA':

  • The language of PA' consists of the usual language of PA - namely, $+,\times,0,1$ - together with a new unary predicate symbol $C$.

  • The axioms of PA' consist of the usual PA axioms together with "$C$ is downwards closed, contains $0$, and is closed under successor." Crucially, we do not extend the induction scheme to formulas involving the new symbol "$C$."

A model of PA' consists then of a model $N$ of PA together with an initial segment $C$ closed under successor; this $C$ is in general very poorly behaved, and in particular even though $N$ itself satisfies a very strong arithmetic we can't even show that $C$ is closed under addition! Note that this relies on the fact that we didn't extend the induction scheme to formulas involving $C$.

Nonetheless, there is a sense in which - working within any model of PA' whatsoever - we can find "well-behaved" cuts inside $C$ (this is due to Nelson):

  • We can find a definable initial segment of $C$ which is closed under successor and addition.

  • We can even find a definable initial segment of $C$ which is closed under successor and addition and multiplication.

However, the proofs of the above facts which I know rely on associativity; they thus fail when we try to move to exponentiation. My question is whether this is in fact unavoidable:

Question. Does every model of PA' necessarily have a definable initial segment of its $C$ which is closed under successor, addition, multiplication, and exponentiation?

Note that while exponentiation isn't in the language of PA, PA is strong enough to define it and prove basic facts about it, so this is fine. Moreover, note that the above is a bit redundant - from closure under successor and exponentiation we get closure under addition and multiplication - but meh.

See this earlier question of mine for proofs of the above facts; I'm omitting them since Eric Wofsey showed that not only do their proofs not generalize to exponentiation, the construction involved can't even work here, so they really are irrelevant.

$\endgroup$
  • 1
    $\begingroup$ Incidentally, the linked earlier question of mine includes the context in which this problem arose; since that context led to a lot of irrelevant discussion, I'm omitting it here - I am truly not interested in the philosophical issues here, only the mathematical problem above. $\endgroup$ – Noah Schweber Oct 14 '18 at 18:18
  • $\begingroup$ Minor request for clarification: the bit where you say ... "$N$ itself satisfies a very strong arithmetic" seems to be missing a word or two. $\endgroup$ – Rob Arthan Oct 14 '18 at 19:55
  • $\begingroup$ Second minorrequest for clarification: the initial segment you are interested in is presumably required to be definable. $\endgroup$ – Rob Arthan Oct 14 '18 at 20:21
  • 1
    $\begingroup$ @RobArthan I've added the definability requirement, that was a silly omission; but "very strong arithmetic" was correct (e.g. I$\Sigma_1$ is a fairly weak arithmetic, PA is in my opinion a very strong arithmetic, etc.). I could see preferring "very strong theory of arithmetic," but I did write what I intended to. $\endgroup$ – Noah Schweber Oct 15 '18 at 4:31
  • $\begingroup$ "satisfies a very strong arithmetic" is the phrase my first comment was about. I'm sure it's just a typo but I still can't figure out what it means. $\endgroup$ – Rob Arthan Oct 15 '18 at 22:40
2
$\begingroup$

This is only a partial positive answer and it's far from optimal.

The statement is that if $\mathfrak{N}$ is a model of PA and $M\subseteq N$ is any cut (closed under successor) then $\mathfrak{M}$ (which as per your question we'll assume is closed under addition and multiplication) interprets $I\Delta_0 + \text{Exp}$ (using a parameter, although I think the parameter can be removed), where $\text{Exp}$ is the axiom that says that $x\mapsto 2^x$ is a total function. This is a slightly different question than the one you asked because on the one hand this is an interpretation, not an initial segment, but on the other hand we're not using the full structure $\mathfrak{N}$, just the cut. The reason why this might indicate that your actual question has a positive answer is that the proof that Robinson arithmetic does not interpret $I\Delta_0+\text{Exp}$ goes through the fact that $I\Delta_0+\text{Exp}$ proves the consistency of Robinson arithmetic, but any structure like $\mathfrak{M}$ satisfies all the $\Pi_1$ consequences of PA, and in particular the consistency of Robinson arithmetic, so that proof can't work to resolve your question.

The proof works in two cases, but these can be combined into a single first-order interpretation (with a parameter).

Note that $\mathfrak{M}\models I\Delta_0$, so in particular the graph of the function exponential function, $y = 2^x$ is a definable predicate in $\mathfrak{M}$ and it proves that the inductive properties of $2^x$, in particular if $2^x$ exists, then $2^{x+1}$ exists as well. Either $\mathfrak{M} \models \text{Exp}$ in which case we are done or by arguments in 'Interpretability in Robinson's Q' by Ferreira and Ferreira, there is a definable cut $C$ of $\mathfrak{M}$ such that $C \models I\Delta_0 + \Omega_2 + B\Sigma_1$, which also has a proper definable sub-cut $C^{\prime}$ such that for any $x\in C^{\prime}$, $2^{2^x}\in C$ and such that $C^{\prime}$ is closed under addition and multiplication. The point is that $I\Delta_0 + \Omega_2 + B\Sigma_1$ is enough to define the "$x$th binary bit of $y$" function and so we can code infinite subsets of $C^{\prime}$ in the binary expansions of numbers in $C$.

PA proves $\text{Con}(T)$, for any finite fragment $T$ of PA, including one big enough to prove that $x^y$ is a total function, so by the arithmetized completeness theorem there is a definable interpretation of $T$ in $\mathfrak{N}$, with constants for $0$ and $1$ and a function symbol for $x^y$. I claim that we can arrange this interpretation so that $0$ and $1$ are coded by standard numbers (i.e. $0$ and $1$) and that for any elements $x$ and $y$, the codes $\ulcorner x+y \urcorner$, $\ulcorner x\cdot y \urcorner$, and $\ulcorner x^y \urcorner$ are all less than or equal to $6 (\ulcorner x \urcorner + \ulcorner y \urcorner + 1)^2$ or so, all that matters is that it's a polynomial bound.

This follows from the fact that the standard Cantor pairing function is a polynomial, so the interpretation will be given by a definable predicate $I(x)$ and the functions $x+y$, $x\cdot y$, and $x^y$ will be interpreted by fixed polynomial expressions.

Now we can find a non-standard number $N\in C \setminus C^{\prime}$ such that $2^N \in C$ and we find a non-standard number $M \in C \setminus C^{\prime }$, with $M \leq 2^N - 1$, whose binary expansion corresponds to the first $N-1$ bits of $I(x)$. This gives us a parameter from which $C$ can define $C^\prime \cap I$, which by construction is closed under the polynomial expressions interpreting the functions $x+y$, $x\cdot y$, and $x^y$. Thus $C$ (and therefore $\mathfrak{M}$) interprets a structure closed under addition, multiplication, and exponentiation all obeying the correct inductive definitions and identities (as well as any finite collection of $\Pi_1$ consequences of PA that you want).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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