Can the same set be decidable in a strong theory and undecidable in a weaker theory?
Some possible examples.
Goodstein's theorem says every Goodstein sequence, $g(n)$, eventually terminates. Goodstein's theorem can not be proven in first order Peano arithmetic(PA). Would the set of positive integers where g(n) terminates in an even number of steps be undecidable in a theory weaker than PA like primitive recursive arithmetic?
The set of non-negative integers encoding a Turing machine (TM) that halts on blank input is normally considered to be an undecidable set. If this set were decidable we could solve the halting problem. There are theories of hypercomputation where the halting problem is solvable for "standard" TM's. Would the set of integers encoding halting standard TM's be a decidable set in these hypercomputation theories?
Response to comments:
I am interested in Tennenbaum'a theorem. It says if addition or multiplication is recursive in a non-standard model of PA then we can encode a "non-recursive set" as a "non-standard natural number". I am trying to figure out what "non-recursive set" means in this context. Let $X$ be a set of standard natural numbers. $X$ is recursive in any non-standard model of PA because it is a subset of some hyper-finite set. Tennenbaum's argument seems to assume $X$ is a "non-recursive set" in the meta-theory.
Assume the meta-theory is ZFC and we can prove Goodstein's theorem. Then $X$ can't be the set of standard natural numbers where Goodstein's sequence terminates in an even number of steps because we know this set is recursive both in the non-standard model and in the meta-theory.
Since Tennenbaum's theorem applies to systems weaker than PA I can let PA be the meta-theory. Now, I can't prove Goodstein's theorem. Can the set that terminates in an even number of steps be considered non-recursive in this meta-theory?
It seems there are recursive sets we can't prove are recursive. If so, then any set might be recursive.
Best Answer
With regard to the deeper motivation behind this question: I think there's some confusions around exactly how to interpret nonstandard models. I'm going to focus on the very narrow question, "Can models disagree about the computability of certain definable sets?"
The first step is realizing that this is a bit vague. There's at least three ways I can see to interpret it:
Interpretation 1 (Internal). You give me a formula in the language of arithmetic - viewed as a definition of a set - $\varphi(x)$. Each model $M$ of $PA$ yields a set $\varphi^M$. Now, $\varphi^M$ is a subset of $M$, not $\mathbb{N}$, but $M$ can't tell the difference. The sentence $\psi\equiv$"$\{x: \varphi(x)\}$ is decidable(=computable)" is expressible in the language of arithmetic, as $$\psi\equiv\exists e_0, e_1\forall x[(\varphi(x)\iff \exists sT(e_0, x, s))\wedge (\neg\varphi(x)\iff\exists sT(e_1, x, s))],$$ where $T$ is Kleene's $T$ predicate: $T(e, x, s)$ means "the $e$th Turing machine halts on input $x$ in $s$ steps."
Okay, fix $\varphi$. We can now ask:
Interpretation 2 (External). You give me a formula in the language of arithmetic - viewed as a definition of a set - $\varphi(x)$. Each model $M$ of $PA$ yields a set $\varphi^M$. Now, $\varphi^M$ is a subset of $M$, but the standard model $\mathbb{N}$ injects into $M$ in a canonical way; call this map "$i_M$." So we can talk about the standard natural numbers which ($M$ thinks) the statement $\varphi$ is true of; that is, the set $$X_M=i_M^{-1}(\varphi^M).$$ This set $X_M$ is a genuine set of natural numbers, and we can ask whether $X_M$ is: computable, infinite, coinfinite, of asymptotic density 1, etc. For instance, in the Goodstein example, $X_M$ is the set of standard natural numbers which $M$ thinks have halting Goodstein sequences.
This "cutting off" process might seem unnatural, but it's actually really mathematically interesting: it's what standard systems, for instance, are all about.
Okay, fix $\varphi$. We can now ask:
Interpretation 3 (Mix-and-match). As in interpretation 1, we look at the whole set $\varphi^M$. However, we now look at standard indices for computable functions, interpreted in $M$. Specifically, say $\varphi^M$ is mix-and-match-computable in $M$ if there is there some standard natural number $n$ such that $M$ thinks $\Phi_n$ is a total computable function such that $\Phi_n$ is the characteristic function of $\varphi^M$.
Okay fix $\varphi$. We can now ask:
Despite the heterogeneous nature of this question, I suspect it too has its place in your intuition: basically, this question is asking, "Is there a genuine algorithm which, consistently, solves this problem?"
Now, what about your actual question? Well, we can exhibit formulas $\varphi$ such that there are models exhibiting divergent behavior in each of the three interpretations. This is actually pretty easy to do: we just shoehorn in some known undecidability. For instance, consider the formula $$\varphi(x)\equiv [\neg Con(PA) \wedge x\not=x]\vee[Con(PA) \wedge \exists s(T(x, x, s)].$$ In a model of $PA$ which thinks $PA$ is inconsistent, $\varphi$ just denotes the empty set, but in any model of $PA$ which thinks $PA$ is consistent - such as the standard one - $\varphi$ denotes that model's halting problem, which that model will think is incomputable. This might seem a bit trivial - it certainly does to me - but there's not an obvious way I can see to "carve out" such trivial solutions. (Maybe someone here can think of one!)