For languages $\mathcal{L} \subseteq \mathcal{L}',$ say that a set of sentences $\Delta$ in $\mathcal{L}'$ eliminates a model $M$ of $\mathcal{L}$ if no matter how the symbols of $\mathcal{L}' \setminus \mathcal{L}$ are interpreted in $M,$ $(M,\mathcal{L}') \not \models \Delta.$ (I don't know if there is a standard term). E.g., for $\mathcal{L}=\mathcal{L}'=\{+,\cdot \},$ PA eliminates models of Q without total exponentiation. More interestingly, $\text{Th}(\omega, +, \cdot)$ eliminates countable nonstandard models of $\text{Th}(\omega, +)$ with recursively defined addition by Tennenbaum's Theorem.

Since the multiplication operator makes it possible to eliminate some nonstandard models of Presburger arithmetic, I consider it to provide "information" about the structure of $\mathbb{N}.$ Is it possible to eliminate some nonstandard models of true arithmetic through additional symbols? Notice we only need to consider unary predicates. So more precisely,

1) Does $\text{Th}(\omega, +, \cdot, \mathcal{P}(\omega))$ eliminate some nonstandard model of true arithmetic? If yes, then

2) Is there some $S \subseteq \omega$ and $\varphi$ such that $(\omega, +, \cdot, S) \models \varphi$ and $\varphi$ eliminates some nonstandard model of true arithmetic?

A negative answer to 1 would seem to imply $\{+, \cdot\}$ provides all the information about $\mathbb{N}$ that is possible in first order logic. An affirmative answer to 2 would be interesting because then, if we're working in say ZFC + V=L, there would be a definable such predicate and sentence, meaning we'd have an explicit first-order fact about $\mathbb{N}$ not necessitated by true arithmetic.

  • 1
    $\begingroup$ An alternative formulation of Gödel's theorem is that $Th(\mathbb{N},+,\cdot)$ cannot be axiomatized in first order logic. $\endgroup$ – Rene Schipperus Sep 18 '16 at 15:13
  • $\begingroup$ Such theories cannot be recursively axiomatized. Obviously I'm interested in nonrecursive theories. $\endgroup$ – Elliot Glazer Sep 18 '16 at 15:14
  • $\begingroup$ Ok, so just take $Th(\mathbb{N},+,\cdot)$ as your theory. But it still wont eliminate nonstandard models. The most you can hope for in a first order context is some $T$ which is $\aleph_0$-categorical. $\endgroup$ – Rene Schipperus Sep 18 '16 at 15:17
  • $\begingroup$ This doesn't answer anything I asked in question. $\endgroup$ – Elliot Glazer Sep 18 '16 at 15:19
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – user642796 Sep 23 '16 at 7:24

For (2) now, here's a modification of the hyperarithmetic set approach, motivated by the almost-disjoint set argument:

There exists a recursive tree $T$ which has infinite branches but no hyperarithmetic infinite branches. (I think this is due to Kleene. Here's a reference: it's Corollary XLI(b) in Chapter 16, in Theory of Recursive Functions and Effective Computability, by Hartley Rogers, Jr.)

There is a sentence $\varphi$ (in the language of arithmetic expanded by an extra one-place relation symbol) such that $S$ is an infinite branch through $T$ iff $\langle \omega; +, \cdot; S\rangle \models \varphi.$

But no model $\langle M; +, \cdot; S\rangle$ which satisfies both $\varphi$ and true arithmetic can have $\langle M; +, \cdot\rangle$ be hyperarithmetic. That's because $S,$ restricted to standard integers, must be a standard branch through $T$ (since $T$ is recursive, any standard integer belongs to $T$ iff $M$ thinks it belongs to $T$). As in the argument with $\mathcal{O},$ let $k$ be an infinite integer in $M,$ and let $o \in M$ code the first $k$ many elements of $S.$ Then questions of the form $"\!\!x\in S\!"$ with $x\in\omega$ can be decided by asking arithmetic questions about $o$ in $\langle M; +, \cdot\rangle.$ Since $S$ isn't hyperarithmetic, $\langle M; +, \cdot\rangle$ can't be hyperarithmetic.

So, although there are hyperarithmetic nonstandard models of true arithmetic, none of them can (when augmented with an extra one-place relation) be models of $\varphi.$

Added: The connection with the almost-disjoint set argument is that the collection of branches through a tree is a family of almost disjoint sets.

  • $\begingroup$ I don't know enough recursion theory to verify this proof, so hopefully someone who does will. What would be the complexity of such an $S \subset \omega$? $\endgroup$ – Elliot Glazer Sep 18 '16 at 23:13
  • $\begingroup$ I think $S$ can be chosen to be $\Pi^1_1,$ if I remember my recursion theory correctly from 40 years ago :) . But all that's necessary for the argument is that no such branch can be hyperarithmetic. $\endgroup$ – Mitchell Spector Sep 18 '16 at 23:14
  • $\begingroup$ I was just curious because I wonder how definable a predicate that adds new information to $\mathbb{N}$, in the sense I have described, can be. $\endgroup$ – Elliot Glazer Sep 18 '16 at 23:33
  • $\begingroup$ $S$ can certainly be chosen to be recursive in a $\Pi^1_1$ set; I'm not certain right now whether it can be chosen actually to be $\Pi^1_1$ itself. If you wanted to find a simpler example, I'd look at a forcing argument, something like Feferman's arithmetic version of Cohen forcing. $\endgroup$ – Mitchell Spector Sep 18 '16 at 23:54

Here's an improvement on (1), with just a single predicate $S,$ but as @ElliotGlazer pointed out, it's not a solution to (2), since there isn't a single sentence $\varphi$ that eliminates some nonstandard model.

I'll leave it here, since it's too long for a comment anyway.

Take $S$ to be Kleene's $\mathcal{O},$ a complete $\Pi^1_1$ set of integers. If $\langle M; +, \cdot; S\rangle$ is any countable model of the theory of $\langle \omega; +, \cdot; \mathcal{O}\rangle,$ then $\langle M; +, \cdot\rangle$ can't be coded by a hyperarithmetic set. Here's why: Let $k$ be an infinite integer in $M.$ We can find a nonstandard integer $o$ in $M$ that codes the first $k$ elements of $S.$ It follows that $\mathcal{O}$ is Turing-reducible to any set of integers which codes $\langle M; +, \cdot\rangle$ (since a question of the form $"\!\!x\in\mathcal{O}"$ where $x\in\omega$ can be answered by asking arithmetic questions about $o$ in $\langle M; +, \cdot\rangle$).

But there are hyperarithmetic nonstandard models of true arithmetic; these are eliminated by passing from $\text{Th}\langle \omega; +, \cdot\rangle$ to $\text{Th}\langle \omega; +, \cdot; \mathcal{O}\rangle.$

  • $\begingroup$ This appears to be a strengthening of 1 but it doesn't quite answer 2. The idea of 2 is for there to be a single sentence in the expanded language which eliminates some nonstandard model. $\endgroup$ – Elliot Glazer Sep 18 '16 at 21:45
  • $\begingroup$ @ElliotGlazer: You're right. I edited the (non-)answer accordingly. $\endgroup$ – Mitchell Spector Sep 18 '16 at 21:51

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.