## Archive for September 13th, 2010

### Statement of Tarski’s Theorem

September 13, 2010

The theorem showing that the theory determined by the standard model of arithmetic, $\mathsf{Th} (\Omega)$, is undecidable and consequently not decidably axiomatizable (this means that $\mathsf{Th} (\Omega) \not= \mathsf{Th} (\Gamma)$, for some $\Gamma$ consisting of axioms of arithmetic, like those of Peano Arithmetic or one of it’s extensions) can be made stronger by showing that $\mathsf{Th}(\Omega)^{\#} := \{p: \chi_{p} \in \mathsf{Th}(\Omega)\}$,  the set of indices of sentences that are true in $\mathsf{Th} (\Omega)$, is not definable over $\Omega$, which means that $\mathsf{Th}(\Omega)$ is not effectively enumerable.  This is known as Tarski’s Theorem on the undefinability of truth.

Now set up the (provably effectively computable) function $\mathsf{Sb}(m):= \#(\chi_{m}(\dot{m}))$, which returns the least number $m$ such that $\chi_{m}$ is a formula of $\textup{L}_{\Omega}$.

In the next update I’ll discuss the proof of Tarski’s Theorem and move into the corollary that Hellman uses to give an example of determination without reduction.