1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    May 26, 2020 at 7:02

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.