Alfred Tarski (January 14, 1902, Warsaw, Russian-ruled Poland – October 26, 1983, Berkeley,
California) was a logician and mathematician who spent four decades as a professor of mathematics at the University of California, Berkeley. A member of the interwar Warsaw School of Mathematics, and active in the USA after 1939, he wrote on
topology, geometry, measure theory, mathematical logic, set theory, metamathematics, and above all, model theory, abstract algebra, and algebraic logic. His biographers Anita Feferman and Solomon
Feferman state (2004) that, "Along with his contemporary, Kurt Gödel, he changed the
face of logic in the twentieth century, especially through his work on the concept of
truth and the theory of models."
Life
Alfred Tarski was born Alfred Teitelbaum (Polish spelling: "Tajtelbaum"), to
parents who were Polish Jews in comfortable circumstances. Some of his
brilliance is attributed to his mother, Rosa Prussak. Tarski first revealed his mathematical abilities while in secondary school,
at Warsaw's Szkoła Mazowiecka. Nevertheless, when he entered the University of
Warsaw in 1918, he intended to study biology.
In 1919, Poland became a nation again for the first time since 1795, and Warsaw University became a Polish university for the first
time in generations. Under the leadership of Jan Łukasiewicz, Stanisław Leśniewski and Wacław Sierpiński, the
university immediately became a world leader in logic, foundational mathematics, the philosophy of mathematics, and analytic and
linguistic philosophy. At Warsaw University, Tarski had a fateful encounter with
Leśniewski, who discovered Tarski's genius and persuaded him to abandon biology for mathematics. Henceforth Tarski attended
courses taught by Łukasiewicz, Sierpiński, Stefan Mazurkiewicz and Tadeusz Kotarbiński, and became the only person ever to complete a doctorate under Leśniewski's
supervision. Tarski and Leśniewski soon grew cool to each other. In private correspondence, Leśniewski sometimes employed
anti-semitic language when talking about Tarski. In later life, Tarski reserved his warmest praise for Kotarbiński.
In 1923, Alfred Teitelbaum and his brother Wacław changed their surname to "Tarski," a name they invented because it sounded
Polish, was simple to spell and pronounce, and seemed unused. (Years later, Alfred met another Alfred Tarski in northern
California.) The Tarski brothers also converted to Roman Catholicism, Poland's dominant religion. Alfred did so even though he was an avowed
atheist, because he was about to complete his doctorate and correctly anticipated that it would
be difficult for a Jew to obtain a serious position in the new Polish university system. Tarski was
a Polish nationalist and wished to be fully accepted as a Pole, which was how he saw himself. He married a Pole of Catholic
ancestry, and spoke Polish at home throughout his later American life.
In 1929 Tarski married a fellow teacher, Maria Witkowska. She had worked as a courier for the army during Poland's fight for
independence. They had two children. His son Jan became a physicist. His daughter married the mathematician Andrzej Ehrenfeucht.
After becoming the youngest person ever to complete a doctorate at Warsaw University, Tarski taught logic at the Polish
Pedagogical Institute, mathematics and logic at the University, and served as Łukasiewicz's assistant. Because these positions
were poorly paid, Tarski also taught mathematics at a Warsaw secondary school; before World War II, it was not uncommon for
European intellectuals of research caliber to teach high school. Hence between 1923 and his departure for the United States in
1939, Tarski not only wrote several textbooks and many papers, a number of them ground-breaking, but also did so while supporting
himself primarily by teaching high-school mathematics.
Tarski applied for a chair of philosophy at Lwów University, but on Bertrand Russell's recommendation it was awarded to Leon
Chwistek. In 1937 Tarski applied for a chair at Poznań
University; but rather than award a chair to one of Jewish ancestry, the chair was abolished (Feferman and Feferman, 2004,
pp. 102-3).
In 1930, Tarski visited the University of Vienna, lectured to Menger's colloquium, and met Kurt
Gödel. Thanks to a fellowship, Tarski was able to return to Vienna during the first half of 1935 to work with Menger's
research group. From Vienna he traveled to Paris to present his ideas on truth at the first meeting of the Unity of Science movement, an outgrowth of the Vienna
Circle.
Tarski's ties to this movement saved his life, because they resulted in his being invited to address the Unity of Science
Congress held in September 1939 at Harvard University. Thus he left Poland in August
1939, on the last ship to sail from Poland for the United States before the
German invasion of Poland and the outbreak of World War II. Tarski left reluctantly, because Leśniewski had died a few months before, creating a vacancy
which Tarski hoped to fill. He was so oblivious to the Nazi threat that he left his wife and children in Warsaw; he did not see
them again until 1946. During the war, nearly all his extended family died at the hands of the Nazis.
Once in the United States, Tarski held a number of temporary teaching and research positions: Harvard University (1939), City College of New York
(1940), and thanks to a Guggenheim Fellowship, the Institute for Advanced
Study at Princeton (1942), where he again met Gödel. Tarski became an American citizen in 1945.
In 1942, Tarski joined the Mathematics Department at the University of
California, Berkeley, where he spent the rest of his career. Although emeritus from 1968, he taught until 1973 and
supervised Ph.D. candidates until his death. At Berkeley, Tarski acquired a reputation as an awesome and demanding teacher:
- "His seminars at Berkeley fast became a power-house of logic. His students, many of them now distinguished mathematicians,
recall the awesome energy with which he would coax and cajole their best work out of them, always demanding the highest standards
of clarity and precision." Times
obituary.
- "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." (Gregory Moore, "Alfred
Tarski" in Dictionary of Scientific Biography.)
- "A charismatic leader and teacher, known for his brilliantly precise yet suspenseful expository style, Tarski had
intimidatingly high standards for students, but at the same time he could be very encouraging, and particularly so to women — in
contrast to the general trend. Some students were frightened away, but a circle of disciples remained, many of whom became
world-renowned leaders in the field." (Anita Feferman 1999)
Tarski supervised 24 Ph.D. dissertations, 5 by women, and strongly influenced the dissertations of Alfred Lindenbaum, Dana Scott, and Steven Givant. His students include
Andrzej Mostowski, Julia Robinson,
Robert Vaught, Solomon Feferman,
Richard Montague, J. Donald Monk, Donald Pigozzi, Roger
Maddux, and the authors of the classic text on model theory, Chang and Jerome Keisler (1973).
Tarski lectured at University College, London (1950, 1966), the
Institut Henri Poincaré in Paris (1955), the Miller
Institute for Basic Research in Science in Berkeley (1958-1960), the University of California at Los Angeles (1967), and the Pontifical Catholic University of Chile (1974-75). He was elected to the
National Academy of Sciences and the British Academy, and presided over the Association for
Symbolic Logic, 1944-46, and the International Union for the History and Philosophy of
Science, 1956-57.
Mathematician
Tarski's mathematical interests were exceptionally broad for a mathematical
logician. His collected papers run to about 2500 pages, most of them on mathematics, not logic. For a concise survey of
Tarski's mathematical and logical accomplishments by his former student Solomon
Feferman, see "Interludes I-VI" in Feferman and Feferman (2004).
Tarski's first paper, published when he was 19 years old, was on set theory, a subject to
which he returned throughout his life. In 1924, he and Stefan Banach proved that a
ball can be cut into a finite number of pieces, and then reassembled into a sphere of
larger size, or alternatively it can be reassembled into two spheres whose sizes each equal that of the original one. This result
is now called the Banach-Tarski paradox.
In A decision method for elementary algebra and geometry, Tarski showed, by the method of quantifier elimination, that the first-order
theory of the real numbers under addition and multiplication is decidable. This is a very curious result, because Alonzo
Church proved in 1936 that Peano arithmetic (effectively the theory Tarski proved
decidable, except that the natural numbers replace the reals) is not decidable.
Peano arithmetic is also incomplete by Gödel's incompleteness theorem.
In his 1953 Undecidable theories, Tarski et al. showed that many mathematical systems, including lattice theory, abstract projective geometry, and
closure algebras, are all undecidable. The theory of Abelian groups is decidable, but that of non-Abelian groups is
not.
In the 1920s and 30s, Tarski often taught high school geometry. In 1929, he showed that much
of Euclidian solid geometry could be recast as a first order theory whose individuals are spheres, a primitive notion, a single
primitive binary relation "is contained in," and two axioms that, among other things, imply that containment partially orders the spheres. Relaxing the requirement that all individuals be spheres yields a
formalization of mereology far easier to exposit that Lesniewski's variant. Starting in
1926, Tarski devised an original axiomatization for plane
Euclidian geometry, one considerably more concise than Hilbert's. Tarski's axiomatization is a first-order
theory devoid of set theory, whose individuals are points, and having only two primitive relations. In 1930, he
proved this theory decidable because it can be mapped into another theory he had already
proved decidable, namely his first-order theory of the real numbers. Near the end of his life, Tarski wrote a very long letter,
published as Tarski and Givant (1999), summarizing his work on geometry.
Cardinal Algebras studied algebras whose models include the arithmetic of cardinal
numbers. Ordinal Algebras sets out an algebra for the additive theory of order
types. Cardinal, but not ordinal, addition commutes.
In 1941, Tarski published an important paper on binary relations, which began the
work on relation algebra and its metamathematics that occupied Tarski and his students for much of the balance of his life. While that
exploration (and the closely related work of Roger Lyndon) uncovered some important limitations
of relation algebra, Tarski also showed (Tarski and Givant 1987) that relation algebra can express most axiomatic set theory and Peano arithmetic. For an
introduction to relation algebra, see Maddux (2006). In the late 1940s, Tarski and his
students devised cylindric algebras, which are to first-order logic what the two-element Boolean
algebra is to classical sentential logic. This work culminated in the two
monographs by Tarski, Henkin, and Monk (1971, 1985).
Logician
Along with Aristotle, Gottlob Frege, and
Kurt Gödel, Tarski is generally considered one of the four greatest logicians of all time
(Vaught 1986). Of these four, he was the best mathematician and the most prolific author. Neither Frege nor Gödel ever supervised
a single Ph. D. or coauthored a paper; Tarski, on the other hand, supervised 24 Ph. Ds and coauthored over 100 books and papers.
Frege was sternly aloof in person and often bitingly sarcastic in print, and Gödel was a notorious recluse. Meanwhile, Tarski
loved to interact with people intellectually and socially.
Tarski produced axioms for logical consequence, and worked on deductive systems, the algebra of logic, and the theory
of definability. His semantic methods, which culminated in the model theory he and a number
of his Berkeley students developed in the 1950s and 60s, radically transformed Hilbert's proof-theoretic metamathematics.
- "In [Tarski's] view, metamathematics became similar to any mathematical discipline. Not only its concepts and results can be
mathematized, but they actually can be integrated into mathematics. ... Tarski destroyed the borderline between metamathematics
and mathematics. He objected to restricting the role of metamathematics to the foundations of mathematics." (Sinaceur 2001)
All formal scientific languages can be studied by model theory and related semantic
methods.
Tarski's 1936 article "On the concept of logical consequence" argued that the conclusion of an argument will follow logically
from its premises if and only if every model of the premises is a model of the conclusion. In 1937, he published a paper
presenting clearly his views on the nature and purpose of the deductive method, and the role of logic in scientific studies. His
high school and undergraduate teaching on logic and axiomatics culminated in a classic short text, published first in Polish,
then in German translation, and finally in a 1941 English translation as Introduction to Logic and to the Methodology of
Deductive Sciences.
Tarski's 1969 "Truth and proof" considered both Gödel's incompleteness
theorems and Tarski's indefinability theorem, and mulled over
their consequences for the axiomatic method in mathematics.
Truth in formalized languages
In 1933, Tarski published a very long (more than 100pp) paper in Polish, titled "Pojęcie prawdy w językach nauk dedukcyjnych,"
setting out a mathematical definition of truth for formal languages. The 1936 German translation was titled "Der Wahrheitsbegriff
in den Sprachen der deduktiven Disziplinen," sometimes shortened to "Wahrheitsbegriff." An English translation had to await the
1956 first edition of the volume Logic, Semantics, Metamathematics. This enormously cited paper is a landmark event in
20th century analytic philosophy, an important contribution to symbolic logic, semantics, and the philosophy of language. For a brief discussion of its content, see Truth for a brief description of the "Convention T" (see also T-schema) standard
in Tarski's "inductive definition of truth".
Some recent philosophical debate examines the extent to which Tarski's theory of truth for formalized languages can be seen as
a correspondence theory of truth. The debate centres on how to read
Tarski's condition of material adequacy for a truth definition. That condition requires that the truth theory have the following
as theorems for all sentences P of the language for which truth is being defined:
- 'P' is True if and only if p.
(where p is the proposition expressed by "P")
The debate amounts to whether to read sentences of this form, such as
- "Snow is white" is true if and only if snow is white
as expressing merely a deflationary theory of truth or as embodying
truth as a more substantial property (see Kirkham 1992).
Logical consequence
In 1936, Tarski published Polish and German versions of a lecture he had given the preceding year at the International
Congress of Scientific Philosophy in Paris. A new English translation of this paper, Tarski (2002), highlights the many
differences between the German and Polish versions of the paper, and corrects a number of mistranslations in Tarski (1983).
This publication set out the modern model-theoretic definition of (semantic) logical
consequence, or at least the basis for it. Whether Tarski's notion was entirely the modern one turns on whether he intended to
admit models with varying domains (and in particular, models with domains of different cardinalities). This question is a matter of some debate in the current philosophical literature.
John Etchemendy (1999) stimulated much of the recent discussion about Tarski's treatment
of varying domains.
Tarski ends by pointing out that his definition of logical consequence depends upon a division of terms into the logical and
the extra-logical and he expresses some skepticism that any such objective division will be forthcoming. "What are Logical
Notions?" can thus be viewed as continuing "On the Concept of Logical Consequence."
What are logical notions?
Another theory of Tarski's attracting attention in the recent philosophical literature is that outlined in his "What are
Logical Notions?" (Tarski 1986). This is the published version of a talk that he gave in 1966; it was edited without his direct
involvement.
In the talk, Tarski proposed a demarcation of the logical operations (which he calls "notions") from the non-logical. The
suggested criteria were derived from the Erlangen programme of the German 19th century
Mathematician, Felix Klein. (Mautner 1946, and possibly an article by the Italian
mathematician Silva, anticipated Tarski in applying the Erlangen Program to logic.)
That program classified the various types of geometry (Euclidean geometry,
affine geometry, topology, etc.) by the type of
one-one transformation of space onto itself that left the objects of that geometrical theory invariant. (A one-to-one
transformation is a functional map of the space onto itself so that every point of the space is associated with or mapped to one
other point of the space. So, "rotate 30 degrees" and "magnify by a factor of 2" are intuitive descriptions of simple uniform
one-one transformations.) Continuous transformations give rise to the objects of topology, similarity transformations to those of
Euclidean geometry, and so on.
As the range of permissible transformations becomes broader, the range of objects one is able to distinguish as preserved by
the application of the transformations becomes narrower. Similarity transformations are fairly narrow (they preserve the relative
distance between points) and thus allow us to distinguish relatively many things (e.g., equilateral triangles from
non-equilateral triangles). Continuous transformations (which can intuitively be thought of as transformations which allow
non-uniform stretching, compression, bending, and twisting, but no ripping or glueing) allow us to distinguish a polygon from an annulus (ring with a hole in the centre), but do not allow us
to distinguish two polygons from each other.
Tarski's proposal was to demarcate the logical notions by considering all possible one-to-one transformations
(automorphisms) of a domain onto itself. By domain is meant the universe of discourse of a model for the semantic theory of a logic. If one identifies the truth
value True with the domain set and the truth-value False with the empty set, then the following operations are counted as logical
under the proposal:
1. Truth-functions: All truth-functions are admitted by the proposal. This
includes, but is not limited to, all n-ary truth-functions for finite n. (It also admits of truth-functions with
any infinite number of places.)
2. Individuals: No individuals, provided the domain has at least two members.
3. Predicates:
- One-place total and null (the predicate that has all members of the domain in its extension and the predicate that has no
members of the domain in its extension).
- Two-place total and null, as well as the identity and diversity predicates (the predicate with the set of all ordered pairs
of domain members as its extension, the predicate with the empty set as extension, the predicate with the set of all order-pairs
<a,a> where a is a member of the domain and the predicate with the set of all order pairs
<a,b> in its extension, where a and b are distinct members of the domain.
- n-ary predicates in general: all predicates definable from the identity predicate together with conjunction, disjunction and negation (up to any ordinality, finite or infinite).
4. Quantifiers: Tarski explicitly discusses only monadic quantifiers and points
out that all such numerical quantifiers are admitted under his proposal. These include the standard universal and existential
quantifiers as well as numerical quantifiers such as "Exactly four", "Finitely many", "Uncountably many", and "Between four and 9
million", for example. While Tarski does not enter into the issue, it is also clear that polyadic quantifiers are admitted under
the proposal. These are quantifiers like, given two predicates Fx and Gy, "More(x, y)", which says "More
things have F than have G."
5. Set-Theoretic relations: Relations such as inclusion, intersection and union applied to subsets of the domain are logical in the present sense.
6. Set membership: Tarski ended his lecture with a discussion of whether the set membership relation counted as logical
in his sense. (Given the reduction of (most of) mathematics to set theory, this was, in effect, the question of whether most or
all of mathematics is a part of logic.) He pointed out that set membership is logical if set theory is developed along the lines
of type theory, but is extralogical if set theory is set out axiomatically, as in the
canonical Zermelo-Fraenkel set theory.
7. Logical notions of higher order: While Tarski confined his discussion to operations of first-order logic, there is
nothing about his proposal that necessarily restricts it to first-order logic. (Tarski likely restricted his attention to
first-order notions as the talk was given to a non-technical audience.) So, higher-order quantifiers and predicates are admitted
as well.
In some ways the present proposal is the obverse of that of Lindenbaum and Tarski (1936), who proved that all the logical
operations of Russell and Whitehead's
Principia Mathematica are invariant under one-to-one transformations of the
domain onto itself. The present proposal is also employed in Tarski and Givant (1987).
Solomon Feferman and Vann McGee further discussed
Tarski's proposal in work published after his death. Feferman (1999) raises problems for the proposal and suggests a cure:
replacing Tarski's preservation by automorphisms with preservation by arbitrary homomorphisms. In essence, this suggestion circumvents the difficulty Tarski's proposal has in dealing with
sameness of logical operation across distinct domains of a given cardinality and across domains of distinct cardinalities.
Feferman's proposal results in a radical restriction of logical terms as compared to Tarski's original proposal. In particular,
it ends up counting as logical only those operators of standard first-order logic without identity.
McGee (1996) provides a precise account of what operations are logical in the sense of Tarski's proposal in terms of
expressibility in a language that extends first-order logic by allowing arbitrarily long conjunctions and disjunctions, and
quantification over arbitrarily many variables. "Arbitrarily" includes a countable infinity.
Bibliography
- 1986. The Collected Papers of Alfred Tarski, 4 vols. Givant, S. R., and McKenzie, R. N., eds. Birkauser.
- Givant, Steven, 1986. "Bibliography of Alfred Tarski", Journal of Symbolic Logic 51: 913-41.
Many of Tarski's more important papers written during his Polish years in languages other than English, including "The Concept
of Truth in Formalized Languages" and "On the Concept of Logical Consequence" discussed above, are translated in the important
collection:
- 1983 (1956). Logic, Semantics, Metamathematics, Corcoran, J., ed. Hackett. 1st edition edited and translated by J. H.
Woodger, Oxford Uni. Press.
Other publications:
- 1936 (with Adolf Lindenbaum). "On the Limitations of Deductive Theories" in Tarski (1983): 384-92.
- 1994 (1941). Introduction to Logic and to the Methodology of Deductive Sciences. Dover.
- 1941. "On the calculus of relations," Journal of Symbolic Logic 6: 73-89.
- 1944. "The Semantical Concept of
Truth and the Foundations of Semantics," Philosophy and Phenomenological Research 4: 341-75.
- 1948. A decision method for elementary algebra and geometry. Santa Monica CA: RAND Corp.
- 1949. Cardinal Algebras. Oxford Univ. Press.
- 1953 (with Mostowski and Rafael Robinson). Undecidable theories. North Holland.
- 1956. Ordinal algebras. North-Holland.
- 1965. "A simplified formalization of predicate logic with identity," Archiv für Mathematische Logik und
Grundlagenforschung 7: 61-79
- 1969. "Truth and Proof," Scientific American 220: 63-77.
- 1971 (with Leon Henkin and Donald Monk). Cylindric Algebras: Part I.
North-Holland.
- 1985 (with Leon Henkin and Donald Monk). Cylindric Algebras: Part II.
North-Holland.
- 1986. "What are Logical Notions?", Corcoran, J., ed., History and Philosophy of Logic 7: 143-54.
- 1987 (with Steven Givant). A Formalization of Set Theory Without Variables. Providence RI: American Mathematical
Society.
- 1999 (with Steven Givant). "Tarski's system of geometry," Bulletin of Symbolic Logic 5: 175-214.
- 2002. "On the Concept of Following Logically" (Magda Stroińska and David Hitchcock, trans.) History and Philosophy of
Logic 23: 155-96.
Biographical:
- Feferman, Anita Burdman, 1999. "Alfred Tarski" in American National Biography vol. 19. Oxford Univ. Press:
330-332.
- Feferman, A. B., and Solomon Feferman, 2004. Alfred Tarski: Life and Logic.
Cambridge Univ. Press. Extensive bibliography.
- Givant, Steven, 1991. "A portrait of Alfred Tarski", Mathematical Intelligencer 13: 16-32.
Secondary:
The December 1986 issue of the Journal of Symbolic Logic surveys Tarski's work on model
theory (Robert Vaught), algebra
(Jonsson), undecidable theories (McNulty), algebraic logic (Donald Monk), and geometry (Szczerba). The March 1988
issue of the same journal surveys his work on axiomatic set theory (Azriel Levy),
real closed fields (Lou Van Den Dries), decidable theory (Doner and Wilfrid Hodges),
metamathematics (Blok and Pigozzi), truth and
logical consequence (John Etchemendy), and
general philosophy (Patrick Suppes).
- Ivor Grattan-Guinness, 2000. The Search for Mathematical Roots
1870-1940. Princeton Uni. Press.
- Kirkham, Richard, 1992. Theories of Truth. MIT Press.
- Karl R. Popper, 1972, Rev. Ed. 1979, "Philosophical Comments on Tarski's Theory of
Truth," with Addendum, Objective Knowledge, Oxford: 319-340.
- Sinaceur, H., 2001. "Alfred Tarski: Semantic shift, heuristic shift in metamathematics," Synthese 126: 49-65.
- Wolenski, Jan, 1989. Logic and Philosophy in the Lvov–Warsaw School. Reidel/Kluwer.
Other references:
- Chang, C.C., and Keisler, H.J., 1973. Model Theory. North-Holland, Amsterdam. American Elsevier, New York.
- Etchemendy, John, 1999. The Concept of Logical Consequence. Stanford CA: CSLI Publications. ISBN 1-57586-194-1
- Solomon Feferman, 1999. "Logic, Logics, and
Logicism," Notre Dame Journal of Formal Logic 40: 31-54.
- Maddux, Roger D., 2006. Relation Algebras, vol. 150 in "Studies in Logic and the
Foundations of Mathematics." Elsevier Science.
- Mautner, F. I., 1946. "An Extension of Klein's Erlanger Program: Logic as Invariant-Theory," American Journal of
Mathematics 68: 345-84.
- McGee, Van, 1996. "Logical Operations", Journal of Philosophical Logic 25: 567-80.
See also
- Banach–Tarski paradox
- History of philosophy in Poland
- Knaster–Tarski theorem
- Lindenbaum–Tarski algebra
- Lwów–Warsaw School of Logic
- Model theory
- T-schema
- Tarski monster group
|
|
External links
pms:Alfred Tarski
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
