# Many-one reductions between the set of true sentences and a particular arithmetical set

Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic.

Let TH(N) = {ϕ : ϕ is a first order sentence in the language of arithmetic and N |= ϕ} (Where N is the standard model of arithmetic - , x, <, +, 0, and the successor; S)

Let γ(x) be some formula with exactly one free variable, namely x. Then assume X = {n : γ(n)} to be the arithmetical subset of the natural numbers defined by γ(x).

My question is: Is there a way to show either of X or TH(N) many one-reduce to each other?

• Welcome to COMPUTERSCIENCE @SE. [Newbie not sure about] the best way to get help There is a help centre including How do I ask a Good Question? My favourite advice is Picture yourself addressing a peer busy with something else. Commented May 26, 2020 at 7:02

For any such $$X$$ we have $$X\le_mTh(\mathbb{N})$$ but not conversely (and in fact $$Th(\mathbb{N})$$ is vastly more complicated than $$X$$).
To see that $$X\le_mTh(\mathbb{N})$$, we want to translate a question of the form "Is $$n\in X$$?" into one of the form "Is $$\psi_n$$ a true sentence?" for some appropriate sentence $$\psi_n$$. Now "$$n\in X$$" is equivalent to "$$\gamma(n)$$," and that's almost a sentence in the language of arithmetic - the only issue is that "$$n$$" isn't a symbol in the language of arithmetic (which consists only of $$0,1,+,\times,<$$). Do you see a quick way around this?
Each natural number $$n$$ has a corresponding numeral, usually denoted "$$\underline{n}$$," which is just an appropriate string of the symbols $$0$$," "$$1$$," "$$($$," and "$$)$$" (or is the symbol "$$0$$" if $$n$$ is $$0$$): e.g. $$\underline{4}$$ is the string $$((1+1)+1)+1$$. Then if we let $$\psi_n=\gamma(\underline{n})$$, we have that $$\psi_n\in Th(\mathbb{N})$$ iff $$n\in X$$.
Note that here I'm conflating e.g. the number $$0$$ and the constant symbol $$0$$; this is annoying, but standard.
The other direction is a consequence of Tarski's undefinability theorem: just show that anything many-one reducible (or even Turing-reducible) to an arithmetically definable set is itself arithmetically definable. This will show that we never have $$Th(\mathbb{N})\le_mX$$ (or even $$\le_TX$$) for such an $$X$$. The key here is to show that the basic notions of computability theory are arithmetically definable:
Use Kleene's $$T$$-predicate to talk about computable reductions.