Alfred Tarski

Alfred Tarski

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.

mathematics

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.

Stefan Banach

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 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.

David Hilbert

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.

L. E. J. Brouwer

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.

Metamathematics

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.

propositional logic

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 S0 of sentences, specifically the set of consequences of the empty set.

In concrete cases, S0 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 S0 is the set of tautologies of the logic L.

complete system

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.

Semantics

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.

empirical languages

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”.

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.

propositional calculus

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 Lukasiewicz, who in the 1920s initiated the metatheoretical investigation of propositional calculi. In a joint publication Tarski and Lukasiewicz 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.

primitive constants

If a theory T has as its primitive constants k predicates with r1,· · ·, rk arguments, then a model for T is defined as an ordered k + 1-tuple ·A,R1,· · ·,RkÒ,where Ri is a relation with ri 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.

mathematicians

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. 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.

Kurt Gödel

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.

equivalence

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.

E.W. Beth

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.

Kazimierz Kuratowski

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.

arithmetical hierarchy

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).

Enlarged Systems

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.

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.

Further Contributions

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.

Thoralf Skolem

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.

numerous papers

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” 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.

Undecidable Theories

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.

J. C. C. McKinsey

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.

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, although the bulk of it is devoted to a systematic exposition of semantics.

Tadeusz Kotarbinski

Tarski, in oral discussions, often indicated his sympathies with nominalism. While he never accepted the “reism” of Tadeusz Kotarbinski, 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.

remained unresolved