# When is a Decidable Set Decidable?

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?

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.

• Especially when you're working over a panopoly of theories, you need to be very careful about explicitly defining your terms. I suspect that once you settle on a specific definition of 'decidable' then the answer, either positive or negative (and there are IMHO reasonable interpretations that would give either answer) should be almost tautological. Commented Mar 13, 2014 at 1:01
• The statement "a set $A \subseteq \mathbb{N}$ is decidable" means there is an algorithm to determine which numbers are in $A$. This definition doesn't reference any formal theory. So you need to explain what you mean by a set being "decidable in a strong theory", because it is not a standard concept. For example, what is the formal definition you are thinking of for "the set of natural numbers whose Goodstein sequence ends with even length is decidable in PRA"? Commented Mar 13, 2014 at 1:03
• I suspect Russell is confusing two different uses of the term "undecidable". We have "undecidability in a formal theory" which applies to a sentence and refers to its unprovability. And then we also have "undecidability in a computability setting" which applies to a family (set) of finite objects and refers to the fact that this set cannot be computed by a Turing machine. For this second use there are some people which have advocated for using the word "uncomputable" instead of "undecidable", in order to avoid these misunderstandings. Commented Mar 13, 2014 at 9:30
• If a statement is undecidable in a theory it is possible the statement is false in some models of the theory. I am pretty sure Goodstein's theorem is false in non-standard models of PA. If multiplication is non-recursive, I think Goodstein's algorithm must also be non-recursive. If we can't prove a particular algorithm halts on every input how can we claim the algorithm decides a set? Commented Mar 13, 2014 at 20:29

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:

Is there a model $M$ which satisfies $\psi$? $\neg \psi$?

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:

Is there a model $M$ such that $X_M$ is computable? Non-computable?

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:

Is there a model $M$ such that $\varphi^M$ is mix-and-match computable in $M$? Non-mix-and-match computable in $M$?

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!)

• I think I am more interested in what you call the internal interpretation. Consider the set of all n where Goodstein's sequence terminates. Clearly, there is a TM that decides this set. In the standard model this TM returns True on any input and halts. There could be a non-standard model of PA where only one number has a non-terminating Goodstein sequence. How can PA decide between the TM that halts on any input and the TM that halts for all but one input? I think your external interpretation is simple. All models have to agree on which standard numbers have terminating Goodstein sequences. Commented Sep 23, 2015 at 2:19