Let $\Sigma = \left\{ 0,1,+,\times , < \right\}$ be a signature, where the last 3 symbols have arity 2 and all except the last symbol are functions symbols. How can I prove that the set $X=\left\{ \ulcorner A \urcorner \ : \mathbb{N} \vDash A \right\}$, where $ \ulcorner A \urcorner $ is the code of the $\Sigma$ formula $A$, and "$\vDash$" means "is a model of", is not arithmetic ?

I can use the fact that the set $$B=\left\{ (c,n)\in \mathbb{N}^2\left| \begin{array}{l} c= \ \ulcorner T \urcorner\text{, where } T \text{ is a } \Sigma \text{ formula that}\\ \text{ has only } v_0 \text{ as a free variable, and }\mathbb{N} \vDash T_{v_0 \rightarrow \underline{n}} \end{array}\right.\right\},$$ where $A_{v_0 \rightarrow \underline{n} }$ is the $\Sigma$ formula were the variable $v_0$ in $T$ is replaced with the term $ \underline{n}$ (that corresponds to the number $n$ meaning $ \underline{n}=++\ldots+011\ldots1$, where there are $n$ additional symbols) is not arithmetic.

What I got until now is the following: I supposed, that $X\subseteq \mathbb{N}$ were arithmetic. Thus there exists a $\Sigma$ formula $\psi$ which has exactly one free variable $v$ such that $\psi_\mathbb{N}=X$ (we have defined $\psi_\mathbb{N} =$ {$ m \in \mathbb{N}: \mathbb{N} \vDash \psi_{v \rightarrow \underline{m}} $} - and if the formula contains 2 free variables, the definition changes accordingly). Thus I can plug $\psi$ in the set $B$. But this is the point from which on I don't kniw how to continue - and I haven't yet used the fact that $B$ is not arithmetic as well.

(For more info, as to how $\Sigma$ formulas etc. were defined in my course, see this post)

  • $\begingroup$ and in a couple of other places too....corrected now. thanks. $\endgroup$ – temo Jun 30 '11 at 5:52

Here are two separate proofs.

  • First, if your set $X$ were arithmetic, then it would have complexity $\Sigma_n$ for some specific natural number $n$. But in this case, we would be able to express the truth of $\Sigma_{n+1}$ statements, or indeed, $\Sigma_m$ statements for any $m$, using only complexity $\Sigma_n$, by saying that a $\Sigma_{n+1}$ statement $\varphi$ holds at $\vec n$ iff ${}^\ulcorner\varphi(\vec n){}^\urcorner\in X$. Thus, the arithmetic hierarchy would collapse at the level of $\Sigma_n$. But the arithemetic hierarchy does not collapse. This can be proved first by proving that there is a universal $\Sigma_1$ set, which cannot be $\Pi_1$ by a simple diagonalization argument, and then proving that there is a universal $\Sigma_n$-set for each $n$, which cannot be $\Pi_n$.

  • The second proof, note that your claim is exactly Tarski's theorem on the non-definability of truth, and there is an elegant proof via the fixed point lemma. Namely, suppose that we had an arithmetic say to say that "$\varphi(\vec n)$ is true", that is, a formula $\psi$ such that $\mathbb{N}\models\psi(^\ulcorner\varphi(\vec n)^\urcorner)\iff\varphi(\vec n)$. By the fixed point lemma, there is a sentence $\sigma$ such that PA proves $\sigma\iff\neg\psi(^\ulcorner\sigma^\urcorner)$. Thus, $\sigma$ asserts that $\sigma$ is not true, just like the liar paradox. It is easy to see that this is contradictory, since if $\sigma$ is true then it isn't and conversely.

It is interesting to observe that Tarski's theorem can be seen as a much stronger version of Gödel's incompleteness theorem. This is because one version of the incompleteness theroem says that the true theory of arithmetic is not computably axiomatizable. But this follows immediately from Tarski's theorem, since if the true theory of arithmetic were computably axiomatizable, then it would be easily definable, with complexity $\Sigma_1$, since we could define the set of true assetions as those that are provable in the system. Meanwhile, Tarski's theorem says not only is there no computably axiomatizable complete axiomatization of true arithemtic, but that there is no arithmetically definable axiomatization of true arithmetic.

It is also interesting to note that Tarski is credited both with giving the recursive first-order definition of truth and proving that truth is not definable. (But despite superficial appearances, these claims do not conflict.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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