Wednesday, April 01, 2009

"Truth!" Said Pilate. "What Does That Mean?"

Alfred Tarski's 1944 essay, "The Semantic Conception of Truth and the Foundations of Semantics" has been put up on a Web site. Tarksi's problem is to formulate a definition of truth for an object language. According to Tarski, a definition of truth is materially adequate only if condition T holds for all true sentences "p" in the object language:
(T): X is true if and only if p,
where X is the name of the sentence "p", and p is the translation of the sentence "p" into the metalanguage in which condition T is expressed.

Maybe I should explain a litte about a metalanguage and the names of sentences. The object language is merely the language for which truth of sentences is defined. It is a formal language, and some mechanism (e.g., a grammar in Backus-Naur form) is available for determining what strings are sentences in the language and what are not. Predicate calculus with quantification ("for all" and "there exists") of variables taken over natural numbers provides an example. The grammar specifies the syntax of the language, but not the semantics.

The metalanguage is merely a (formal) language in which to talk about expressions and sentences in the object language. My title provides an easy example of named sentences. "John 18:38" is the name of those sentences. Notice that "John 18:38" does not appear in the New Testament, although the verse with the name "John 18:38" does. Likewise, the names of sentences presumably do not appear in the object language.

In this informal exposition, Tarski waves his hands at a couple of points, most notably in (not) explaining what it means for the metalanguage to be "essentially richer" than the object language. The metalanguage contains translations of every sentence "p" in the metalanguage, as well as additional sentences. But this is not enough for the metalanguage to be richer. Tarski points to Bertrand Russell's theory of types and says something about the metalanguage being able to include sentences about higher types.

I'll have to study more if I really want to understand "essential richness". It occurs to me that any sentence in the metalanguage has a Gödel number. So sentences in the object language can include variables taking on a number expressing a sentence in the metalanguage. But Gödel numbering operates only on the level of syntax. I guess the idea of essential richness is to prevent the formulation of a relation like T(GN(X), GN(p)) in the object language, where this relation somehow encodes condition T and GN(X) and GN(p) are the Gödel numbers of X and p, respectively. If one could formulate a relation like this, the possibility arises of creating a sentence that says that it itself is false, under the obvious interpretation. (Footnote 11 in Section 8 of Tarski's paper provides a neat formulation of the paradox of the liar.)

I find it amazing that Tarski can relegate a proof of Gödel's incompleteness theorem to a couple of footnotes. Part of why he can do this is that he presumes all the technical machinery Gödel used to demonstrate that one can assert the provability of a sentence in the object language within the object language (given an object language in which arithmetic can be expressed). Since Tarski has shown that one cannot assert the truth of a sentence in the object language, the non-equivalence of provability and truth falls out. And all provable sentences in the object language are true. So the existence of true but unprovable sentences in the object language follows, even though Tarski, unlike Gödel, doesn't construct one.

I have some questions:
  1. Would at least some authors of the committe that developed the Web Ontology Language be extremely well-versed in Tarski's work, including semantics and model theory? Would the same be true of at least some developers of the semantic web?
  2. Is there a good book on model theory available and downloadable on the Web?

3 comments:

walt said...

Weiss and D'Mello (http://www.math.toronto.edu/weiss/model_theory.html) is okay, but there's nothing great.

Robert Vienneau said...

Walt, thanks. That looks interesting. I ended up ordering Hodges' A Shorter Model Theory anyways. The more I read, the less convinced I become that model theory has much to do with work on the semantic web and ontology.

Anonymous said...

truth is a function of the amount of informqatio we have.
www.economicstruth.com