TARSKI, ALFRED
(1902–1983)

Alfred Tarski, the Polish-American mathematician and logician, was born in Warsaw, received his doctorate in mathematics from the University of Warsaw in 1924, and two years later was named docent. In 1939 he emigrated to the United States. Appointed lecturer in mathematics at the University of California (Berkeley) in 1942, he remained at that institution for the rest of his life, serving as professor of mathematics from 1946 and becoming professor emeritus in 1968.

Mathematics

Tarski worked in both pure mathematics, especially set theory and algebra, and mathematical logic, especially metamathematics. This entry will not discuss his mathematical contributions, although some of them (in particular his famous theorem, established jointly with Stefan Banach, on the decomposition of the sphere, as well as his theory of inaccessible cardinals) have a definite bearing on the epistemology of mathematics. (See S. Banach and A. Tarski, "Sur la décomposition des ensembles des points en parties respectivement congruentes," Fundamenta Mathematicae 6 [1924]: 244–277.)

It should be noted that in these papers Tarski has not criticized the assumptions of set theory. Like most mathematicians he has simply accepted them as true. This attitude and a systematic use of set-theoretic concepts have profoundly influenced his work in logic and metamathematics. Unlike the followers of David Hilbert and of L. E. J. Brouwer, Tarski has not refrained from the use of infinitistic set-theoretical concepts. He finds a definition or a theorem to be acceptable if it is expressed or proved on the basis of set theory. This attitude, of course, is completely different from that of Hilbert's formalism or Brouwer's intuitionism.

As a consequence of this methodological attitude, Tarski has gained much freedom in introducing new notions and thus has put himself in a much more advantageous position than the adherents of Hilbert or Brouwer. Consider the following very simple but typical example. In Logic, Semantics, Metamathematics (p. 38) Tarski defines the set of consequences of a given set of axioms as the smallest set containing the axioms and closed with respect to the rules of proof, and on this definition he bases the whole theory of the consequence relation in the propositional calculus. A follower of Hilbert or Brouwer would never accept such a definition because he would regard the clarification of the notion of set (involved in this definition) as the ultimate aim of his activity.

The free use of set theory has enabled Tarski to extend the field of application of metamathematics (see, for instance, his investigations of "infinitary languages," discussed below) and has formed a natural basis for the development of his semantic method. This method can indeed be formulated only in a language that has considerable deductive strength and is provided with means to express definitions of a very complicated structure. The general theory of sets satisfies both these requirements.

Obviously Tarski's methodological attitude is rejected by the adherents of finitism and by all logicians who seek in metamathematics a justification or explanation of set theory.

Metamathematics

Metamathematics is a branch of mathematical logic that studies formal theories and solves problems pertaining to such theories. Tarski contributed so much to this field that he deserves to be regarded, with Hilbert, as its cofounder.

axiomatic theory of formal systems

In his early papers Tarski presented an axiomatic theory of arbitrary formal systems. A "theory" for him is a set (whose elements are called formulas) and a function (called the consequence function) that correlates a set of formulas with each such set; this new set is called the set of consequences of the first set. The consequence function is not wholly arbitrary; it must satisfy certain axioms that will not be reproduced here. Several metamathematical notions, such as consistency, completeness, and independence, can be defined for theories in this abstract sense. All formal theories that were known in 1930 can be subsumed under this scheme. While this is no longer true today (see below), a relatively small rectification of Tarski's axioms would suffice to restore the universality of his scheme.

systems based on propositional logic

Besides discussing the most general scheme of formal theories, Tarski axiomatically described theories based on the classical propositional logic. Here the assumptions must, of course, be specialized. It is assumed, for example, that certain operations are defined on the set of formulas (the joining of two formulas by means of a connective). An example of an important property of consequence that Tarski took as an axiom is the deduction theorem. Its importance is that it provides the possibility of defining the consequence function in terms of one fixed set S ₀ of sentences, specifically the set of consequences of the empty set. In concrete cases, S ₀ consists of logical tautologies expressible in the given theory. In what follows, we shall speak of theories as being based on a logic L if S ₀ is the set of tautologies of the logic L.

description of systems

Tarski calls a set X of formulas a system if it is deductively closed, that is, if it is equal to its set of consequences. In "Grundzüge des Systemenkalküls" he formulated a general program aimed at describing all systems of a given theory. Tarski showed in this paper that in order to achieve this aim it is sufficient to describe all complete systems, and he illustrated his program in several simple but interesting cases of decidable theories. Many ideas developed in this paper were later incorporated by Tarski in the general theory of models.

Semantics

In the early 1930s Tarski formulated the semantic method, which is his most important achievement in logic. The essence of the method consists in discussion of the relations between expressions and the objects they denote.

Tarski himself said that his semantics was a modest discipline. Yet the philosophical claims of semantics were ambitious from the start. Tarski's aim was "to construct—with reference to a given language—a materially adequate and formally correct definition of the term 'true sentence, '" a problem "which belongs to the classical questions of philosophy."

Almost from the beginning the methods of semantics exerted a profound influence on philosophers engaged in the construction and study of exact scientific languages. Semantics opened new possibilities in these studies, which formerly were limited to purely syntactic problems and thus were unable to express relations between languages and extralinguistic objects. Semantics offered a natural tool for the discussion of such relations. The price one had to pay was the use of a much stronger metalanguage than the one sufficient for syntax. At any rate, semantic methods became an accepted tool in the study of scientific languages: "Contemporary studies in the methodology of science are primarily concerned with the syntax and semantics of the language of science" (R. M. Martin, Truth and Denotation, Chicago, 1958, p. 16).

Tarski published little concerning the applicability of semantics to the study of empirical languages (see, however, his remarks in "The Semantic Conception of Truth and the Foundations of Semantics"). Rather, he limited himself to applications of his method to logic and mathematics. His most outstanding contributions in these areas will be described briefly.

interpretations of propositional calculi

The propositional calculus provides us with simple examples of semantic notions. Thus, the two-element Boolean algebra is an interpretation of the calculus; the propositional connectives are interpreted as functions whose arguments and values range over the algebra. We may accordingly conceive of the propositional calculus as a language that describes the two-element algebra. Instead of the two-element algebra we may take any other matrix for the propositional calculus. Thus, a formal calculus may have (and in general does have) many interpretations. Tarski early became acquainted with these notions through his collaboration with Jan Łukasiewicz, who in the 1920s initiated the metatheoretical investigation of propositional calculi. In a joint publication Tarski and Łukasiewicz gave a general set-theoretical definition of a matrix and showed its usefulness in various special problems.

models

Models play the same role for theories based on (extensions of) the first-order functional calculus as that played by matrices for propositional calculi. If a theory T has as its primitive constants k predicates with r ₁, · · ·, r_k arguments, then a model for T is defined as an ordered k + 1-tuple 〈A,R ₁,· · ·,R_k 〉, where R_i is a relation with r_i arguments ranging over A (i = l, · · ·, k ). A model determines a partition of sentences into two sets, one consisting of sentences that are true in the model and the other of sentences that are false in the model. A formula that contains free variables is by itself neither true nor false in the model, but if arbitrary elements of A are correlated with the free variables of the formula, it becomes either true or false. In the first case we say that the elements of A correlated with the free variables satisfy the formula in the model. We have here an analogy with the situation in the propositional calculus: if a matrix is given and if its elements are correlated in an arbitrary way with the free variables of a formula, then the formula has a value that is an element of the matrix. This analogy between models and matrices was stressed in "The Concept of Truth in Formalized Languages," in Logic, Semantics, Metamathematics, pp. 152–278. (This is an English translation of an earlier paper.)

The notion of a model and some related semantic notions were known to mathematicians and logicians long before the work of Tarski. No one, however, was concerned to strive for such a degree of precision as Tarski maintained. The fruits of Tarski's approach are first, a precise set-theoretical description of the semantic notions, together with a meticulous discussion of the language in which these definitions are expressible; second, the discovery of general properties of these notions which sometimes are very startling; and third, the discovery of a broad field of applications.

The semantic notions, which before Tarski were used in solving relatively special problems concerning consistency and independence, now turned out to be powerful tools in dealing with many metamathematical investigations. For a philosopher the most important application of the semantic method is Tarski's theory of truth.

logical consequence

Logical consequence is defined as follows: a sentence F is a logical consequence of a set X of sentences if F is true in every model in which all sentences of X are true. For theories based on first-order logic this notion is coextensive with the syntactic notion of derivability (Gödel's completeness theorem). For theories based on the higher-order logics or on the various extensions of first-order logic, these notions are essentially different. Analyzing the intuitions underlying the notion of consequence, one arrives with Tarski at the conclusion that it is the semantic and not the syntactic notion that adequately describes the notion that is intuitively given. At the same time, many logics in which the consequence functions are defined semantically turn out to be free from defects resulting from the incompleteness phenomenon discovered by Kurt Gödel. This shows the essential gains brought by the acceptance of the semantically defined notion of logical consequence. What is lost is the finitary ("combinatorial") description of the consequence function.

definability

Like the notion of consequence, definability can be treated syntactically and semantically. Although investigations in both these directions were pursued in special cases before Tarski, it is only following Tarski's work that we can speak of a systematic theory of definability.

Syntactic theory of definability

Let T be a formal theory among whose constants there is a one-place predicate C. We say that C depends on other constants of T if there is a formula F free of C with exactly one free variable x such that the equivalence C (x ) ≡ F is provable in T. In special cases this notion was used long before Tarski; but Tarski was the first to formulate this notion precisely and in the general case, to discuss its properties, and to discover a far-reaching parallelism between the notions of consequence and definability. One of the most interesting results of his theory is a general formulation of a method (due in principle to A. Padoa) allowing one to establish the independence of a constant. Tarski also showed the universality of this method in cases in which the theory under consideration is based on second-order logic or its extensions; the case of theories based on first-order logic was decided much later by E. W. Beth.

Semantic notion of definability

Let M be a model as defined above. A subset S of A is called definable in M if there is a formula F with exactly one free variable such that an element a of A satisfies F in M if and only if a is an element of S. The formula F is called a definition of S in M.

The determination of the class of definable sets is an interesting problem that occupies a central place in investigations concerning the so-called hierarchies of sets. Without going into details, the aim of these investigations is to discuss sets obtainable from simple sets (which constitute the lowest level of the hierarchy) by means of fixed operations that lead to higher and higher levels. Hierarchies of this kind are discussed in mathematics (the Borel and the projective hierarchies) and in metamathematics (the arithmetical, the hyperarithmetical, and the analytic hierarchies). Tarski and Kazimierz Kuratowski in a joint paper described a method that in many cases allows one to infer directly, from the form of definition of a set, to which level of a given hierarchy this set belongs. Their method introduced essential simplifications into the theory of hierarchies.

The importance of these investigations for metamathematics will be clear if we reflect that, for example, Gödel's incompleteness theorem is an obvious corollary of the fact that the set of (numbers of) sentences derivable from the axioms of arithmetic does not belong to the lowest level of the arithmetical hierarchy. Tarski's work on definability is thus closely connected with problems of incompleteness. The most important result in this field is his theorem on truth, which says that under very general assumptions the set of (numbers of) sentences that are true in a model M is not definable in M. Gödel's incompleteness theorem for arithmetic and many related results are immediate corollaries of this theorem ("On Undecidable Statements in Enlarged Systems of Logic and the Concept of Truth," 1.939). Tarski's semantic theorem, however, requires for its formulation as well as for its proof a much stronger logical basis than the syntactic theorem of Gödel.

general theory of models

Notions closely related to models (as defined above) appeared in abstract mathematics independently of the logical investigations. Mathematicians were led to notions of this degree of generality by the development of abstract algebra. Tarski developed these algebraic investigations and tied them to metamathematics.

It is easy to explain the close connections between the general theory of models and the theory of systems. If we consider a theory whose consequence function is defined semantically, then every system is determined by the class of those models in which all sentences of the system are true. Conversely, every model determines a (complete) system consisting of sentences that are true in the model. However, different models may yield one and the same system.

Tarski and his students exploited these relationships especially for the case in which the theory under consideration is based on first-order logic. In this case it is irrelevant whether we accept the semantic or the syntactic notion of consequence, and we thus have the advantage of being able to use on the one hand the connection between systems and models and on the other the various properties of the consequence function that result from its syntactic definition. One of these properties is the so-called compactness of the consequence function, which states that if a set X of sentences is contradictory, then the same is true of a finite subset of X.

In his publications on the theory of models, which date as far back as 1949, Tarski sought to develop the theory in purely mathematical terms and avoided notions current in logic but less so in mathematics. Consequently his papers on the theory of models are more accessible to mathematicians than to logicians. The details of his highly technical works on the theory of models cannot be related here, and we must content ourselves with the brief indications given above.

generalizations of first-order logic

As was stated earlier, the general setting of model theory is meaningful for theories that are not necessarily based on first-order logic. Tarski suggested two important generalizations of first-order logic and showed that the model-theoretic approach to these logics leads to important discoveries.

The first of these logics is one with infinitely long formulas ("A Sentential Calculus with Infinitely Long Expressions"). Such formulas are, of course, abstract entities definable only in strong systems of set theory; nevertheless, Tarski showed that most of the questions formerly raised exclusively for theories based on ordinary logic are also meaningful for this abstractly described logic. The mathematically important work "Some Problems and Results Relating to the Foundations of Set Theory" resulted from a negative solution of the analogue of the compactness problem ("Some Model-Theoretical Results concerning Weak Second Order Logic," Notices of the American Mathematical Society 5, Abstract 550–6) for logics with infinitely long formulas.

Another important logic introduced by Tarski is weak second-order logic, that is, second-order logic in which the set variables are restricted to finite sets. For this logic as well, the semantic notion of consequence is definable only in a fairly strong system of set theory. Thus weak second-order logic, like the preceding one, is only an abstract construction. Tarski established various metamathematical properties of this logic (for instance, the analogue of the Skolem-Löwenheim theorem) and showed that they imply important mathematical consequences in algebra.

Further Contributions

decision problem and undecidable theories

The decision problem for a theory T is the question whether there exists an algorithm allowing one to decide whether a sentence of T is or is not provable in T. Tarski discussed this problem for a large number of theories using the so-called method of the elimination of quantifiers, which originated with Thoralf Skolem ("The Concept of Truth in Formalized Languages," in Logic, Language, Metamathematics, p. 204). The most important result in this direction was a positive solution of the problem in the case in which T is the first-order theory of the field of real numbers (A Decision Method for Elementary Algebra and Geometry ). This result found numerous applications in algebra and geometry.

A theory for which the decision problem does not admit a positive solution is called undecidable. It was related above how Tarski deduced the incompleteness (and hence the undecidability) of arithmetic from his general theorem. His further efforts were directed toward establishing the undecidability of various very weak but mathematically interesting theories. To this end he introduced the important notion of essential undecidability. A theory is said to be essentially undecidable if all consistent extensions of it are undecidable. Tarski showed in Undecidable Theories (1953) that a theory that has a joint consistent extension with an essentially undecidable theory based on a finite number of axioms is itself undecidable, although in general not essentially undecidable. This theorem provided a basis for numerous undecidability results obtained partly by Tarski and partly by his collaborators.

intuitionist and modal logics

Of the numerous papers that Tarski devoted to the propositional calculus, only those on the intuitionistic and modal propositional calculi can be mentioned here. In "Sentential Calculus and Topology" (Logic, Semantics, Metamathematics, pp. 421–454) he established a startling connection between intuitionistic logic and topology: he constructed matrices for the intuitionistic propositional calculus, using as elements closed subsets of a topological space. In his further work on this calculus, done jointly with J. C. C. McKinsey, he no longer used topological notions but worked instead with certain algebraic structures. The class of all subsets of a topological space and the class of all closed subsets of such a space are examples of such structures, which Tarski and McKinsey called closure algebras and Brouwerian algebras, respectively. Using them, they established several properties of the intuitionistic and modal propositional logics.

cylindric algebras

The above papers give a good illustration of Tarski's growing tendency to deal with metamathematical problems by means of algebraic tools. Another example is his work on cylindric algebras. These algebraic structures are related to the predicate calculus with identity in the way Boolean algebras are related to the usual propositional calculus. Logics with infinitely long expressions can also be investigated by means of suitable cylindric algebras.

calculus of binary relations

The calculus of binary relations was created by Ernst Schröder but soon fell into oblivion. Tarski gave axioms for this calculus, investigated its relations to the predicate calculus, and initiated extensive work on the models of his axioms. Of the several applications of the calculus found by Tarski, the axiomatization of set theory without variables, the existence of undecidable subsystems of the two-valued propositional calculus, and a general method of reduction of the number of primitive terms of a theory should be mentioned.

Philosophy

In the rich bibliography of Tarski's publications there are almost no philosophical papers. The exceptions are "The Establishment of Scientific Semantics" and "The Semantic Conception of Truth and the Foundations of Semantics," which deal with the philosophical significance of semantics. A partial exception is Tarski's paper on the notion of truth (in Logic, Semantics, Metamathematics, pp. 153–278), although the bulk of it is devoted to a systematic exposition of semantics.

Tarski, in oral discussions, often indicated his sympathies with nominalism. While he never accepted the "reism" of Tadeusz Kotarbiński, he was certainly attracted to it in the early phase of his work. However, the set-theoretical methods that form the basis of his logical and mathematical studies compelled him constantly to use the abstract and general notions that a nominalist seeks to avoid. In the absence of more extensive publications by Tarski on philosophical subjects, this conflict appears to have remained unresolved.

See also Boole, George; Brouwer, Luitzen Egbertus Jan; Correspondence Theory of Truth; First-Order Logic; Gödel's Theorem; Hilbert, David; Kotarbiński, Tadeusz; Logic, History of; Łukasiewicz, Jan; Mathematics, Foundations of; Model Theory; Second-Order Logic; Semantics; Set Theory.

Bibliography

Tarski's scientific writings consist of more than one hundred articles and books, plus many abstracts and reviews. Among these the most important for logic and philosophy are the following:

"Sur les truth-functions au sens de MM. Russell et Whitehead." Fundamenta Mathematicae 5 (1924): 59–74.

"Grundzüge des Systemenkalküls." Fundamenta Mathematicae 25 (1935): 503.

"Der Wahrheitsbegriff in den formalisierten Sprachen." Studio Philosophica 1 (1935–1936): 261–405.

"Über unerreichbare Kardinalzahlen." Fundamenta Mathematicae 30 (1938): 68–89.

"On Undecidable Statements in Enlarged Systems of Logic and the Concept of Truth." Journal of Symbolic Logic 4 (1939): 105–112.

"On the Calculus of Relations." Journal of Symbolic Logic 6 (1941): 73–89.

"The Semantic Conception of Truth and the Foundations of Semantics." Journal of Philosophy and Phenomenological Research 4 (1944): 341–375. Reprinted in Readings in Philosophical Analysis, edited by H. Feigl and W. Sellars, 52–84. New York: Appleton-Century-Crofts, 1949.

"On Closed Elements in Closure Algebras." Annals of Mathematics 45 (1944): 141–191, and 47 (1946): 122–162. Written with J. C. C. McKinsey, with remarks by Tarski, 163–165.

"Some Theorems about the Sentential Calculi of Lewis and Heyting." Journal of Symbolic Logic 13 (1948): 1–15. Written with J. C. C. McKinsey.

"Some Notions and Methods on the Borderline of Algebra and Metamathematics." In Proceedings of the International Congress of Mathematicians, 705–720. Cambridge, MA, 1950.

A Decision Method for Elementary Algebra and Geometry. Santa Monica, CA, 1948; 2nd ed., Berkeley: University of California Press, 1951.

Undecidable Theories. Amsterdam: North-Holland, 1953. Written with A. Mostowski and R. M. Robinson.

Logic, Semantics, Metamathematics. Oxford: Clarendon Press, 1956. Tarski's papers on logic from 1923 to 1938, collected and translated by J. H. Woodger.

"A Sentential Calculus with Infinitely Long Expressions." Colloquium Mathematicum 6 (1958): 165–170. Written with Dana Scott. Remarks by Tarski, 171–176.

"Cylindric Algebras." In Proceedings of Symposia in Pure Mathematics: II Lattice Theory, 83–113. Providence, RI: American Mathematical Society, 1961. Written with Leon Henkin.

"Some Problems and Results Relating to the Foundations of Set Theory." In Proceedings of the 1960 Congress on Logic, Methodology, and Philosophy of Science, 125–135. Palo Alto, CA, 1962.

"From Accessible to Inaccessible Cardinals." Fundamenta Mathematicae 53 (1964): 225–308. Written with H. J. Keisler.

Andrzej Mostowski (1967)