7
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ An alternative formulation of Gödel's theorem is that $Th(\mathbb{N},+,\cdot)$ cannot be axiomatized in first order logic. $\endgroup$ Commented Sep 18, 2016 at 15:13
  • 1
    $\begingroup$ Such theories cannot be recursively axiomatized. Obviously I'm interested in nonrecursive theories. $\endgroup$ Commented Sep 18, 2016 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$ Commented Sep 18, 2016 at 15:17
  • 1
    $\begingroup$ This doesn't answer anything I asked in question. $\endgroup$ Commented Sep 18, 2016 at 15:19
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – user642796
    Commented Sep 23, 2016 at 7:24

2 Answers 2

5
$\begingroup$

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.$

$\endgroup$
2
  • $\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$ Commented Sep 18, 2016 at 21:45
  • $\begingroup$ @ElliotGlazer: You're right. I edited the (non-)answer accordingly. $\endgroup$ Commented Sep 18, 2016 at 21:51
4
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Commented Sep 18, 2016 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$ Commented Sep 18, 2016 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$ Commented Sep 18, 2016 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$ Commented Sep 18, 2016 at 23:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .