Tarski, Alfred

views updated

TARSKI, ALFRED

(b. Warsaw, Poland, 14 January 1901; d. Berkeley, California, 27 October 1983)

mathematical logic, set theory, algebra.

Trained as both a mathematician and a philosopher, Tarski discovered interconnections between such diverse areas of mathematics as logic, algebra, set theory, and measure theory. He brought clarity and precision to the semantics of mathematical logic, and in so doing he legitimized semantic concepts, such as truth and definability, that had been stigmatized by the logical paradoxes. Tarski was extroverted, quick-witted, strong-willed, energetic, and sharp-tongued. He preferred his research to be collaborative—sometimes working all night with a colleague—and was very fastidious about priority. An inspiring teacher, at Berkeley he supervised the doctoral dissertations of many of the leading mathematical logicians of the next generation. Tarski’s influence was especially pervasive in model theory—in forming its concepts, problems, and methodology. Although he did much research in algebra, he remained a logician first and an algebraist second. Collectively, his work can be regarded as an immensely fruitful interplay among algebra, set theory, and logic.

Tarski was the son of Ignacy Tajtelbaum, a successful shopkeeper, and his wife, Rose Prussak Tajtelbaum. (Around 1924 he changed his name from Tajtelbaum to Tarski—to protect his as yet unborn children from anti-Semitism.) He was educated in Warsaw, where he submitted his doctoral dissertation, supervised by Stanislaw Lesniewski, in 1923. His other principal teachers in logic and philosophy were Tadeusz Kotarb?ski and Jan Lukasiewicz; in mathematics, Stefan Banach and Waclaw Sierpinski. The University of Warsaw granted Tarski a Ph.D. in mathematics in 1924. In 1918, and again in 1920, he served briefly in the Polish army.

From 1922 to 1925 Tarski was an instructor in logic at the Polish Pedagogical Institute in Warsaw. Then he became a Privatdozent and an adjunct professor of mathematics and logic at the University of Warsaw. Since this was not a regular university position, in 1925 he also accepted a position as professor at Zeromski’s Lycée in Warsaw, teaching there full-time and keeping both positions until 1939. On 23 June 1929 he married Maria Witkowski; they had a son and a daughter. From January to June 1935 he worked in Vienna, holding a fellowship from Karl Menger’s colloquium, where he had lectured by invitation in February 1930. Shortly before the war, Tarski was a candidate for the chair of philosophy at the University of Lvov, but that position went to Leon Chwistek. Tarski’s difficulty in obtaining a regular academic appointment, which some have blamed on anti-Semitism, contrasted sharply with his acknowledged role as a leading Warsaw logician. Politically, he was a socialist.

In 1939 Tarski traveled to the United States for a lecture tour. When World War II broke out, he remained there, and was naturalized as an American citizen six years later. With the influx of refugees from Europe, academic positions were scarce. Nevertheless, from 1939 to 1941 Tarski was a research associate in mathematics at Harvard, and in 1940 also served as visiting professor at the City College of New York. During the year 1941–1942 he was a member of the Institute for Advanced Study at Princeton.

Tarski did not obtain a permanent position until 1942, when the University of California at Berkeley hired him as a lecturer. There he remained for the rest of his career, becoming an associate professor in 1945 and full professor a year later. The breadth of his interests is illustrated by his establishment at Berkeley in 1958 of the Group in Logic and the Methodology of Science, bringing together mathematicians and philosophers to study foundational questions. Although Tar ski was made emeritus professor in 1968, he continued to teach for five years and to supervise doctoral students and do research until his death. In 1981 he received the Berkeley Citation, the highest award that university gives to its faculty.

Tarski established ties with other academic institutions, serving as Sherman memorial lecturer at University College (London) in 1950 and again in 1966, as lecturer at the Institut Henri Poincaré (Paris) in 1955, and as Flint professor of philosophy at U.C.L.A. in 1967. In addition to his European connections, he had close ties to Latin America. He was visiting professor at the National University of Mexico in 1957, and at the Catholic University of Chile in the year 1974–1975.

Despite his early difficulties in securing a regular position, Tarski received numerous honors. In 1935 he was made a Rockefeller fellow, and a Guggenheim fellow in the year 1941–1942 (and again in the year 1955–1956). From 1958 to 1960 he served as research professor at the Miller Institute for Basic Research in Science. In 1966 he was awarded the Jurzykowski Foundation Prize. The journal Algebra Universalis made Tarski honorary editor for his work in universal algebra. He was awarded honorary doctorates by the Catholic University of Chile in 1975 and by the University of Marseilles in 1977.

For many years Tarski was actively involved with mathematical and scientific organizations. From 1935 to 1939 he served as vice president of the Polish Logic Society. In 1940 he was elected to the executive committee of the Association for Symbolic Logic and was the association’s president from 1944 to 1946. In 1948 he became a council member of the American Mathematical Society. Tarski served as president of the International Union for the History and Philosophy of Science (1956–1957) and was chairman of the U.S. National Committee on History and Philosophy of Science (1962–1963). In 1965 he was elected to the National Academy of Sciences. In addition, he was a fellow of the American Academy of Arts and Sciences, a foreign member of the Royal Netherlands Academy of Sciences and Letters, and a corresponding fellow of the British Academy.

Tarski was more eclectic than most logicians educated in the 1920’s. He drew not only from Bertrand Russell and Alfred North Whitehead’s Principia mathematica and from David Hilbert, but also from the Peirce-Sehröder tradition of algebraic logic and from the Polish logic of Le?niewski and ?ukasiewicz. All four traditions repeatedly influenced his work. His dissertation examined the definability of prepositional connectives in the theory of types, but his interests were already quite broad. During his career he wrote several hundred articles, as well as monographs, in French, Polish, German, and English. The extreme richness of his work makes it necessary to treat it thematically rather than chronologically.

In 1921 Tarski began publishing in set theory and continued to do so until his death. His first substantial paper (1924), on finite sets, completed several decades of research on this topic by Georg Cantor, Richard Dedekind, Ernst Zermelo, and others. His work often combined foundational concerns with mathematical results, as in the Banach-Tarski paradox (a sphere can be decomposed into a finite number of pieces and reassembled into a sphere of any larger size). Influenced by Sierpi?ski, Tarski investigated the role of the axiom of choice and showed many propositions (such as the proposition that M2 = M for every infinite cardinal M) to be equivalent to this axiom. By 1929 he became convinced that cardinal arithmetic divided naturally into those propositions equivalent to this axiom and those independent of it. The latter propositions, he believed, formed part of a new theory of the equivalence of sets with respect to a given class of one:one mappings, a theory intensively studied by Tarski and Banach. In 1926 Tarski established that the axiom of choice is implied by the generalized continuum hypothesis (that is, for every infinite set A, there is no cardinal between A and its power set). His concern with propositions equivalent to the axiom of choice was lifelong, as was his interest in cardinal arithmetic dispensing with that axiom.

A second theme in Tarski’s set-theoretic research was large cardinals. In 1930 he introduced, jointly with Sierpi?ski, the notion of a strongly inaccessible cardinal, and in 1939 he put forward the axiom of inaccessible sets, a large cardinal axiom that implies the axiom of choice. In 1943, in a joint paper with Paul Erdös, he introduced the seminal notions of strongly compact cardinal and weakly compact cardinal. They observed that every strongly compact cardinal is measurable and that every measurable cardinal is weakly compact. Proofs were not published until 1961, a year after Tarski also established, by using the work of his student William Hanf on infinitary logic, that a measurable cardinal is very large among inaccessible cardinals, thus settling a thirty-year-old problem.

From 1926 to 1928 Tarski conducted a seminar on metamathematics at Warsaw University. There he investigated, in particular, the structure of complete theories in geometry and group theory. He also exploited the technique of quantifier elimination on the theory of discrete order and the theory of real closed fields, thereby establishing the decidability of these theories. The latter work, which yielded the decidability of first-order Euclidean geometry, was not published until 1948. Never published was Tarski’s 1949 result that the theory of Boolean algebras is decidable. And his 1939 discovery, with his former student Andrzej Mostowski, that the first-order theory of well-orderings is decidable was published in 1978. The richness of Tarski’s discoveries, and the clarity he demanded of their published form, increased the number of his unpublished results and lengthened the time between discovery and publication.

During the 1930’s Tarski did much research on the metamathematical notion of deductive system, axiomatizing the notion of consequence with a generality that included all kinds of logic known at the time. He then specialized the notion of consequence to treat specific logics, such as classical propositional logic. Here he was particularly concerned with determining the number of complete extensions of a given mathematical theory. This research was connected with his desire to find purely mathematical (and especially algebraic) equivalents of metamathematical notions.

A recurring theme in Tarski’s work was the role of the infinitary in logic. In 1926 he formulated the w-rule (an infinitary version of the principle of mathematical induction), which, by 1933, he considered to be problematical. He showed in 1939 that even in the presence of this rule there are undecidable statements. Around 1957 Tarski investigated first-order logic extended by infinitely long formulas. In 1961 the incompactness of many such languages led to very important results in set theory.

Tarski’s famous work on definitions of truth in formalized languages (1933–1935) gave the notion of satisfaction of a sentence in a structure for first-order logic, second-order logic, and so on. This work had a very pronounced influence on philosophers concerned with mathematics, science, and linguistics.

During the mid 1930’s Tarski started to do research in algebra, at first as a tool for studying logic and then, in the 1940’s, increasingly for its own sake as well. In 1935 he investigated complete and atomic Boolean algebras, notions closely related to logic. His increasing concern in the late 1930’s with ideals in Boolean algebras reflected his discovery that such ideals correspond to the metamathematical notion of a mathematical theory. He wrote several joint papers on closure algebras with J. C. C. McKinsey in the 1940’s. While Tarski’s original motivation for inventing closure algebras was to provide an algebraic analogue for the notion of topological space, he showed that these algebras were intimately related to modal logic and to intuitionistic logic. In 1941 he axiomatized the theory of binary relations and posed the problem of representability : Is every model of this theory isomorphic to an algebra of relations’? Although in 1950 Roger Lyndon found the answer to be no, Tarski proved in 1955 that the class of all representable relation algebras is a variety. The following year he determined all complete varieties of rings and of relation algebras. Closely related to this work on varieties was his 1968 paper on equational logic.

Tarski’s research on relation algebras led to his most ambitious algebraic creation, cylindrical algebras. During the period 1948–1952 he and his student Fred Thompson formulated the notion of cylindrical algebra as an algebraic analogue of first-order logic. That is, the class of cylindrical algebras was to bear the same relation to first-order logic with identity that the class of Boolean algebras bears to propositional logic. From the 1950’s until his death, Tarski investigated cylindrical algebras and their representability, first with Leon Henkin and then with his former student Donald Monk as well.

Another major area of Tarski’s logical research was the undecidability of theories. In 1939 he and Mostowski reduced Godel’s incompleteness theorems to a form that depended only on a finite number of first-order arithmetic axioms, and thereby were able to extend greatly the number of theories known to be undecidable. Their results were published in 1953 in the monograph Undecidable Theories, in which Tarski established the undecidability of the first-order theory of groups, of lattices, of abstract projective geometries, and (with Mostowski) of rings.

In his research after World War II, Tarski no longer used the theory of types as his basic logical system; instead, he used first-order logic. At most, he considered certain extensions of first-order logic, such as weak second-order logic and infinitary logics.

Tarski’s immense influence cannot be properly judged on the basis of his publications alone. He influenced the many mathematicians with whom he did joint work, and he molded the perspectives of many doctoral students who became leading mathematical logicians. While still at Warsaw, he unofficially supervised Mostowski’s dissertation on set theory (1939) as well as M. Presburger’s master’s thesis on decidability (1930). But it was during his years at Berkeley that Tarski exerted his greatest influence. Those who wrote their dissertations under him included Bjarni Jónsson (1946), Julia Robinson (1948), Robert Vaught (1954), Chen-chung Chang (1955), Solomon Feferman (1957), Robert Montague (1957), Jerome Keisler (1961), Haim Gaifman (1962), William Hanf (1963), and George McNulty (1972). Tarski also molded Dana Scott’s approach to logic, although Scott received his Ph.D. at Princeton. Nor was Tarski’s influence felt only in mathematics; it was also seen in J. H. Woodger’s work on the axiomatic foundations of biology and in Patrick Suppes’ research on the axiomatic foundations of physics.

BIBLIOGRAPHY

I. Original Works. Tarski’s Collected Papers were published in 4 vols. (1986). His Nachlass is in the Bancroft Library, University of California at Berkeley. A complete bibliography is in Steven Givant, “Bibliography of Alfred Tarski,” in Journal of Symbolic Logic, 51 (1986), 913–941. A list of his Ph.D. students is in the Tarski symposium volume. Proceedings of Symposia in Pure Mathematics, 25 (1974), honoring his seventieth birthday and in Hodges (see below).

II. Secondary Literature. A series of articles on Tarski’s life and work appeared in Journal of Symbolic Logic: W. J. Blok and Don Pigozzi, “Alfred Tarski’s Work on General Metamathematics,” 53 (1988), 36–50; John Doner and Wilfrid Hodges, “Alfred Tarski and Decidable Theories,” ibid., 20–35; John Etchemendy, “Tarski on Truth and Logical Consequence,” ibid., 51–79; Wilfrid Hodges, “Alfred Tarski,” 51 (1986), 866–868; Bjarni Jónsson, “The Contributions of Alfred Tarski to General Algebra,” ibid., 883–889; Azriel Levy, “Alfred Tarski’s Work in Set Theory,” 53 (1988), 2–6; George F. McNulty, “Alfred Tarski and Undecidable Theories,” 51 (1986), 890–898; J. Donald Monk, “The Contributions of Alfred Tarski to Algebraic Logic,” ibid., 899–906: Patrick Suppes, “Philosophical Implications of Tarski’s Work,” 53 (1988), 80–91; L. W. Szczerba, “Tarski and Geometry,” 51 (1986), 907–912; Lou van den Dries, “Alfred Tarski’s Elimination Theory for Real Closed Fields,” 53 (1988), 7–19; and Robert L. Vaught, “Alfred Tarski’s Work in Model Theory,” 51 (1986), 869–882. On Tarski’s contributions to model theory, see C. C. Chang, “Model Theory 1945–1971,” in Proceedings of Symposia in Pure Mathematics, 25 (1974), 173–186; and R. L. Vaught, “Model Theory Before 1945,” ibid., 153–172.

Gregory H. Moore

More From encyclopedia.com