Tarski’s Theorem

Archive for the ‘Tarski’s Theorem’ Category

Hellman’s First Definability Example

September 15, 2010

What Tarski’s Theorem shows is that interpreted formal languages that are interesting (i.e., with enough expressive machinery to represent arithmetic or fragments thereof) cannot contain a predicate whose extension is the set of code numbers (e.g., $\mathsf{Th}(\Omega)^\#$ ) of sentences true in the interpretation. The extension of any proposed truth predicate in such a system escapes the definitional machinery of the system. Of course, the truth predicate for first-order arithmetic can be defined with appeal to a stronger system, like second-order arithmetic, in the case of the Peano Axioms, etc.

Hellman’s first example is the following. It is a corollary of Tarski’s theorem that a theory in the language, $\textup{L}$ , of arithmetic (e.g., an axiom system $\textup{T}$ containing Robinson Arithmetic ( $\mathsf{Q}$ )) with symbols for zero, successor, addition, and multiplication, when extended with a one place predicate, $\mathsf{Tr}(x)$ (read “true in arithmetic” such that for each closed sentence $\textup{S}$ in $\textup{L}$ a new axiom of the form $\ulcorner \mathsf{Tr}(n) \leftrightarrow \textup{S}\urcorner$ (where $n$ is the numeral for a code number for the sentence $\textup{S}$ ), the resulting theory $\textup{T}^{*}$ contains no explicit definition of $\mathsf{Tr}(x)$ in $\textup{L}$ .

Connecting this to our ongoing discussion of determination of truth and reference in special collections of models, suppose that $\alpha$ is the class of standard $\omega$ -models of $\textup{T}^{*}$ . Then we have:

In $\alpha$ -structures $\textup{L}$ -truth determines $\mathsf{Tr}$ -truth.
In $\alpha$ -structures $\textup{L}$ -reference determines $\mathsf{Tr}$ -reference

Which means that once you have the arithmetical truths in the class $\alpha$ , then so are the ‘true-in-arithmetic’ truths and the same goes for the reference of the vocabularies. To avoid collapsing to reductionism via Beth’s theorem, note that there is no first-order theory (like those under discussion) in a language with finitely many non-logical symbols has as it’s models just the models in in $\alpha$ .

If you extend $\alpha$ to $\alpha^{*}$ containing all models of $\textup{T}^{*}$ , then you do get reductionism, since determination of reference in $\alpha^{*}$ amounts to implicit definability in $\textup{T}^{*}$ -thus showing that there exist non-standard models of arithmetic.

This is a good example because it is clear, based on popular, well established results and firmly shows how determination of truth and reference in one core theory carry over to it’s extension, without thereby reducing the extension to the core.

In the next update I’ll discuss Hellman’s second definability example.

Posted in Robinson Arithmetic, Supervenience and Determination, Tarski's Theorem, Undefinability of Truth | Leave a Comment »

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 »

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.

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

M	T	W	T	F	S	S
« Feb
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Logicians do it with Models

Archive for the ‘Tarski’s Theorem’ Category

Hellman’s First Definability Example

Tarski’s Theorem

Statement of Tarski’s Theorem

Categories

Archives

Twitter

Mathematics and Philosophy Links

Follow “Logicians do it with Models”