MODERN LOGIC: SINCE GÖDEL: MODEL THEORY

Tarski

The Polish-American logician Alfred Tarski (1901–1983) was born Alfred Teitelbaum in Warsaw; he changed his surname to Tarski in 1924. That same year he obtained his doctorate at the University of Warsaw for a thesis in logic under the supervision of Stanisław Leśniewski; he had also studied under Tadeusz Kotarbiński, Kazimierz Kuratowski, Jan Łukasiewicz, Stefan Mazurkiewicz and Wacław Sierpiński. At the University of Warsaw he was Docent and then Adjunct Professor from 1924 to 1939; simultaneously he taught in a high school from 1925 to 1939. From 1942 to his retirement in 1969 he held posts at the University of California at Berkeley.

Through his own work and that of his students, Tarski stands along with Aristotle and Frege as one of the creators of the discipline of logic. Andrzej Mostowski, Julia Robinson, Robert Vaught, Chen-Chung Chang, Solomon Feferman, Richard Montague, Jerome Keisler, and Haim Gaifman, among others, wrote their theses under his supervision.

In print Tarski was reluctant to place himself in any philosophical tradition. He described himself as "perhaps a philosopher of a sort." In 1930 he said that he agreed in principle with Leśniewski's "intuitionistic formalism," but in 1954 he reported that this was no longer his attitude. His philosophical reticence was certainly deliberate and reflected a view that careful formalization can resolve or at least avoid problems thrown up by philosophical speculation.

Tarski had many research interests within logic. He maintained most of them throughout his career and integrated them to an extraordinary degree. The setting of most of his work in Warsaw from 1926 to 1938 was the notion of a deductive theory. Such a theory develops a certain subject matter, starting from primitive terms together with axioms and proceeding by definition and logical deduction, all within a formally defined language. Tarski saw these theories as a paradigm for research in mathematical subjects. Like David Hilbert with his metamathematics, Tarski proposed to take the theories themselves as subject matter. But unlike Hilbert, Tarski did so by developing metatheories (that is, deductive theories about deductive theories) without any restriction to finitary means. For example the notion of "true sentence of the deductive theory T′ " must be defined in a metatheory T′. Tarski chose as primitive notions of T′ those of T together with notions from set theory and syntax, and he showed how to write a definition in the metatheory which exactly characterizes the class of true sentences of T. He proposed similar metatheoretic definitions of "satisfies," "definable," and (with less confidence) "logical consequence." His later characterization of "logical notion" was published posthumously. His influential English exposition of his definition of truth in 1944 is still the best nontechnical introduction.

At the same time Tarski developed methodologies for creating deductive theories of particular topics, and for settling the decision problem for particular deductive theories. His method of elimination of quantifiers, based on work of Thoralf Skolem and others, guided him to an axiomatisation of the first-order theory of the field of real numbers. As a byproduct he found an algorithm for deciding the truth of first-order statements about the field of real numbers (or, as he later realized, any real-closed field). Responding to the work of Alonzo Church and Alan Turing on undecidability, Tarski developed methods for proving the undecidability of a deductive theory T by interpreting a known undecidable theory within T.

In the 1940s Tarski turned his attention to the application of metatheorems of logic in mathematics. In parallel with Anatolii Mal'tsev and Abraham Robinson, he showed that the compactness theorem of first-order logic could be used to prove purely mathematical facts. During the early 1950s he recast his notion of deductive theory to fit the new program. A deductive theory was no longer about a particular subject matter. Rather it was in a formal language with primitive symbols that could be interpreted as one pleases. An interpretation that makes all the axioms of the theory true is called a model of the theory. We can study those classes of structures which consist of all the models of a particular theory; in 1954 Tarski proposed the name theory of models for this line of research. Tarski adapted his definition of truth to define the relation "Sentence ϕ is true in structure A." He published this new model-theoretic truth definition in a joint paper with Vaught, which also included fundamental theorems about elementary embeddings between structures.

Particular theories that Tarski had studied in connection with quantifier elimination or undecidability became central to model-theoretic research. Some of them, such as the theories of real-closed fields and algebraically closed fields, remained central fifty years on. Tarski also stated several problems that strongly influenced the direction of model-theoretic research. For example he asked for a quantifier elimination for the field of reals with an exponentiation function, and for algebraic necessary and sufficient conditions for two structures to be elementarily equivalent.

Tarski's further contributions during his American period were perhaps more scattered but no less important. He was closely involved in the theory of large cardinals. He also worked with students and colleagues on relation algebras and cylindrical algebras. During the 1960s he studied finite axiomatisations of equational classes, picking up a theme from his work with Łukasiewicz during the 1920s on propositional logics. He never lost his interest in formal theories of geometry. Students of his recall that he looked back with particular pride to the work that he did during the 1940s with Bjarni Jónsson on decompositions of finite algebras. With the help of colleagues in Europe and the United States, he was instrumental in the setting up of the series of International Congresses in Logic, Methodology and Philosophy of Science, which first met at Stanford in 1960.

See also Aristotle; Frege, Gottlob; Hilbert, David; Kotarbiński, Tadeusz; Leśniewski, Stanisław; Łukasiewicz, Jan; Model Theory; Montague, Richard; Set Theory.

Bibliography

Feferman, Anita Burdman, and Solomon Feferman. Alfred Tarski: Life and Logic. New York: Cambridge University Press, 2004.

Givant, Steven R. "A Portrait of Alfred Tarski." The Mathematical Intelligencer 13 (1991): 16–32.

Suppes, Patrick. "Philosophical Implications of Tarski's Work." Journal of Symbolic Logic 53 (1988): 80–91.

Tarski, Alfred. O logice matematycznej i metodzie dedukcyjnej, Biblioteczka Mat. 3–5. Lwów and Warsaw: Ksia̧znica-Atlas, 1936. Translated and revised as Introduction to Logic and to the Methodology of the Deductive Sciences. New York: Oxford University Press, 1994.

Tarski, Alfred. "The Semantic Conception of Truth." Philosophy and Phenomenological Research 4 (1944): 13–47.

Tarski, Alfred. Logic, Semantics, Metamathematics. Translated by J. H. Woodger. 2nd ed., edited by John Corcoran. Indianapolis: Hackett, 1983.

Tarski, Alfred. Pisma Logiczno-Filozoficzne. Vol. 1, Prawda ; Vol. 2, Metalogika, edited by Jan Zygmunt. Warsaw: Wydawnictwo Naukowe, 1995, 2001.

Tarski, Alfred. "What Are Logical Notions?" History and Philosophy of Logic 7 (1986): 143–154.

Tarski, Alfred. Collected Papers. 4 vols., edited by S. R. Givant and R. N. McKenzie. Basel: Birkhäuser, 1986.

Tarski, Alfred, and Robert L. Vaught. "Arithmetical Extensions of Relational Systems." Compositio Mathematica 13 (1957): 81–102.

Woleński, Jan. Logic and Philosophy in the Lvov-Warsaw School. Dordrecht: Kluwer, 1989.

Wilfrid Hodges (2005)