Alfred Tarski
Encyclopedia
Alfred Tarski was a Polish
logic
ian and mathematician
. Educated at the University of Warsaw
and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics
and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of California, Berkeley
, from 1942 until his death.
A prolific author best known for his work on model theory
, metamathematics
, and algebraic logic
, he also contributed to abstract algebra
, topology
, geometry
, measure theory, mathematical logic
, set theory
, and analytic philosophy
.
His biographers Anita and Solomon Feferman
state 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."
spelling: "Tajtelbaum"), to parents who were Polish Jews
in comfortable circumstances. He first manifested his mathematical abilities while in secondary school, at Warsaw's Szkoła Mazowiecka. Nevertheless, he entered the University of Warsaw
in 1918 intending to study biology
.
After Poland regained independence in 1918, Warsaw University came under the leadership of Jan Łukasiewicz, Stanisław Leśniewski and Wacław Sierpiński and quickly became a world leading research institution in logic, foundational mathematics, and the philosophy of mathematics. Leśniewski recognized Tarski's potential as a mathematician and persuaded him to abandon biology. 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. However, in later life, Tarski reserved his warmest praise for Kotarbiński
, as was mutual.
In 1923, Alfred Teitelbaum and his brother Wacław changed their surname to "Tarski", a name they invented because it sounded more 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
. Tarski was a Polish nationalist who saw himself as a Pole and wished to be fully accepted as such. (Later, in America, he spoke Polish at home.)
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. In 1929 Tarski married a fellow teacher Maria Witkowska, a Pole of Catholic ancestry. She had worked as a courier for the army during Poland's fight for independence. They had two children, a son Jan who became a physicist, and a daughter Ina who married the mathematician Andrzej Ehrenfeucht
.
Tarski applied for a chair of philosophy at Lwów University, but on Bertrand Russell
's recommendation it was awarded to Leon Chwistek
. In 1930, Tarski visited the University of Vienna
, lectured to Karl Menger
's colloquium, and met Kurt Gödel
. Thanks to a fellowship, he 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
. In 1937, Tarski applied for a chair at Poznań University but the chair was abolished. Tarski's ties to the Unity of Science 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 German occupying authorities.
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
in Princeton
(1942), where he again met Gödel. In 1942, Tarski joined the Mathematics Department at the University of California, Berkeley
, where he spent the rest of his career. Tarski became an American citizen in 1945. 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, a fact noted by many observers:
Indeed, Tarski supervised twenty-four Ph.D. dissertations including (in chronological order) those of Andrzej Mostowski
, Bjarni Jónsson
, Julia Robinson
, Robert Vaught, Solomon Feferman
, Richard Montague
, James Donald Monk, Haim Gaifman, Donald Pigozzi and Roger Maddux
, as well as Chen Chung Chang
and Jerome Keisler, authors of Model Theory (1973), a classic text in the field. He also strongly influenced the dissertations of Alfred Lindenbaum, Dana Scott
, and Steven Givant. Five of Tarski's students were women, a remarkable fact given that men represented an overwhelming majority of graduate students at the time.
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). Among many distinctions garnered over the course of his career, Tarski was elected to the United States National Academy of Sciences
, the British Academy
and the Royal Netherlands Academy of Arts and Sciences
, received honorary degree
s from the Pontifical Catholic University of Chile in 1975, from Marseilles' Paul Cézanne University in 1977 and from the University of Calgary
, as well as the Berkeley Citation in 1981. Tarski presided over the Association for Symbolic Logic
, 1944–46, and the International Union for the History and Philosophy of Science, 1956-57. He was also an honorary editor of Algebra Universalis
.
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, if one accepts the Axiom of Choice, a ball
can be cut into a finite number of pieces, and then reassembled into a ball of larger size, or alternatively it can be reassembled into two balls 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 number
s under addition and multiplication is decidable
. (While this result appeared only in 1948, it dates back to 1930 and was mentioned in Tarski (1931).) This is a very curious result, because Alonzo Church
proved in 1936 that Peano arithmetic (the theory of natural number
s) 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 group
s is decidable, but that of non-Abelian groups is not.
In the 1920s and 30s, Tarski often taught high school geometry
. Using some ideas of Mario Pieri
, in 1926 Tarski devised an original axiomatization for plane Euclidean geometry
, one considerably more concise than Hilbert's
. Tarski's axioms
form a first-order theory devoid of set theory, whose individuals are point
s, 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.
In 1929 he showed that much of Euclidean 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 than Lesniewski's variant. 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 number
s. Ordinal Algebras sets out an algebra for the additive theory of order type
s. Cardinal, but not ordinal, addition commutes.
In 1941, Tarski published an important paper on binary relation
s, 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 algebra
s, 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).
Tarski produced axioms for logical consequence, and worked on deductive system
s, 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.
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 undefinability theorem, and mulled over their consequences for the axiomatic method in mathematics.
, 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 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:
(where p is the proposition expressed by "p")
The debate amounts to whether to read sentences of this form, such as
as expressing merely a deflationary theory of truth
or as embodying truth
as a more substantial property (see Kirkham 1992). Though it is important to realize that Tarski's theory of truth is for formalized languages so giving examples in natural language has no validity according to Tarski's theory of truth.
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
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".
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 Portuguese mathematician Sebastiao e 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 (automorphism
s) 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:
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 homomorphism
s. 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.
Original publications of Tarski:
Poles
thumb|right|180px|The state flag of [[Poland]] as used by Polish government and diplomatic authoritiesThe Polish people, or Poles , are a nation indigenous to Poland. They are united by the Polish language, which belongs to the historical Lechitic subgroup of West Slavic languages of Central Europe...
logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
ian and mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
. Educated at the University of Warsaw
University of Warsaw
The University of Warsaw is the largest university in Poland and one of the most prestigious, ranked as best Polish university in 2010 and 2011...
and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics
Warsaw School of Mathematics
"Warsaw School of Mathematics" is the name given to a group of mathematicians who worked at Warsaw, Poland, in the two decades between the World Wars, especially in the fields of logic, set theory, point-set topology and real analysis. They published in the journal Fundamenta Mathematicae, founded...
and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, from 1942 until his death.
A prolific author best known for his work on model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
, metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
, and algebraic logic
Algebraic logic
In mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
, he also contributed to abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, measure theory, mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, and analytic philosophy
Analytic philosophy
Analytic philosophy is a generic term for a style of philosophy that came to dominate English-speaking countries in the 20th century...
.
His biographers Anita and Solomon Feferman
Solomon Feferman
Solomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
state 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
Truth
Truth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...
and the theory of models."
Life
Alfred Tarski was born Alfred Teitelbaum (PolishPolish language
Polish is a language of the Lechitic subgroup of West Slavic languages, used throughout Poland and by Polish minorities in other countries...
spelling: "Tajtelbaum"), to parents who were Polish Jews
Ashkenazi Jews
Ashkenazi Jews, also known as Ashkenazic Jews or Ashkenazim , are the Jews descended from the medieval Jewish communities along the Rhine in Germany from Alsace in the south to the Rhineland in the north. Ashkenaz is the medieval Hebrew name for this region and thus for Germany...
in comfortable circumstances. He first manifested his mathematical abilities while in secondary school, at Warsaw's Szkoła Mazowiecka. Nevertheless, he entered the University of Warsaw
University of Warsaw
The University of Warsaw is the largest university in Poland and one of the most prestigious, ranked as best Polish university in 2010 and 2011...
in 1918 intending to study biology
Biology
Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...
.
After Poland regained independence in 1918, Warsaw University came under the leadership of Jan Łukasiewicz, Stanisław Leśniewski and Wacław Sierpiński and quickly became a world leading research institution in logic, foundational mathematics, and the philosophy of mathematics. Leśniewski recognized Tarski's potential as a mathematician and persuaded him to abandon biology. Henceforth Tarski attended courses taught by Łukasiewicz, Sierpiński, Stefan Mazurkiewicz
Stefan Mazurkiewicz
Stefan Mazurkiewicz was a Polish mathematician who worked in mathematical analysis, topology, and probability. He was a student of Wacław Sierpiński and a member of the Polish Academy of Learning...
and Tadeusz Kotarbiński
Tadeusz Kotarbinski
Tadeusz Kotarbiński , a pupil of Kazimierz Twardowski, was a Polish philosopher, logician, one of the most representative figures of the Lwów-Warsaw School, and a member of the Polish Academy of Learning as well as the Polish Academy of Sciences...
, 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. However, in later life, Tarski reserved his warmest praise for Kotarbiński
Tadeusz Kotarbinski
Tadeusz Kotarbiński , a pupil of Kazimierz Twardowski, was a Polish philosopher, logician, one of the most representative figures of the Lwów-Warsaw School, and a member of the Polish Academy of Learning as well as the Polish Academy of Sciences...
, as was mutual.
In 1923, Alfred Teitelbaum and his brother Wacław changed their surname to "Tarski", a name they invented because it sounded more 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
Atheism
Atheism is, in a broad sense, the rejection of belief in the existence of deities. In a narrower sense, atheism is specifically the position that there are no deities...
. Tarski was a Polish nationalist who saw himself as a Pole and wished to be fully accepted as such. (Later, in America, he spoke Polish at home.)
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. In 1929 Tarski married a fellow teacher Maria Witkowska, a Pole of Catholic ancestry. She had worked as a courier for the army during Poland's fight for independence. They had two children, a son Jan who became a physicist, and a daughter Ina who married the mathematician Andrzej Ehrenfeucht
Andrzej Ehrenfeucht
Andrzej Ehrenfeucht is a Polish American mathematician and computer scientist. He formulated the Ehrenfeucht–Fraïssé game, using the back-and-forth method given by Roland Fraïssé in his thesis. The Ehrenfeucht–Mycielski sequence is also named after him....
.
Tarski applied for a chair of philosophy at Lwów University, but on Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
's recommendation it was awarded to Leon Chwistek
Leon Chwistek
Leon Chwistek was a Polish avant-garde painter, theoretician of modern art, literary critic, logician, philosopher and mathematician.-Logic and philosophy:...
. In 1930, Tarski visited the University of Vienna
University of Vienna
The University of Vienna is a public university located in Vienna, Austria. It was founded by Duke Rudolph IV in 1365 and is the oldest university in the German-speaking world...
, lectured to Karl Menger
Karl Menger
Karl Menger was a mathematician. He was the son of the famous economist Carl Menger. He is credited with Menger's theorem. He worked on mathematics of algebras, algebra of geometries, curve and dimension theory, etc...
's colloquium, and met Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
. Thanks to a fellowship, he 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
Unity of science
The unity of science is a thesis in philosophy of science that says that all the sciences form a unified whole.Even though, for example, physics and politics are distinct disciplines, the thesis of the unity of science says that in principle they must be part of a unified intellectual endeavor,...
movement, an outgrowth of the Vienna Circle
Vienna Circle
The Vienna Circle was an association of philosophers gathered around the University of Vienna in 1922, chaired by Moritz Schlick, also known as the Ernst Mach Society in honour of Ernst Mach...
. In 1937, Tarski applied for a chair at Poznań University but the chair was abolished. Tarski's ties to the Unity of Science 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
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
. 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
Invasion of Poland (1939)
The Invasion of Poland, also known as the September Campaign or 1939 Defensive War in Poland and the Poland Campaign in Germany, was an invasion of Poland by Germany, the Soviet Union, and a small Slovak contingent that marked the start of World War II in Europe...
and the outbreak of World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
. 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 German occupying authorities.
Once in the United States, Tarski held a number of temporary teaching and research positions: Harvard University (1939), City College of New York
City College of New York
The City College of the City University of New York is a senior college of the City University of New York , in New York City. It is also the oldest of the City University's twenty-three institutions of higher learning...
(1940), and thanks to a Guggenheim Fellowship
Guggenheim Fellowship
Guggenheim Fellowships are American grants that have been awarded annually since 1925 by the John Simon Guggenheim Memorial Foundation to those "who have demonstrated exceptional capacity for productive scholarship or exceptional creative ability in the arts." Each year, the foundation makes...
, the Institute for Advanced Study
Institute for Advanced Study
The Institute for Advanced Study, located in Princeton, New Jersey, United States, is an independent postgraduate center for theoretical research and intellectual inquiry. It was founded in 1930 by Abraham Flexner...
in Princeton
Princeton, New Jersey
Princeton is a community located in Mercer County, New Jersey, United States. It is best known as the location of Princeton University, which has been sited in the community since 1756...
(1942), where he again met Gödel. In 1942, Tarski joined the Mathematics Department at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, where he spent the rest of his career. Tarski became an American citizen in 1945. 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, a fact noted by many observers:
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.
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.
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.
Indeed, Tarski supervised twenty-four Ph.D. dissertations including (in chronological order) those of Andrzej Mostowski
Andrzej Mostowski
Andrzej Mostowski was a Polish mathematician. He is perhaps best remembered for the Mostowski collapse lemma....
, Bjarni Jónsson
Bjarni Jónsson
Bjarni Jónsson is an Icelandic mathematician and logician working in universal algebra and lattice theory. He is emeritus Distinguished Professor of Mathematics at Vanderbilt University and the honorary editor in chief of Algebra Universalis...
, Julia Robinson
Julia Robinson
Julia Hall Bowman Robinson was an American mathematician best known for her work on decision problems and Hilbert's Tenth Problem.-Background and education:...
, Robert Vaught, Solomon Feferman
Solomon Feferman
Solomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
, Richard Montague
Richard Montague
Richard Merett Montague was an American mathematician and philosopher.-Career:At the University of California, Berkeley, Montague earned an B.A. in Philosophy in 1950, an M.A. in Mathematics in 1953, and a Ph.D. in Philosophy 1957, the latter under the direction of the mathematician and logician...
, James Donald Monk, Haim Gaifman, Donald Pigozzi and Roger Maddux
Roger Maddux
Roger Maddux is an American mathematician specializing in algebraic logic.He completed his B.A. at Pomona College in 1969, and his Ph.D. in mathematics at the University of California in 1978, where he was one of Alfred Tarski's last students...
, as well as Chen Chung Chang
Chen Chung Chang
Chen Chung Chang is a mathematician who works in model theory. He obtained his PhD from Berkeley in 1955 on "Cardinal and Ordinal Factorization of Relation Types" under Alfred Tarski. He wrote the standard text on model theory. Chang's conjecture is named after him...
and Jerome Keisler, authors of Model Theory (1973), a classic text in the field. He also strongly influenced the dissertations of Alfred Lindenbaum, Dana Scott
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
, and Steven Givant. Five of Tarski's students were women, a remarkable fact given that men represented an overwhelming majority of graduate students at the time.
Tarski lectured at University College, London (1950, 1966), the Institut Henri Poincaré
Institut Henri Poincaré
The Institut Henri Poincaré is a mathematical institute in Paris which has established itself over its eighty year history as an important meeting place for French and international mathematicians and theoretical physicists...
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
Pontifical Catholic University of Chile
The Pontifical Catholic University of Chile is one of the six Catholic Universities existing in the Chilean university system and one of the two Pontifical Universities in the country, along with the Pontifical Catholic University of Valparaíso. It is also one of Chile's oldest universities and...
(1974–75). Among many distinctions garnered over the course of his career, Tarski was elected to the United States National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
, the British Academy
British Academy
The British Academy is the United Kingdom's national body for the humanities and the social sciences. Its purpose is to inspire, recognise and support excellence in the humanities and social sciences, throughout the UK and internationally, and to champion their role and value.It receives an annual...
and the Royal Netherlands Academy of Arts and Sciences
Royal Netherlands Academy of Arts and Sciences
The Royal Netherlands Academy of Arts and Sciences is an organisation dedicated to the advancement of science and literature in the Netherlands...
, received honorary degree
Honorary degree
An honorary degree or a degree honoris causa is an academic degree for which a university has waived the usual requirements, such as matriculation, residence, study, and the passing of examinations...
s from the Pontifical Catholic University of Chile in 1975, from Marseilles' Paul Cézanne University in 1977 and from the University of Calgary
University of Calgary
The University of Calgary is a public research university located in Calgary, Alberta, Canada. Founded in 1966 the U of C is composed of 14 faculties and more than 85 research institutes and centres.More than 25,000 undergraduate and 5,500 graduate students are currently...
, as well as the Berkeley Citation in 1981. Tarski presided over the Association for Symbolic Logic
Association for Symbolic Logic
The Association for Symbolic Logic is an international organization of specialists in mathematical logic and philosophical logic—the largest such organization in the world. The ASL was founded in 1936, a crucial year in the development of modern logic, and its first president was Alonzo Church...
, 1944–46, and the International Union for the History and Philosophy of Science, 1956-57. He was also an honorary editor of Algebra Universalis
Algebra Universalis
Algebra Universalis ) is an international scientific journal focused on universal algebra and lattice theory. The journal, founded in 1971, is currently published by Springer-Verlag. Honorary editors in chief of the journal include Alfred Tarski and Bjarni Jónsson.- External links :*...
.
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.Tarski's first paper, published when he was 19 years old, was on set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, a subject to which he returned throughout his life. In 1924, he and Stefan Banach
Stefan Banach
Stefan Banach was a Polish mathematician who worked in interwar Poland and in Soviet Ukraine. He is generally considered to have been one of the 20th century's most important and influential mathematicians....
proved that, if one accepts the Axiom of Choice, a ball
Ball (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
can be cut into a finite number of pieces, and then reassembled into a ball of larger size, or alternatively it can be reassembled into two balls whose sizes each equal that of the original one. This result is now called the Banach–Tarski paradox
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theoretic geometry which states the following: Given a solid ball in 3-dimensional space, there exists a decomposition of the ball into a finite number of non-overlapping pieces , which can then be put back together in a different way to yield two...
.
In A decision method for elementary algebra and geometry, Tarski showed, by the method of quantifier elimination
Quantifier elimination
Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. One way of classifying formulas is by the amount of quantification...
, that the first-order theory of the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s under addition and multiplication is decidable
Decidability (logic)
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
. (While this result appeared only in 1948, it dates back to 1930 and was mentioned in Tarski (1931).) This is a very curious result, because Alonzo Church
Alonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
proved in 1936 that Peano arithmetic (the theory of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s) 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
Projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant under projective transformations. This means that, compared to elementary geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts...
, and closure algebras, are all undecidable. The theory of Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
s is decidable, but that of non-Abelian groups is not.
In the 1920s and 30s, Tarski often taught high school geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
. Using some ideas of Mario Pieri
Mario Pieri
Mario Pieri was an Italian mathematician who is known for his work on foundations of geometry.Pieri was born in Lucca, Italy, the son of Pellegrino Pieri and Ermina Luporini. Pellegrino was a lawyer. Pieri began his higher education at University of Bologna where he drew the attention of Salvatore...
, in 1926 Tarski devised an original axiomatization for plane Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
, one considerably more concise than Hilbert's
Hilbert's axioms
Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
. Tarski's axioms
Tarski's axioms
Tarski's axioms, due to Alfred Tarski, are an axiom set for the substantial fragment of Euclidean geometry, called "elementary," that is formulable in first-order logic with identity, and requiring no set theory . Other modern axiomizations of Euclidean geometry are those by Hilbert and George...
form a first-order theory devoid of set theory, whose individuals are point
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
s, 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.
In 1929 he showed that much of Euclidean solid geometry
Solid geometry
In mathematics, solid geometry was the traditional name for the geometry of three-dimensional Euclidean space — for practical purposes the kind of space we live in. It was developed following the development of plane geometry...
could be recast as a first-order theory whose individuals are spheres (a primitive notion
Primitive notion
In mathematics, logic, and formal systems, a primitive notion is an undefined concept. In particular, a primitive notion is not defined in terms of previously defined concepts, but is only motivated informally, usually by an appeal to intuition and everyday experience. In an axiomatic theory or...
), 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
Mereology
In philosophy and mathematical logic, mereology treats parts and the wholes they form...
far easier to exposit than Lesniewski's variant. 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 number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
s. Ordinal Algebras sets out an algebra for the additive theory of order type
Order type
In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone...
s. Cardinal, but not ordinal, addition commutes.
In 1941, Tarski published an important paper on binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s, which began the work on relation algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
and its metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
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
Roger Lyndon
Roger Conant Lyndon was an American mathematician, for many years a professor at the University of Michigan. He is known for Lyndon words, the Curtis–Hedlund–Lyndon theorem, Craig–Lyndon interpolation and the Lyndon–Hochschild–Serre spectral sequence.-Biography:Lyndon was born on December 18, 1917...
) 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
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
, see Maddux (2006). In the late 1940s, Tarski and his students devised cylindric algebra
Cylindric algebra
The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Indeed, cylindric algebras are Boolean algebras equipped with additional...
s, which are to first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate 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
Tarski's student, Vaught, has ranked Tarski as one of the four greatest logicians of all time --- along with Aristotle, Gottlob Frege, and Kurt Gödel. However, Tarski often expressed great admiration for Charles Sanders Peirce, particularly for his pioneering work in the logic of relations.Tarski produced axioms for logical consequence, and worked on deductive system
Deductive system
A deductive system consists of the axioms and rules of inference that can be used to derive the theorems of the system....
s, 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."
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
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
and Tarski's undefinability 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 1935 German translation was titled "Der Wahrheitsbegriff in den formalisierten Sprachen", (The concept of truth in formalized languages), 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 philosophyAnalytic philosophy
Analytic philosophy is a generic term for a style of philosophy that came to dominate English-speaking countries in the 20th century...
, an important contribution to symbolic logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
, and the philosophy of language
Philosophy of language
Philosophy of language is the reasoned inquiry into the nature, origins, and usage of language. As a topic, the philosophy of language for analytic philosophers is concerned with four central problems: the nature of meaning, language use, language cognition, and the relationship between language...
. For a brief discussion of its content, see Truth
Truth
Truth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...
for a brief description of the "Convention T" (see also T-schema
T-schema
The T-schema or truth schema is used to give an inductive definition of truth which lies at the heart of any realisation of Alfred Tarski's semantic theory of truth...
) 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
Correspondence theory of truth
The correspondence theory of truth states that the truth or falsity of a statement is determined only by how it relates to the world, and whether it accurately describes that world...
. 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 ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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
Deflationary theory of truth
A deflationary theory of truth is one of a family of theories which all have in common the claim that assertions that predicate truth of a statement do not attribute a property called truth to such a statement.-Redundancy theory:...
or as embodying truth
Truth
Truth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...
as a more substantial property (see Kirkham 1992). Though it is important to realize that Tarski's theory of truth is for formalized languages so giving examples in natural language has no validity according to Tarski's theory of truth.
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
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
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
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
). This question is a matter of some debate in the current philosophical literature. John Etchemendy
John Etchemendy
John W. Etchemendy and of Basque descent is Stanford University's twelfth and current Provost. He succeeded John L. Hennessy to the post on September 1, 2000....
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
Felix Klein
Christian Felix Klein was a German mathematician, known for his work in group theory, function theory, non-Euclidean geometry, and on the connections between geometry and group theory...
. (Mautner 1946, and possibly an article by the Portuguese mathematician Sebastiao e Silva, anticipated Tarski in applying the Erlangen Program to logic.)
That program classified the various types of geometry (Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
, affine geometry
Affine geometry
In mathematics affine geometry is the study of geometric properties which remain unchanged by affine transformations, i.e. non-singular linear transformations and translations...
, topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, 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
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
from an annulus
Annulus (mathematics)
In mathematics, an annulus is a ring-shaped geometric figure, or more generally, a term used to name a ring-shaped object. Or, it is the area between two concentric circles...
(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 (automorphism
Automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism...
s) 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:
- 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.)
- Individuals: No individuals, provided the domain has at least two members.
- Predicates:
- the one-place total and null predicates, the former having all members of the domain in its extension and the latter having no members of the domain in its extension
- two-place total and null predicates, the former having the set of all ordered pairs of domain members as its extension and the latter with the empty set as extension
- the two-place identity predicate, with the set of all order-pairs <a,a> in its extension, where a is a member of the domain
- the two-place diversity predicate, with the set of all order pairs <a,b> where a and b are distinct members of the domain
- n-ary predicates in general: all predicates definable from the identity predicate together with conjunctionLogical conjunctionIn logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
, disjunction and negationNegationIn logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
(up to any ordinality, finite or infinite)
- 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."
- Set-Theoretic relations: Relations such as inclusion, intersectionIntersection (set theory)In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
and unionUnion (set theory)In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
applied to subsetSubsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of the domain are logical in the present sense. - 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 theoryType theoryIn mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
, but is extralogical if set theory is set out axiomatically, as in the canonical Zermelo-Fraenkel set theory. - 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
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
's Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
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 homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
s. 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.
See also
- History of philosophy in Poland
- List of Poles
- List of topics named after Alfred Tarski
- Lwów–Warsaw School of LogicLwów–Warsaw School of LogicThe Lwów–Warsaw School of Logic was headed by Kazimierz Twardowski, who had been a student of Franz Brentano and is regarded as the "father of Polish logic."-History:...
- T-schemaT-schemaThe T-schema or truth schema is used to give an inductive definition of truth which lies at the heart of any realisation of Alfred Tarski's semantic theory of truth...
- Warsaw School of MathematicsWarsaw School of Mathematics"Warsaw School of Mathematics" is the name given to a group of mathematicians who worked at Warsaw, Poland, in the two decades between the World Wars, especially in the fields of logic, set theory, point-set topology and real analysis. They published in the journal Fundamenta Mathematicae, founded...
Works of Tarski
Anthologies and collections- 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.
- 1983 (1956). Logic, Semantics, Metamathematics: Papers from 1923 to 1938 by Alfred Tarski, Corcoran, J., ed. Hackett. 1st edition edited and translated by J. H. Woodger, Oxford Uni. Press. This collection contains translations from Polish of some of Tarski's most important papers of his early career, including The Concept of Truth in Formalized Languages and On the Concept of Logical Consequence discussed above.
Original publications of Tarski:
- 1930 Une contribution a la theorie de la mesure. Fund Math 15 (1930), 42-50.
- 1930. (with Jan Łukasiewicz). "Untersuchungen uber den Aussagenkalkul" ["Investigations into the Sentential Calculus"], Comptes Rendus des seances de la Societe des Sciences et des Lettres de Varsovie, Vol, 23 (1930) Cl. III, pp. 31–32
- 1931. "Sur les ensembles définissables de nombres réels I", Fundamenta Mathematica 17: 210-239.
- 1936. "Grundlegung der wissenschaftlichen Semantik", Actes du Congrès international de philosophie scientifique, Sorbonne, Paris 1935, vol. III, Language et pseudo-problèmes, Paris, Hermann, 1936, pp. 1–8.
- 1936. "Über den Begriff der logischen Folgerung", Actes du Congrès international de philosophie scientifique, Sorbonne, Paris 1935, vol. VII, Logique, Paris: Hermann, pp. 1–11.
- 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 Raphael 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 HenkinLeon HenkinLeon Albert Henkin was a logician at the University of California, Berkeley. He was principally known for the "Henkin's completeness proof": his version of the proof of the semantic completeness of standard systems of first-order logic.-The completeness proof:Henkin's result was not novel; it had...
and Donald Monk). Cylindric Algebras: Part I. North-Holland. - 1985 (with Leon HenkinLeon HenkinLeon Albert Henkin was a logician at the University of California, Berkeley. He was principally known for the "Henkin's completeness proof": his version of the proof of the semantic completeness of standard systems of first-order logic.-The completeness proof:Henkin's result was not novel; it had...
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 references
- Givant, Steven, 1991. "A portrait of Alfred Tarski", Mathematical Intelligencer 13: 16-32.
Logic literature
- The December 1986 issue of the Journal of Symbolic Logic surveys Tarski's work on model theoryModel theoryIn mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
(Robert Vaught), algebraAbstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
(Jonsson), undecidable theoriesDecidability (logic)In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
(McNulty), algebraic logicAlgebraic logicIn mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
(Donald Monk), and geometryGeometryGeometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
(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 theoryDecidability (logic)In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
(Doner and Wilfrid HodgesWilfrid HodgesWilfrid Augustine Hodges is a British mathematician, known for his work in model theory. He was Professor of Mathematics at Queen Mary, University of London from 1987 to 2006, and is the author of numerous books on logic....
), metamathematicsMetamathematicsMetamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
(Blok and Pigozzi), truthTruthTruth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...
and logical consequence (John EtchemendyJohn EtchemendyJohn W. Etchemendy and of Basque descent is Stanford University's twelfth and current Provost. He succeeded John L. Hennessy to the post on September 1, 2000....
), and general philosophyPhilosophyPhilosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
(Patrick Suppes).- Blok, W. J.; Pigozzi, Don, "Alfred Tarski's Work on General Metamathematics", The Journal of Symbolic Logic, Vol. 53, No. 1 (Mar., 1988), pp. 36–50
- Ivor Grattan-GuinnessIvor Grattan-GuinnessIvor Grattan-Guinness, born 23 June 1941, in Bakewell, in England, is a historian of mathematics and logic.He gained his Bachelor degree as a Mathematics Scholar at Wadham College, Oxford, got an M.Sc in Mathematical Logic and the Philosophy of Science at the London School of Economics in 1966...
, 2000. The Search for Mathematical Roots 1870-1940. Princeton Uni. Press. - Kirkham, Richard, 1992. Theories of Truth. MIT Press.
- Karl R. PopperKarl PopperSir Karl Raimund Popper, CH FRS FBA was an Austro-British philosopher and a professor at the London School of Economics...
, 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.
- 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 FefermanSolomon FefermanSolomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
, 1999. "Logic, Logics, and Logicism," Notre Dame Journal of Formal Logic 40: 31-54. - Maddux, Roger D.Roger MadduxRoger Maddux is an American mathematician specializing in algebraic logic.He completed his B.A. at Pomona College in 1969, and his Ph.D. in mathematics at the University of California in 1978, where he was one of Alfred Tarski's last students...
, 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.
- Smith, James T., 2010. "Definitions and Nondefinability in Geometry", American Mathematical MonthlyAmerican Mathematical MonthlyThe American Mathematical Monthly is a mathematical journal founded by Benjamin Finkel in 1894. It is currently published 10 times each year by the Mathematical Association of America....
117:475–89.
External links
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
:- Tarski's Truth Definitions by Wilfred Hodges.
- Alfred Tarski by Mario Gómez-Torrente.
- Propositional Consequence Relations and Algebraic Logic by Ramon Jansana. Includes a fairly detailed discussion of Tarski's work on these topics.
- Tarski’s Semantic Theory on the Internet Encyclopedia of Philosophy.