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

Question

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?

Answer 1

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.