Skip to main content

2018 | OriginalPaper | Buchkapitel

Alfred Tarski: Auxiliary Notes on His Legacy

verfasst von : Jan Zygmunt

Erschienen in: The Lvov-Warsaw School. Past and Present

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The purpose of this article is to highlight a selected few of Alfred Tarski's career achievements. The choice of these achievements is subjective. Section 1 is a general sketch of his life and work, emphasizing his role as researcher, teacher, organizer and founder of a scientific school. Section 2 discusses his contributions to set theory. Section 3 discusses his contributions to the foundations of geometry and to measure theory. Section 4 looks at his metamathematical work, and especially the decision problem for formalized theories. Section 5 is a selected bibliography to illustrate Sects. 1–4.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Tarski’s first university year, 1918–19, was a write-off. Classes were cancelled. Students and faculty signed up for military service. Stanisław Leśniewski, Stefan Mazurkiewicz and Wacław Sierpiński worked with the military on decoding Soviet communications. Tarski performed community service in lieu of military service.
In June, 1920, lectures were again cancelled and students and faculty again volunteered, Tadeusz Kotarbiński and Jan Łukasiewicz among them. This time Tarski served with a military supply and medical unit.
 
2
Jacek Jadacki speculates that Tarski’s habilitation thesis was the 50-page paper Sur les ensembles finis—i.e., [24c]. See J.J. Jadacki (ed.), Alfred Tarski: dedukcja i semantyka (déduction et semantique), Wydawnictwo Naukowe Semper: Warszawa 2003, p. 117. If true, Tarski must have researched and written two dissertations simultaneously.
 
3
For English translations see Chapter 12, Exercises Posed by Tarski, in A. McFarland, J. McFarland, James T. Smith (eds.), Alfred Tarski: Early Work in Poland—Geometry and Teaching. With a Bibliographic Supplement, Birkhäuser: New York 2014, pp. 243–272.
 
4
Geometria dla trzeciej klasy gimnazjalnej, co-authored with Z. Chwiałkowski and W. Schayer. For an English translation see McFarland–McFarland–Smith [2014], pp. 273–318.
 
5
…leaving his wife and children in Warsaw. In fact he had little choice, as his ship’s return sailing was cancelled.
 
6
Although emeritus from 1968, he continued teaching until 1973, and continued supervising Ph.D. candidates right up until his death in 1983.
 
7
The Mathematics Genealogy Project lists her as Louise Hoy Chin Lim.
 
8
For a beautifully written exposition of the first stages of these investigations, and their prehistory, see [61a]. For later developments, see [71m] and [85m].
 
9
The Mathematics Genealogy Project defines a “student of Tarski” as someone who was awarded a Ph.D. and whose dissertation listed Tarski as “Advisor 1” or “Advisor 2.”
 
10
In March, 1949, he was stripped of this distinction, as were other Polish scholars living abroad at that time, for failing to repatriate.
 
11
He seemed to tire of it for a spell in 1936 when he wrote to Karl Popper, “Ich arbeite an einer Monographie aus der Mengenlehre, aber es interessiert mich wenig: alte Sachen, mit denen ich mich schon seit Jahren nicht beschäftigt habe.” It is not clear if “schon seit Jahren nicht” was truth or posturing. Or possibly he just meant he had lost interest in writing a survey of established results; he preferred to work on getting new results. Sadly, the monograph he was referring to, Theorie der eineinendeutigen Abbildungen, which he was writing jointly with Adolf Lindenbaum and which was to have been “ein großes mathematisches Buch”, paid with its life. No working drafts ever surfaced, as far as anyone today knows.
 
12
Where “elementary theory of well-ordering” is understood as the set of all formulas of first-order predicate calculus that are true in every structure <U, R>, where U is a non-empty set and R is a (binary) relation which well-orders the set U.
 
13
Montague died in 1971. For reasons which remain unclear, Scott and Tarski ceased work on the manuscript in 1972. It remains unpublished to this day.
 
14
See [25] and [30f].
 
15
See [24a], [26], [38d], [39b], [48b], [49], [54], [64ab].
 
16
In [49m] cardinals satisfying “m = 2 ⋅ m” were introduced on an abstract level as “idem-multiple” (a + a = a) elements of a cardinal algebra.
 
17
Adolf Lindenbaum first posed it as an open question. In 1925 Lindenbaum and Tarski jointly proved it, and asserted it without proof in [26a], §1, page 314, theorem 94.
 
18
See [39b].
 
19
See [48b].
 
20
See [54af], [54ag], [54ah].
 
21
See [24c]. The reader should bear in mind that “minimal element” and “least element” are different concepts. Notice that this definition is independent of the notion of a finite natural number.
 
22
See [38c], page 163.
 
23
A set is said to be Dedekind-finite, or D-finite, iff there is no bijection of the set onto a proper subset of itself (or equivalently, iff every one-to-one mapping of the set into itself is surjective.) A cardinal number is said to be a Dedekind-finite cardinal, or a D-finite cardinal, iff it is the cardinality of a D-finite set. In weak set theory—without the Axiom of Choice—it can be proved that if a set is finite by Tarski’s definition then it is also D-finite, but it cannot be proved that if a set is D-finite then it is also finite by Tarski’s definition.
In [49m] D-finite cardinals were introduced on an abstract level as finite elements of a cardinal algebra.
 
24
See the joint paper with Wacław Sierpinski [30a].
 
25
See [38a] and [39b].
 
26
See [62]; the joint papers [43] and [61b] with Paul Erdös; and the joint paper [64] with H. Jerome Keisler.
 
27
A. Lévy, Alfred Tarski’s Work in Set Theory, The Journal of Symbolic Logic, vol. 53 (1988), pp. 2–6; p. 2.
 
28
See [34], [56c], the joint paper [56b] with E.W. Beth, and the joint papers [65a] and [79] with L.W. Szczerba.
 
29
The Banach–Tarski Paradox was fully articulated, and its proof elaborated, in [24d], a subsequent paper co-authored with Banach.
 
30
Tarski’s circle-squaring problem was finally answered in the affirmative in 1990 by Miklós Laczkovich. See: M. Laczkovich, Equidecomposability and Discrepancy: a Solution to Tarski’s Circle-squaring Problem, Journal für die Reine und Angewandte Mathematik, vol. 404 (1990), pp. 77–117. Laczkovich proved that the circle could be decomposed into no more than 1050 different pieces, which could be rearranged to compose a square of equal area. He needed the Axiom of Choice to obtain his decomposition, which was highly non-constructive.
 
31
J. Mycielski, Review of The Banach–Tarski Paradox by Stan Wagon, The American Mathematical Monthly, vol. 94, no. 7, pp. 698–700. The quoted passages are from page 698.
 
32
Though published 6 years apart, [39] and [45] were nominally parts I and II of the same two-part paper, and appeared in consecutive issues of Fundamenta Mathematicae, vol. 32, pp. 45–63, and vol. 33, pp. 51–65. The journal’s operations were interrupted by the Second World War.
 
33
Undecidable Theories by Alfred Tarski, in collaboration with Andrzej Mostowski and Raphael M. Robinson. North-Holland Publishing Co., Amsterdam, 1953. The quoted paragraph is from Chapter I, A General Method in Proofs of Undecidability, §I.1. Introduction, page 3.
 
34
See H. Sinaceur (ed., with introduction), Address at the Princeton University Bicentennial Conference on Problems of Mathematics, December 17–19, 1946, by Alfred Tarski, The Bulletin of Symbolic Logic, vol. 6 (2000), pp. 1–44. See also Odczyt Alfreda Tarskiego na Konferencji o Problemach Matematyki w Princeton, 17 grudnia 1946, in [01m], pp. 396–413.
 
35
For more comments on this see Tarski [48m], note 10.
 
36
See: L. Löwenheim, Über Möglichkeiten im Relativkalkül <On Possibilities in the Calculus of Relatives>, Mathematische Annalen, vol. 76 (1915), pp. 447–470.
 
37
The four paragraphs in the box are an extended quote from: John Doner and Wilfrid Hodges, Alfred Tarski and Decidable Theories, The Journal of Symbolic Logic, Vol. 53, No. 1, (March, 1988), pp. 20–35. The text reproduced here is from page 24 of their article, where they present it in three paragraphs, not four.
 
38
See: C.C. Chang and H.J. Keisler, Model Theory, North-Holland: Amsterdam 1973 (3rd edition, 1990), pages 49–60. This quotation is from page 49 in the 3rd edition.
 
39
See: M. Presburger, Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Sprawozdanie z I Kongresu Matematików Krajów Słowiańskich , Warszawa 1929 (=Comptes-rendus du I Congrès des Mathématiciens des Pays Slaves), Księżnica Atlas: Warszawa 1930, pp. 92–101 & p. 395; see p. 97, footnote 1.
See also: W. Hodges, A Visit to Tarskis Seminar on Elimination of Quantifiers, in J. van Benthem et al. (eds.), Proof, Computation and Agency, Synthese Library 352, Springer Science+Business Media B.V. 2011; pp. 53–66.
 
40
In [36d], §5, Tarski axiomatized these two theories, calling them, respectively, “die elementare Theorie der dichten Anordnung” (p. 290), and “die elementare Theorie der isolierten Anordnung” (p. 294). In footnote 1 on page 293 he asserted that his results on the theory of dense order supplemented those reported in Langford’s 1927 paper. (Literally: “Die unten angegebenen Tatsachen, die diese Theorie betreffen, bilden die Ergänzung der Ergebnisse Langfords”). He used the phrase “sukzessiven Elimination der Operatoren” (successive elimination of quantifiers) in print for the first time on pp. 293 and 295… somewhat odd considering he had been promoting the method since 1926 or earlier.
 
41
By “a theory of an order type α” is meant, the set of all first-order sentences true in any structure <X,R>, where the relation R orders the set X according to the type α.
 
42
See [78]. Precise attribution of specific results is a long and complicated story. See especially the historical comments on page 1.
 
43
These results were announced in a variety of published works, scattered over time, and in varying notations and terminologies. See: [31], [48m], [48m](1), [49ad], and [67m]. The last was originally intended for publication in 1939 but was interrupted by the Second World War.
 
44
Tarski was perfectly right that difficulties resided in mathematics, and this has been confirmed by the further development of algebraic geometry. The importance of the two problems is discussed in: D.E. Marker, Model Theory and Exponentiation, Notices of the American Mathematical Society, vol. 43 (1996), pp. 753–759.
Tarski’s theorem that the ordered field of real numbers (a first-order theory) admits quantifier elimination triggered a stream of research. Important contributions were made by: Abraham Seidenberg (1954), Abraham Robinson (1959 and 1971), Stanisław Łojasiewicz (1964–65), Paul Joseph Cohen (1969), Joseph R. Shoenfield (1971), George Edwin Collins (1982), and Helmut Wolter (1986). They are summarized in an expert presentation by Lou van den Dries: Alfred Tarski’s Elimination Theory for Real Closed Fields, The Journal of Symbolic Logic, vol. 53 (1988), pp. 7–19.
A comprehensive review by Charles I. Steinhorn of Alex J. Wilkie’s paper Model Completeness Results for Expansions of the Ordered Field of Real Numbers in The Journal of Symbolic Logic, vol. 64 (1999), pp. 910–913, contains a survey of research up to the end of the 1990s stimulated by Tarski’s beautiful, influential, and far-reaching monograph [48m], A Decision Method for Elementary Algebra and Geometry. See also Bob F. Caviness and Jeremy Russell Johnson (eds.), Quantifier Elimination and Cylindrical Algebraic Decomposition. Wien, New York: Springer 1998.
 
45
See [44a], p. 359.
 
46
Tarski’s use of the word “essentially” here came from a distinction he drew between two different ways of extending a theory. An extension \( {\mathsf{T}}_2 \) of \( {\mathsf{T}}_1 \) was called in essential, if every constant of \( {\mathsf{T}}_2 \) which did not occur in \( {\mathsf{T}}_1 \) was an individual constant, and every valid sentence of \( {\mathsf{T}}_2 \) was derivable from a set of valid sentences of \( {\mathsf{T}}_1 \).
 
47
By the work of Church and Rosser from the year 1936, elementary Peano arithmetic is essentially undecidable.
 
48
The general idea of relativization was introduced by Tarski in 1930. The idea of relativization of quantifiers was due to Adolf Lindenbaum and Tarski, and dated from 1935. See [56m], p. 69, p. 314 (footnote 1) and p. 396. With Tarski as one of his doctoral advisors, Andrzej Mostowski used the method of relativization of quantifiers in his Ph.D. dissertation, which he published under the title O niezależności definicji skończoności w systemie logiki <On the Independence of Definitions of Finiteness in a System of Logic>, in Dodatek do Rocznika Polskiego Towarzystwa Matematycznego (Supplement to the Annales de la Société Polonaise de Mathématique), Vol. 11 (1938), pp. 1–54.
 
49
Both terms were coined in [53m] (see pp. 34–35).
 
50
See [53m], p. 35, and [68], p. 287.
 
51
To obtain these proofs he applied a method that he had earlier set out, in [53m], p. 22, footnote 17, which could be termed “generalized interpretation”.
 
52
For a class K of similar algebras (of a fixed similarity type τ), the equational theory of this class is defined as the set of all identities (in type τ) which are true or hold in every algebra belonging to the class K.
 
53
In equational logic finitely based means axiomatizable by a finite number of equations (identities).
 
54
That such a procedure does not exist was communicated in 1949 by Samuel Linial (Gulden) and Emil Leon Post. For a detailed presentation of their result, see Mary Katherine Yntema, A detailed argument for the Post-Linial theorems, Notre Dame Journal of Formal Logic, vol. 5 (1964), pp. 37–51.
 
55
See: George F. McNulty, Alfred Tarski and Undecidable Theories, The Journal of Symbolic Logic, vol. 51 (1986), pp. 890–898.
 
56
A. Fraenkel, Y. Bar-Hillel, A. Lévy, Foundations of Set Theory, Studies in Logic and the Foundations of Mathematics, Vol. 67, Elsevier, Amsterdam 1958, (2nd edition 1973). The quotation is from the second edition, Chapter 5, §7, The limitative theorems of Gödel, Tarski, Church and their generalizations, page 320.
 
57
R. McKenzie, Tarski’s Finite Basis Problem is Undecidable, International Journal of Algebra and Computation, Vol. 6 (1996), pp. 49–104.
 
58
See [68], p. 288.
 
59
See [56m], p. 59.
 
60
See [87m], pp. 167–168.
 
Metadaten
Titel
Alfred Tarski: Auxiliary Notes on His Legacy
verfasst von
Jan Zygmunt
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-65430-0_31