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.

Posted in Tarski's Theorem, Undefinability of Truth | Leave a Comment »

Follow

Get every new post delivered to your Inbox.