Alfred Tarski

Alfred Tarski

Alfred Tarski (January 14, 1901 – October 26, 1983) was a logician and mathematician of considerable philosophical importance. A brilliant member of the interwar Warsaw School of Mathematics and active in the United States after 1939, he wrote on topology, geometry, measure theory, mathematical logic, set theory, metamathematics, and most of all, on model theory, abstract algebra, and algebraic logic. His biographers, Anita Feferman and Solomon Feferman (2004), wrote that he was "one of the greatest logicians of all time...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."

Contents

Life

Tarski was born Alfred Teitelbaum (Polish spelling: Tajtelbaum) in Warsaw to parents who were Polish Jews in comfortable circumstances. His mother, Rosa Prussak, is considered to be responsible for his later brilliance. Tarski first revealed his mathematical abilities while at Warsaw's Schola Mazowiecka, an unusually good secondary school for that place and time. Nevertheless, in 1918 he entered the University of Warsaw intending to study biology.

In 1919, Poland regained its independence for the first time since 1795, and the University of Warsaw 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 the University of Warsaw, 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 Ph.D. under Leśniewski's supervision. Tarski and Leśniewski soon grew cool to each other; in later life, Tarski reserved his warmest praise for Tadeusz Kotarbiński.

In 1923, he and his brother Wacław changed their surnames to Tarski, a name they invented because it sounded very Polish, was simple to spell and pronounce, and was unused (years later, he met another Alfred Tarski in northern California). The Tarski brothers also converted to Roman Catholicism, the dominant religion in Poland. Tarski did so even though he was an avowed atheist because he was about to finish his Ph.D. and correctly anticipated that it would be difficult for a Jew to obtain a serious position in the new Polish university system (the pre-1918 universities had been controlled by the Imperial Russian and Austro-Hungarian governments). Tarski was caught up in the Polish nationalism of the time and wished to be fully accepted as a Pole. He remained warm to matters Polish in conversation throughout his later American life.

After becoming the youngest person ever to complete a Ph.D. at the University of Warsaw, Tarski did a variety of work in Warsaw: teaching logic at the Polish Pedagogical Institute, mathematics and logic at the university, and serving as Lukasiewicz's assistant. Because these positions were poorly paid, Tarski also taught mathematics in a Warsaw secondary school; before World War II, it was not uncommon for European intellectuals of research caliber to teach high school. It should be kept in mind that between 1923 and his departure for the United States in 1939, Tarski not only wrote several textbooks and many papers, a number of them pathbreaking, but did so while supporting himself primarily by teaching high school mathematics.

In 1929, Tarski married a fellow teacher, Maria Witkowski. She had worked as a courier for the army during Poland's fight for independence. They had two children. He also applied for the chair of philosophy at Lvov, but it was awarded to Leon Chwistek on Bertrand Russell's recommendation. In 1937, Tarski applied for a chair at the University of Poznan. Rather than award a chair to someone of Jewish ancestry, the position was abolished.

In 1930 Tarski visited the University of Vienna, where he lectured to Carl 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 ultimately saved his life as 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 leave Poland for the United States before the German invasion of Poland and the outbreak of World War II. Tarski left reluctantly because Lesniewski had died a few months before, creating a vacancy that Tarski very much hoped to fill. Tarski was so oblivious to the Nazi threat that he left his wife and children in Warsaw; he did not see them again until 1946. Nearly all of his extended family died at the hands of the Nazis during the war.

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 met Gödel again. Tarski became an American citizen in 1945.

Tarski joined the Mathematics Department at the University of California, Berkeley in 1942, where he spent the rest of his career. Although emeritus from 1968 on, he taught until 1973 and supervised Ph.Ds until his death on October 26, 1983. At Berkeley, Tarski acquired a reputation as a demanding teacher:


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. (Feferman 1999)

Tarski supervised 24 Ph.D. dissertations—including five 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, and the authors of the classic text on model theory, Chang and Keisler (1973).

Tarski lectured at University College, London (1950, 1966), the Henri Poincaré Institute in Paris (1955), the Miller Institute of Basic Research in Science (1958-1960), the University of California, Los Angeles (1967), and the Catholic University of Chile (1974-1975). He was elected to the National Academy of Sciences and the British Academy, and presided over the Association for Symbolic Logic (1944-1946), and the International Union for the History and Philosophy of Science (1956-1957).

Mathematician

Tarski's mathematical interests were exceptionally broad for a mathematical logician. His collected papers run to about 2,500 pages, with most of those papers treating of 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 only 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 sphere 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. "Paradoxical" here means "counterintuitive."

Cardinal algebras studies algebras whose models include the arithmetic of cardinal numbers. Ordinal algebras sets out an algebra for the additive theory of order types. Addition commutes cardinal, but not ordinal.

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 naturals replace the reals) is not decidable. Peano arithmetic is also incompletable (Gödel's incompleteness theorem, 1931). In Undecidable Theories, Tarski et al. showed that many mathematical systems, including lattice theory, abstract projective geometry, and closure algebras, are all undecidable. Abelian groups are decidable but non-Abelian groups are not.

In the 1920s and 1930s, Tarski often taught 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 thing, 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 Euclidian geometry of the plane, one considerably more concise than that in Hilbert's Grundlagen der Geometrie. The result was a first order theory, devoid of set theory, whose individuals are points, and having only two primitive relations. In 1930, he proved his version of Euclidian plane geometry decidable because it maps into the first-order theory of the real numbers, whose decidability is mentioned above. The culmination of Tarski's work on geometry is Tarski and Givant (1999).

Tarski (1941) is an important paper on binary relations, whose methods matured into a powerful relation algebra and whose metamathematics Tarski (along with Roger Lyndon) and his students carefully explored. While that exploration uncovered some important limitations, Tarski also showed (Tarski and Givant 1987) that relation algebra is powerful enough to express most axiomatic set theories 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 two monographs by Tarski, Henkin, and Monk (1971, 1985).

Logician

Aristotle, Gottlob Frege, Kurt Gödel, and Tarski are sometimes considered to be the four greatest logicians of all time (Vaught 1986). Of these four, Tarski was the best mathematician and the most prolific author. Neither Frege nor Gödel ever supervised a single Ph.D. or coauthored any papers with anyone; 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, whose culmination was the model theory he and a number of his Berkeley students developed in the 1950s and 1960s, 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 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 considering the role of logic in scientific studies. His high school and undergraduate teaching on logic and axiomatics culminated in his 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

The "Convention T" (also T-schema) standard in his "inductive definition of truth" was an important contribution to symbolic logic, semantics, and the philosophy of language.

"The Concept of Truth in Formalized Languages" is a long (over one hundred pages) paper setting out a mathematical definition of truth for logical languages. It first appeared in 1933 in Polish ("Pojęcie prawdy w językach nauk dedukcyjnych") and then in 1935 in German, under the title "Der Wahrheitsbegriff in den Sprachen der deduktiven Disziplinen." It is thus sometimes referred to as the "Wahrheitsbegriff." Its first appearance in full in English was in 1956 in the first edition of Logic, Semantics, Metamathematics.

Tarski's concept of truth was quite influential on members of the Vienna Circle and on Karl Popper, who credits it explicitly.

Some recent philosophical debate has examined the extent to which Tarski's theory of truth for formalized languages can be seen as a correspondence theory of truth. The debate centers 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 either the modern model-theoretic definition of (semantic) logical consequence, or the basis for that modern notion. Whether Tarski's notion was 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. 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 was derived from the Erlangen program of nineteenth-century German mathematician Felix Klein (Mautner 1946).

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-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 (equilateral triangles from non-equilateral triangles, for instance). Continuous transformations (which can intuitively be thought of as transformations which allow non-uniform stretching, compression, bending, and twisting, but no ripping or gluing) allow us to distinguish a polygon from an annulus (ring with a hole in the center), but does not allow us to distinguish two polygons from each other.

Tarski's proposal was to demarcate the logical notions by considering all possible one-one transformations of a domain onto itself (by domain here is meant the universe of discourse of a model for the semantic theory of a logic. A one-one transformation of a set onto itself is also known as an automorphism). If one identifies the truth-value True with the domain set and the truth-value False with the empty set, then the following sorts of 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).
  1. 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 nine 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."
  2. Set-Theoretic relations: Relations such as inclusion, intersection and union applied to subsets of the domain are logical in the present sense.
  3. Set-theoretic membership: Tarski ended his lecture with a discussion of whether the set theory relation of membership 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 of) mathematics is a part of logic. He pointed out that if you develop set-theory along the lines of a type-theory, set membership does count as logical, whereas if you develop your set theory axiomatically, as in Zermelo-Fraenkel set theory, it counts as extralogical.
  4. Logical notions of higher order: Tarski confined his discussion to operations of first-order logic. However, there is nothing about his proposal that explicitly 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-one transformations of the domain onto itself. The present proposal is also employed in Tarski and Givant (1987).

Tarski's proposal was discussed in more recent work of Feferman and McGee. Feferman (1999) raises problems for the proposal and suggests a modification. Feferman's suggestion is to substitute preservation by arbitrary homomorphism for Tarski's preservation by automorphisms. In essence, this suggestion is made to circumvent the difficulties that 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, disjunction and quantification over arbitrarily long sequences of variables. In both cases, "arbitrarily long" admits lengths of any ordinality, finite or infinite.

Bibliography

Primary sources

  • Tarski, Alfred and Adolf Lindenbaum. 1936. "On the Limitations of Deductive Theories" in Tarski (1983): 384-392.
  • Tarski, Alfred. [1941] 1994. Introduction to Logic and to the Methodology of Deductive Sciences. Mineola, NY: Dover Publications.
  • Tarski, Alfred. 1941. "On the Calculus of Relations." Journal of Symbolic Logic 6: 73-89.
  • Tarski, Alfred. 1944. “The Semantical Concept of Truth and the Foundations of Semantics.” Philosophy and Phenomenological Research 4: 341-375. Retrieved September 11, 2007.
  • Tarski, Alfred. 1948. A Decision Method for Elementary Algebra and Geometry. Santa Monica, CA: RAND Corp.
  • Tarski, Alfred. 1949. Cardinal Algebras. Oxford: Oxford University Press.
  • Tarski, Alfred. [1956] 1983. Logic, Semantics, Metamathematics, Corcoran, J., ed. Hackett. 1st edition edited and translated by J. H. Woodger, Oxford Uni. Press.
    • Many of Tarski's more important papers written during his Polish years are translated in this collection.
  • Tarski, Alfred, Andrzej Mostowski and Rafael Robinson. 1953. Undecidable Theories. Amsterdam: North-Holland.
  • Tarski, Alfred. 1956. Ordinal Algebras. Amsterdam: North-Holland.
  • Tarski, Alfred. 1969. "Truth and Proof." Scientific American 220: 63-77.
  • Tarski, Alfred, Leon Henkin and Donald Monk. 1971. Cylindric Algebras: Part I. Amsterdam: North-Holland.
  • Tarski, Alfred, Leon Henkin and Donald Monk. 1985. Cylindric Algebras: Part II. Amsterdam: North-Holland.
  • Tarski, Alfred. 1986. The Collected Papers of Alfred Tarski, 4 vols. Ed. Steven Givant and R. N. McKenzie. Birkauser.
  • Tarski, Alfred. 1986. "What are Logical Notions?" in History and Philosophy of Logic 7: 143-154.
  • Tarski, Alfred, and Steven Givant. 1987. A Formalization of Set Theory Without Variables. Providence, RI: American Mathematical Society.
  • Tarski, Alfred, and Steven Givant. 1999. "Tarski's System of Geometry." Bulletin of Symbolic Logic 5: 175-214.
  • Tarski, Alfred. 2002. "On the Concept of Following Logically", trans. Magda Stroińska and David Hitchcock. History and Philosophy of Logic 23: 155-196.

Secondary sources

  • Chang, C. C., and H. J. Keisler. 1973. Model Theory. Amsterdam: North-Holland.
  • Etchemendy, John. 1999. The Concept of Logical Consequence. Stanford, CA: CSLI Publications. ISBN 1575861941
  • Feferman, Anita B. 1999. "Alfred Tarski" in American National Biography, vol. 19, 330-332. Oxford: Oxford University Press.
  • Feferman, Anita B. and Solomon Feferman. 2004. Alfred Tarski: Life and Logic. Cambridge: Cambridge University Press. ISBN 0521802407
  • Feferman, Solomon. 1999. “Logic, Logics, and Logicism.” Notre Dame Journal of Formal Logic 40: 31-54.
  • Givant, Steven. 1986. "Bibliography of Alfred Tarski." Journal of Symbolic Logic 51: 913-941.
  • Givant, Steven. 1991. "A Portrait of Alfred Tarski." Mathematical Intelligencer 13: 16-32.
  • Grattan-Guinness, Ivor. 2000. The Search for Mathematical Roots 1870-1940. Princeton, NJ: Princeton University Press. ISBN 069105858X
  • Kirkham, Richard. [1992] 1995. Theories of Truth: A Critical Introduction. Cambridge, MA: MIT Press. ISBN 0262611082
  • 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-384.
  • McGee, Van. 1996. "Logical Operations." Journal of Philosophical Logic 25: 567-580.
  • 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. Springer. ISBN 902772749X

External links

All links retrieved March 5, 2016.

General Philosophy Sources

Credits

New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:

Note: Some restrictions may apply to use of individual images which are separately licensed.