## Archive for September 14th, 2010

### Tarski’s Theorem

September 14, 2010

Today we’re going to follow Hinman’s proof of Tarski’s theorem. The proof is by contradiction, and employs diagonalization. First, assuming clauses (i)-(iii) on definability, a universal $\textup{U}$-section for the class of $\Omega$-definable sets is established and it’s diagonal is shown to not be definable over $\Omega$.

A $\textup{U}$-section is a set defined for any set $\textup{A}$ and any relation $\textup{U} \subseteq \textup{A} \times \textup{A}$ such that for each $a \in \textup{A}$, $\textup{A}_{a} := \{b : \textup{U}(a, b)\}$$\textup{U}$ is universal for a class $\mathcal{C} \subseteq \wp (\textup{A})$ if, and only if, every member of the class $\mathcal{C}$ is a $\textup{U}$-section.  The diagonal set of $\textup{U}$ is $\textup{D}_{\textup{U}} := \{a : \textup{U}(a, a)\}$.

Second, assuming the definability of $\mathsf{Th}(\Omega)^{\#}$, there is a formula $\phi (y)$ such that for all $p$, $p \in \mathsf{Th}(\Omega)^{\#} \Longleftrightarrow \phi (\dot{p}) \in \mathsf{Th}(\Omega)$.  But since the function $\mathsf{Sb}$ is effectively computable, it is definable  and so, $\mathsf{Sb}(m) = p \Longleftrightarrow \psi (\dot{m}, \dot{p}) \in \mathsf{Th}(\Omega)$, for some $\psi (x, y)$.  But this means that,

$m \in \textup{D}_{\textup{U}} \Longleftrightarrow \exists p [\phi(\dot{p}) \in \mathsf{Th}(\Omega)$ and $\psi(\dot{m}, \dot{p}) \in \mathsf{Th}(\Omega)]$

$m \in \textup{D}_{\textup{U}} \Longleftrightarrow \exists y [\phi(y) \wedge \psi(\dot{m}, y)] \in \mathsf{Th}(\Omega)$,

which means that $\textup{D}_{\textup{U}}$ is definable.  This is a contradiction.  So, $\mathsf{Th}(\Omega)^{\#}$ is not definable and not effectively countable.  Nor is $\mathsf{Th}(\Omega)$ effectively countable.

In the next update (probably on a plane!) I’ll discuss this theorem and get into Hellman’s example.