Definable classes of sentences despite Tarksi's Theorem

43 Views Asked by At

In number theory, I know that Tarski's Theorem rules out the possibility of the existence of a predicate which is true precisely for the Godel numbers of sentences which are true. However, do there exist predicates which are true precisely for Godel numbers of true sentences confined to particular infinite classes? One example would be the class of all sentences having only bounded quantifiers. Are there others allowing for unbounded quantifiers (besides trivial ones in which a bounded variable is totally extraneous, that is it does not appear in the rest of the sentence)?

1

There are 1 best solutions below

2
On BEST ANSWER

You use "decidable" in the title, but focus on definability in the body of the question - I'm assuming you mean the latter.

For each $n$, there is a $\Sigma_n$ formula defining in $\mathbb{N}$ the set of (Godel numbers of) true $\Sigma_n$ sentences. So for each "layer" of the arithmetical hierarchy we do in fact have definable truth. Note that local truth definitions like this don't run afoul of Tarski since the relevant classes of sentences are not closed under negation: if $\varphi\in\Sigma_n$ then $\neg\varphi\in\Pi_n$, but $\Pi_n\not=\Sigma_n$.

Incidentally, the analogous situation holds in set theory with the Levy hierarchy in place of the arithmetical hierarchy.