Alfred Tarski

How to use this course

Alfred Tarski described himself as a mathematician, a logician, and perhaps a philosopher of a sort. All three labels fit. Philosophers know him for the semantic definition of truth. Logicians know him as a founder of model theory and of the study of decidable and undecidable theories. Algebraists and geometers know the decision method for real closed fields, the fixed-point theorem for lattices, and the paradox he proved with Stefan Banach. This course covers all of these, alongside the story of a Polish Jewish scholar who was stranded in America by the outbreak of war and who rebuilt his school there.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proof sketches and exercises with folded solutions. The order is roughly chronological: set theory and measure (1924–1938), truth and consequence (1929–1936), decision methods (1930–1951), undecidability (1953), and the algebraic logic of the Berkeley years.

Timeline

Warsaw, 1901–1918

Alfred Teitelbaum, in Polish spelling Tajtelbaum, was born in Warsaw on 14 January 1901. Warsaw was then the capital of the Kingdom of Poland inside the Russian Empire. His father, Ignacy Teitelbaum, was a Jewish merchant in the timber trade; his mother was Rosa Prussak. The family was comfortably off, and Alfred and his younger brother Wacław received a good education.

He attended the Schola Mazowiecka, a respected Warsaw secondary school, and did well in mathematics, but he intended to become a biologist. In 1918, as Poland regained its independence, he finished school, served briefly in the new Polish army, and enrolled at the reopened University of Warsaw to study biology.

Warsaw in 1918 was an unusual place to start. The university had been refounded as a Polish institution only in 1915. A group of young mathematicians, led by Wacław Sierpiński, Zygmunt Janiszewski and Stefan Mazurkiewicz, had decided to concentrate the new Polish mathematics on set theory, topology and logic, fields where a small country could compete. In 1920 they founded Fundamenta Mathematicae, the first journal devoted to these subjects. Tarski arrived just as this programme began.

Leśniewski’s student, 1918–1924

In his first year Tarski attended the logic course of Stanisław Leśniewski, a philosopher-logician of great rigour who was building his own systems of logic, called protothetic, ontology and mereology. The course persuaded him to switch from biology to mathematics. His teachers also included the logician Jan Łukasiewicz, the philosopher Tadeusz Kotarbiński, and the mathematicians Sierpiński and Mazurkiewicz. His studies were interrupted in 1920, when he again served in the army during the Polish–Soviet War.

His first paper, on set theory, appeared in 1921, when he was 19. His doctoral thesis, O wyrazie pierwotnym logistyki (On the primitive term of logistic), was published in 1923. It showed that in a logic with quantifiers over propositions, all the propositional connectives can be defined from equivalence alone. Leśniewski adopted the result as the basis of his protothetic. Tarski received his doctorate in 1924. He was Leśniewski’s only doctoral student, and he was then among the youngest doctors the university had produced.

A new name

In 1923 Alfred and Wacław changed their surname to Tarski and converted from Judaism to Roman Catholicism. Tarski was not religious; he was by his own account an atheist. His biographers, Anita Burdman Feferman and Solomon Feferman, connect the decision with Polish nationalism and with the real obstacles that Jewish scholars faced in obtaining university chairs. The change did not remove those obstacles.

From 1922 to 1925 he taught logic at the Polish Pedagogical Institute in Warsaw. He was already working on two fronts that would define his career: the foundations of logic in the Warsaw tradition, and the set theory of Fundamenta.

Docent and schoolteacher, 1924–1939

1924 was Tarski’s breakthrough year in set theory. In Fundamenta he proved that the axiom of choice is equivalent to the statement that every infinite set has the same cardinality as its square, and with Stefan Banach he proved the paradoxical decomposition of the ball (Lesson 04). In 1925 he became a docent at the University of Warsaw, with the right to lecture but no salary to speak of. He also served as assistant to Łukasiewicz. To earn a living he taught mathematics from 1925 to 1939 at Żeromski’s Lycée, a Warsaw secondary school, alongside his university work.

The Warsaw logic seminar of Łukasiewicz and Tarski became one of the most productive centres of logic in Europe. Its members studied the propositional calculus, many-valued logics, and the methodology of deductive sciences. In 1929 Tarski’s student Mojżesz Presburger showed that the theory of the natural numbers with addition alone is decidable. Adolf Lindenbaum, Tarski’s closest collaborator in these years, proved that every consistent set of sentences extends to a complete one. Tarski and Kazimierz Kuratowski showed in 1931 that the quantifier structure of a definition predicts where a set lies in the hierarchy of projective sets: an existential quantifier corresponds to a projection and a universal quantifier to the complement of one. With Sierpiński he introduced strongly inaccessible cardinals in 1930.

In 1929 he married Maria Witkowska, who also taught at Żeromski’s Lycée. They had a son, Jan, later a physicist, and a daughter, Ina. In February 1930 he lectured in Vienna and met the young Kurt Gödel, beginning a long friendship.

Truth and consequence

From the seminar came the two papers that made his name among philosophers. Pojęcie prawdy w językach nauk dedukcyjnych (1933), published in German in 1935 as Der Wahrheitsbegriff in den formalisierten Sprachen, gave a mathematical definition of truth for formal languages and proved that truth for a sufficiently rich language cannot be defined within that language. On the concept of logical consequence (1936) defined consequence through models. He presented these ideas to the Unity of Science congress in Paris in 1935, where Rudolf Carnap and others took them up. His textbook O logice matematycznej i metodzie dedukcyjnej (1936), translated as Introduction to Logic and to the Methodology of Deductive Sciences, became one of the most widely read introductions to logic.

Despite this work, Tarski never obtained a professorship in Poland. He applied for chairs in the 1930s, including one at Lwów, without success; his biographers count antisemitism among the reasons. In August 1939 he sailed to the United States to speak at the Unity of Science congress at Harvard, intending to return. He left his wife and their two young children in Warsaw. Germany invaded Poland on 1 September 1939. He would not see his family for seven years.

Choice, measure and paradox

For the general reader. Tarski’s first fame came from set theory, the study of infinite collections. He showed that a simple-sounding statement about infinite sets is equivalent to the axiom of choice, the principle that lets one pick an element from each of infinitely many sets at once. With Banach he showed that this same principle allows a ball to be cut into a few pieces and reassembled into two balls of the same size. He then proved the deeper fact behind the paradox: a set fails to carry a sensible notion of size exactly when it can be duplicated in this way.

Squares of cardinals

For an infinite set \(A\), the Hartogs number \(\aleph(A)\) is the least ordinal that does not inject into \(A\). It exists without the axiom of choice.

Proof of (2)⇒(1). It suffices to show every set \(A\) can be well-ordered; we may take \(A\) infinite and disjoint from \(\kappa=\aleph(A)\). Put \(B=A\sqcup\kappa\). By (2) there is an injection \(f:A\times\kappa\to B\). For each \(a\in A\), the map \(\alpha\mapsto f(a,\alpha)\) cannot send all of \(\kappa\) into \(A\), since \(\kappa\) does not inject into \(A\). Let \(\alpha_a\) be the least \(\alpha\) with \(f(a,\alpha)\in\kappa\), and set \(g(a)=f(a,\alpha_a)\). Since \(f\) is injective, \(g:A\to\kappa\) is injective, so \(A\) inherits a well-order from \(\kappa\). The direction (1)⇒(2) is Hessenberg’s theorem \(\kappa\cdot\kappa=\kappa\) for infinite alephs.

Paradoxical decompositions

Let a group \(G\) act on a set \(X\). A subset \(E\subseteq X\) is \(G\)-paradoxical if there are pairwise disjoint \(A_1,\dots,A_n,B_1,\dots,B_m\subseteq E\) and \(g_i,h_j\in G\) with \(E=\bigcup_i g_iA_i=\bigcup_j h_jB_j\).

The proof, outlined in the Banach course, rests on a free subgroup of \(\mathrm{SO}(3)\) and on the Banach–Schröder–Bernstein theorem. Tarski then asked what exactly a paradox obstructs. His answer, worked out over the following years and published in 1938, is a perfect duality.

One direction is Exercise 4.1. The other is hard: Tarski built the measure from a theory of “cardinal algebras” of equidecomposition types, which he later developed in his 1949 book of that name. Applied to a group acting on itself, the theorem says that a group is amenable, in John von Neumann’s sense, exactly when it is not paradoxical.

Squaring the circle

In 1925 Tarski asked whether a disc and a square of the same area in the plane are equidecomposable. Banach’s 1923 measure shows that equal area is necessary, and the plane admits no paradoxes, so the question is delicate. Lester Dubins, Morris Hirsch and Jack Karush showed in 1963 that it cannot be done with pieces bounded by Jordan curves. Miklós Laczkovich proved in 1990 that it can be done, using translations alone and roughly \(10^{50}\) non-measurable pieces. In 2017 Andrew Marks and Spencer Unger found a decomposition with Borel pieces.

The concept of truth

For the general reader. The sentence “snow is white” is true if and only if snow is white. Tarski took this platitude seriously. He showed how to define truth for a formal language so that every such equivalence follows from the definition, and he proved that the definition must always be given in a stronger language. A language rich enough to talk about arithmetic cannot define its own truth. The ancient liar paradox, “this sentence is false”, becomes a theorem.

Object language and metalanguage

Tarski distinguished the object language \(\mathcal L\) under study from the metalanguage in which we talk about it. A definition of a predicate \(\mathrm{Tr}\) in the metalanguage is materially adequate if it satisfies

Truth cannot be defined directly by recursion on sentences, because the sentence \(\exists x\,\psi(x)\) is built from the formula \(\psi(x)\), which has a free variable and is neither true nor false. Tarski’s solution is to define satisfaction of a formula by an assignment \(s\) of objects to variables in a structure \(\mathcal M\):

A sentence is true in \(\mathcal M\) if every (equivalently, some) assignment satisfies it. In 1933 Tarski worked in the theory of types and spoke of “sequences” rather than structures; the relativization to an arbitrary structure \(\mathcal M\) became standard in his model theory of the 1950s.

Undefinability

Fix a Gödel numbering of the language of arithmetic \(\{0,S,+,\cdot\}\), let \(\mathbb N\) be the standard model, and write \(\overline n\) for the numeral of \(n\).

Proof. Suppose \(\mathrm{True}(x)\) existed. Apply the diagonal lemma to \(\neg\mathrm{True}(x)\) to get \(\delta\) with \(\mathbb N\models\delta\leftrightarrow\neg\mathrm{True}(\overline{\ulcorner\delta\urcorner})\). Combined with the T-sentence for \(\delta\), this gives \(\mathbb N\models\delta\leftrightarrow\neg\delta\), a contradiction. The sentence \(\delta\) is a formal liar: it says of itself that it is not true.

The proof is a close relative of Gödel’s 1931 argument, and Tarski acknowledged the debt. The difference is instructive. Provability in a recursively axiomatized theory is definable in arithmetic, by a \(\Sigma_1\) formula, so Gödel’s diagonal sentence “I am not provable” is not paradoxical: it is true and unprovable. Truth is not definable at all. For each \(n\), truth for \(\Sigma_n\) sentences is definable by a \(\Sigma_n\) formula, but no single formula covers every level. To define truth for \(\mathcal L\) one needs a metalanguage of higher order, or set theory, or an explicit axiomatic truth predicate.

Consequence and the theory of models

For the general reader. When does a conclusion follow from premises? Tarski’s 1936 answer was that it follows when every interpretation making the premises true also makes the conclusion true. Interpretations of this kind are called models. In the 1950s Tarski and his Berkeley students turned the study of models into a branch of mathematics, with its own theorems about which properties first-order sentences can and cannot express.

By Gödel’s completeness theorem (1930), for first-order logic \(K\models\varphi\) holds exactly when \(\varphi\) is formally provable from \(K\). Tarski’s point in 1936 was that consequence is a semantic notion, prior to any proof system; he noted that incompleteness phenomena show the two notions can diverge for richer logics.

Elementary substructures

Two structures are elementarily equivalent, \(\mathcal M\equiv\mathcal N\), if they satisfy the same first-order sentences. A substructure \(\mathcal M\subseteq\mathcal N\) is elementary, \(\mathcal M\preccurlyeq\mathcal N\), if for every formula \(\varphi(\bar x)\) and tuple \(\bar a\) from \(M\), \(\mathcal M\models\varphi(\bar a)\iff\mathcal N\models\varphi(\bar a)\).

Proof. Necessity is immediate. For sufficiency, prove \(\mathcal M\models\varphi(\bar a)\iff\mathcal N\models\varphi(\bar a)\) by induction on \(\varphi\). Atomic formulas agree because \(\mathcal M\) is a substructure; connectives are trivial. If \(\mathcal N\models\exists y\,\varphi(y,\bar a)\), the hypothesis gives a witness \(b\in M\), so \(\mathcal N\models\varphi(b,\bar a)\), hence \(\mathcal M\models\varphi(b,\bar a)\) by induction, so \(\mathcal M\models\exists y\,\varphi\). The converse direction is clear.

The downward form goes back to Leopold Löwenheim (1915) and Thoralf Skolem (1920); one closes \(S\) under witnesses for existential formulas and applies the Tarski–Vaught test. Tarski’s name is attached to the upward form, which he noted in his Warsaw seminar in the late 1920s; the general version appeared with Robert Vaught in 1957. Both depend on the compactness theorem: a set of first-order sentences has a model if every finite subset does (Gödel for countable languages, 1930; Anatoly Maltsev in general, 1936).

Tarski’s three-part Contributions to the theory of models (1954–55) fixed the vocabulary of the subject. His students carried it forward: Vaught on countable models, Chen Chung Chang and H. Jerome Keisler with the standard textbook Model Theory (1973), William Hanf and Keisler on infinitary languages. The Keisler–Tarski paper From accessible to inaccessible cardinals (1964) set out how compactness properties of infinitary logics produce large cardinals, and showed in particular that the first measurable cardinal, if it exists, lies far beyond the first inaccessible.

Real closed fields and elementary geometry

For the general reader. Any question about real numbers that can be written using addition, multiplication, comparison, “and”, “or”, “not”, “for all” and “there exists” can be answered by a mechanical procedure. Tarski found this procedure around 1930. It covers every problem of classical Euclidean geometry, since such problems can be translated into algebra. It is the reason computers can, in principle, prove any elementary geometry theorem.

An ordered field is real closed if every positive element has a square root and every polynomial of odd degree has a root. Examples are \(\mathbb R\) and the field of real algebraic numbers. A set \(S\subseteq\mathbb R^n\) is semialgebraic if it is a finite Boolean combination of sets \(\{x:p(x)>0\}\) and \(\{x:p(x)=0\}\) with polynomials \(p\).

Abraham Seidenberg gave an independent, more algebraic proof in 1954. The geometric form is the starting point of real algebraic geometry and, later, of o-minimality.

How elimination works

It suffices to eliminate one existential quantifier from a conjunction of sign conditions, \(\exists x\,\bigwedge_i p_i(x,\bar y)\,\square_i\,0\) with \(\square_i\in\{<,=,>\}\). Tarski’s method generalizes Sturm’s theorem, which counts the real roots of a polynomial in an interval through sign changes in a sequence of remainders. Close the family \(\{p_i\}\) under derivatives and remainders, and treat leading coefficients by case distinction on \(\bar y\). The sign of each polynomial between consecutive real roots of the family is then determined by the signs of the family at those roots, and these are expressible by quantifier-free conditions on \(\bar y\). Tarski’s procedure was correct but very slow. George Collins’s cylindrical algebraic decomposition (1975) runs in time doubly exponential in the number of variables, and examples show this cannot be improved in general.

Elementary geometry

Tarski axiomatized plane Euclidean geometry with points as the only objects and two primitive relations: betweenness \(B(x,y,z)\), “\(y\) lies between \(x\) and \(z\)”, and equidistance \(xy\equiv zw\). The axioms are a short list of first-order statements plus one first-order continuity schema in place of Hilbert’s second-order completeness axiom. Coordinates turn every model into the plane \(F^2\) over a real closed field \(F\). By the theorem above, elementary geometry is complete and decidable, a result Tarski developed in Warsaw in the late 1920s and summarized in What is elementary geometry? (1959).

The boundary of decidability is sharp. The field of rationals and the ring of integers have undecidable theories (Lesson 08). Tarski asked whether the reals with exponentiation remain decidable. Alex Wilkie proved in 1996 that this structure is model complete, and Angus Macintyre and Wilkie showed it is decidable if Schanuel’s conjecture in transcendental number theory is true.

Undecidable theories

For the general reader. After Alonzo Church and Alan Turing showed in 1936 that some mathematical problems have no algorithmic solution, Tarski asked which familiar theories are undecidable. With Andrzej Mostowski and Raphael Robinson he found a method: locate inside a theory a small, finitely described fragment of arithmetic. Any theory compatible with that fragment inherits its undecidability. The method settled the status of groups, rings, fields and lattices.

A theory \(T\) (a set of sentences closed under consequence) is decidable if membership in \(T\) is computable. \(T\) is essentially undecidable if every consistent extension of \(T\) in the same language is undecidable.

Robinson arithmetic \(Q\) has seven axioms in \(\{0,S,+,\cdot\}\): \(Sx\ne0\); \(Sx=Sy\to x=y\); \(x\ne0\to\exists y\,(x=Sy)\); \(x+0=x\); \(x+Sy=S(x+y)\); \(x\cdot0=0\); \(x\cdot Sy=x\cdot y+x\). It has no induction axioms.

Proof of (b) from (a). Let \(\sigma\) be the conjunction of the seven axioms. If \(T\) were decidable, so would be \(T'=\{\varphi:\sigma\to\varphi\in T\}\), which by the deduction theorem is the theory generated by \(T\cup\{\sigma\}\). This is a consistent extension of \(Q\), contradicting (a). Here finite axiomatizability of \(Q\) is essential. Part (a) is proved by showing that every recursive function is representable in \(Q\) and then running the diagonal argument of Lesson 05.

The map of decidability

• Undecidable: Peano arithmetic and ZF set theory; the theory of groups (Tarski); rings; fields, because Julia Robinson showed in 1949 that the integers are first-order definable in the field \(\mathbb Q\); lattices; the theory of a single binary relation.
• Decidable: Presburger arithmetic \((\mathbb N,+)\); real closed fields and algebraically closed fields of given characteristic (Tarski); Boolean algebras (Tarski); abelian groups (Wanda Szmielew, 1955); elementary geometry.

Tarski also asked, around 1945, whether all free groups of rank at least 2 satisfy the same first-order sentences. Olga Kharlampovich and Alexei Myasnikov, and independently Zlil Sela, proved in work published in 2006 that they do, and that the common theory is decidable.

Lattices, fixed points, Boolean algebras

For the general reader. Many constructions in mathematics and computing look for a solution of an equation \(x=f(x)\) where \(f\) only ever makes things bigger. Tarski proved that in a complete lattice such equations always have a smallest and a largest solution. The theorem now underlies the semantics of recursive programs. Tarski also used algebra to study logic itself, turning sets of formulas into Boolean algebras.

A complete lattice is a partially ordered set in which every subset has a supremum \(\bigvee\) and an infimum \(\bigwedge\). A map \(f:L\to L\) is monotone if \(x\le y\) implies \(f(x)\le f(y)\).

Proof of the least fixed point. Let \(P=\{x:f(x)\le x\}\) and \(a=\bigwedge P\). For \(x\in P\), \(a\le x\), so \(f(a)\le f(x)\le x\). Hence \(f(a)\) is a lower bound of \(P\), and \(f(a)\le a\). Then \(f(f(a))\le f(a)\), so \(f(a)\in P\) and \(a\le f(a)\). Thus \(f(a)=a\), and any fixed point lies in \(P\), hence above \(a\). The full lattice statement applies the same argument to the intervals \([y,\top]\) for \(y\) a supremum of fixed points.

Bronisław Knaster and Tarski proved the case \(L=\mathcal P(X)\) in 1928. Tarski published the general theorem in 1955, and in the same issue of the Pacific Journal of Mathematics Anne Davis proved the converse: a lattice in which every monotone map has a fixed point is complete. In computer science, the meaning of a recursive definition is taken to be the least fixed point of a monotone operator, and much of program semantics and verification is built on this theorem.

Boolean algebras and logic

Given a propositional or first-order theory \(T\), identify sentences \(\varphi,\psi\) when \(T\vdash\varphi\leftrightarrow\psi\). The classes form a Boolean algebra under \(\wedge,\vee,\neg\), the Lindenbaum–Tarski algebra of \(T\). Its ultrafilters correspond to complete extensions of \(T\), so Lindenbaum’s lemma becomes the existence of ultrafilters.

Marshall Stone’s representation theorem (1936) handles all Boolean algebras, as algebras of clopen sets of a compact space. Tarski went on to study the arithmetic of cardinal numbers without choice in Cardinal Algebras (1949), abstracting the equidecomposition types of Lesson 04, and order types in Ordinal Algebras (1956).

Relation and cylindric algebras

For the general reader. George Boole had turned propositional logic into algebra in the nineteenth century. Tarski spent much of his later career doing the same for full first-order logic, with its variables and quantifiers. One approach treats relations themselves as elements of an algebra, combined by composition and reversal. Another treats quantifiers as operations on sets of points in a high-dimensional space. Both programmes showed how much of logic and set theory can be written as equations.

The calculus of relations

For a set \(U\), the binary relations on \(U\) form an algebra under union, complement, composition \(R;S=\{(x,z):\exists y\,(xRy\wedge ySz)\}\), converse \(R^{\smile}=\{(y,x):xRy\}\), and the identity relation \(1'\). Tarski’s 1941 paper On the calculus of relations, reviving work of Augustus De Morgan, Charles Sanders Peirce and Ernst Schröder, gave a finite list of equations for these operations. Algebras satisfying them are relation algebras.

Tarski showed that the equational theory of relation algebras has exactly the expressive power of first-order logic restricted to three variables. In A Formalization of Set Theory without Variables (1987), completed with Steven Givant, he used a pairing trick to express all of ZF set theory as equations in this calculus, so that the whole of mathematics can be developed in a logic with no variables at all.

Cylindric algebras

For a set \(U\) and a dimension \(\alpha\), consider subsets of \(U^\alpha\), thought of as the sets of assignments satisfying formulas. The cylindrification \(c_i(X)=\{s:\ s(i\mapsto u)\in X\ \text{for some}\ u\in U\}\) interprets \(\exists x_i\), and the diagonal \(d_{ij}=\{s:s_i=s_j\}\) interprets \(x_i=x_j\). Abstracting their equational properties gives the cylindric algebras of Tarski, Leon Henkin and Donald Monk (Cylindric Algebras, Part I 1971, Part II 1985). They stand to first-order logic as Boolean algebras stand to propositional logic.

Exile and the Berkeley school, 1939–1968

Stranded in the United States in September 1939, Tarski held a series of temporary positions: Harvard from 1939, City College of New York in 1940, and the Institute for Advanced Study in Princeton in 1941–42 with a Guggenheim Fellowship. At Harvard he met Rudolf Carnap and W. V. O. Quine again, and their long discussions on semantics and logical truth shaped analytic philosophy after the war. In 1942 the University of California, Berkeley, appointed him to a one-year lectureship. He stayed for the rest of his life. He became a United States citizen and received tenure in 1945.

His wife and children survived the war in Poland and joined him in Berkeley in 1946. His parents, his brother Wacław and his sister-in-law were murdered by the Nazis. Most of the Warsaw logic school was destroyed: Lindenbaum and his wife, the philosopher Janina Hosiasson-Lindenbaum, were killed, as was Presburger.

Building a school

At Berkeley Tarski set out to recreate Warsaw, and did more. He recruited colleagues and students, ran a demanding seminar, and drew visitors from around the world. He supervised some two dozen doctoral dissertations. His students included Andrzej Mostowski (in Warsaw, 1938), Bjarni Jónsson (1946), Julia Robinson (1948), Wanda Szmielew (1950), Robert Vaught (1954), Chen Chung Chang (1955), Solomon Feferman and Richard Montague (1957), H. Jerome Keisler and Donald Monk (1961) and Haim Gaifman (1962). Leon Henkin, Dana Scott and many others worked with him closely. In 1958 he founded Berkeley’s interdisciplinary Group in Logic and the Methodology of Science, which still awards doctorates.

Tarski served as president of the Association for Symbolic Logic (1944–46) and of the International Union for the History and Philosophy of Science (1956–57). He gave the AMS Colloquium Lectures in 1952 and addressed the International Congress of Mathematicians at Cambridge, Massachusetts, in 1950, and spoke again at the Amsterdam congress of 1954. He organized the 1957–58 Berkeley symposium on the axiomatic method and helped organize the first International Congress for Logic, Methodology and Philosophy of Science, at Stanford in 1960.

Last years and legacy, 1968–1983

Tarski became professor emeritus in 1968 but kept teaching until 1973 and supervising doctoral students until his death. He continued to work on algebraic logic with Givant and on cylindric algebras with Henkin and Monk. He spent 1974–75 at the Catholic University of Chile. He was elected to the United States National Academy of Sciences, the Royal Netherlands Academy (1958) and, as corresponding fellow, the British Academy. He received honorary doctorates from the Catholic University of Chile (1975) and the University of Marseilles (1977), and the Berkeley Citation in 1981. He died in Berkeley on 26 October 1983, aged 82.

Legacy

• Logic: model theory, the semantics of first-order logic, and the classification of theories as decidable or undecidable all take their modern form from his work and his students’.
• Philosophy and linguistics: the semantic theory of truth is central to philosophy of language. His student Montague extended model-theoretic semantics to natural language.
• Mathematics: the Tarski–Seidenberg theorem founded semialgebraic geometry, which grew into o-minimality; the Banach–Tarski paradox and Tarski’s measure theorem founded the theory of amenability; fixed-point theory and Boolean algebras are standard tools.
• Computer science: least fixed points in program semantics, cylindrical algebraic decomposition in computer algebra, and decision procedures in automated reasoning all descend from his theorems.
• Memory: Berkeley holds annual Tarski Lectures in his honour. The standard biography is Anita Burdman Feferman and Solomon Feferman, Alfred Tarski: Life and Logic (2004).

Sources and further reading

Biography

1. J. J. O’Connor and E. F. Robertson, Alfred Tarski, MacTutor History of Mathematics.
2. Alfred Tarski, Wikipedia.
3. M. Gómez-Torrente, Alfred Tarski, Stanford Encyclopedia of Philosophy.
4. Alfred Tarski, Mathematics Genealogy Project.
5. A. B. Feferman and S. Feferman, Alfred Tarski: Life and Logic, Cambridge University Press, 2004.
6. J. W. Addison, L. Henkin and others, Alfred Tarski 1901–1983, memorial notices in J. Symbolic Logic 51 (1986) and 53 (1988).

Mathematics

1. S. Banach and A. Tarski, Sur la décomposition des ensembles de points en parties respectivement congruentes, Fund. Math. 6 (1924), 244–277.
2. A. Tarski, Sur quelques théorèmes qui équivalent à l’axiome du choix, Fund. Math. 5 (1924), 147–154.
3. A. Tarski, Der Wahrheitsbegriff in den formalisierten Sprachen, Studia Philosophica 1 (1935). English in Logic, Semantics, Metamathematics, Oxford, 1956; 2nd ed. Hackett, 1983.
4. A. Tarski, Algebraische Fassung des Maßproblems, Fund. Math. 31 (1938), 47–66.
5. A. Tarski, A Decision Method for Elementary Algebra and Geometry, RAND, 1948; 2nd ed. University of California Press, 1951.
6. A. Tarski, A. Mostowski and R. M. Robinson, Undecidable Theories, North-Holland, 1953.
7. A. Tarski, A lattice-theoretical fixpoint theorem and its applications, Pacific J. Math. 5 (1955), 285–309.
8. A. Tarski and R. L. Vaught, Arithmetical extensions of relational systems, Compositio Math. 13 (1957), 81–102.
9. L. Henkin, J. D. Monk and A. Tarski, Cylindric Algebras, Parts I and II, North-Holland, 1971 and 1985.
10. A. Tarski and S. Givant, A Formalization of Set Theory without Variables, AMS, 1987.
11. G. Tomkowicz and S. Wagon, The Banach–Tarski Paradox, 2nd ed., Cambridge University Press, 2016.
12. C. C. Chang and H. J. Keisler, Model Theory, 3rd ed., North-Holland, 1990; Dover, 2012.
13. S. Basu, R. Pollack and M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer, 2006.