Alfred Tarski

From Example Problems
Jump to navigation Jump to search

Alfred Tarski (January 14, 1901 in WarsawOctober 26, 1983 in Berkeley, USA) was a Polish mathematician, and widely considered one of the four greatest logicians of all time, along with Aristotle, Gottlob Frege, and Kurt Gödel.

Tarski wrote on algebra, algebraic logic, measure theory, mathematical logic, set theory, and metamathematics. See Truth for a brief description of the "Convention T" standard in his "inductive definition of truth". This was an important contribution to symbolic logic, semantics, and the philosophy of language.

Tarski studied logic and philosophy in Warsaw with Jan Łukasiewicz and Tadeusz Kotarbiński. He was Stanisław Leśniewski's only Ph.D. student. In 1939, Tarski, who had until then earned his living teaching mathematics in secondary schools, received an offer to spend the 1939-40 academic year at Harvard. Quine, who had met Tarski in Warsaw in 1933, was instrumental in obtaining him this invitation. And so in August 1939, Tarski unwittingly was a passenger on the last passenger ship to leave Poland for the USA before the German invasion of Poland, also the outbreak of WWII. He did not see his wife and two children again before 1946. He became an American citizen in 1945. He joined the University of California, Berkeley in 1942, where he spent the rest of his career.

See Givant (1986) for a comprehensive bibliography of Tarski's writings, and Feferman and Feferman (2004) for a full-length biography.

The concept of truth in formalized languages

This paper is a long (over 100 pages) presentation of a mathematical definition of truth for logical languages. It first appeared in 1933 in Polish ("Pojęcie prawdy w językach nauk dedukcyjnych") and then in 1935 in German, under the title "Der Wahrheitsbegriff in den Sprachen der deduktiven Disziplinen." It is thus sometimes referred to as the "Wahrheitsbegriff." Its first appearance in full in English was in 1956 in the first edition of Logic, Semantics, Metamathematics.

Some fairly recent philosophical debate has examined to what extent Tarski's theory of truth for formalized languages can be seen as a correspondence theory of truth. The debate centres 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 if 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 or as embodying truth as a more substantial property. (See Kirkham, 1992.)

On the concept of logical consequence

In 1935, Tarski gave a lecture to the International Congress of Scientific Philosophy in Paris. It appeared in 1936 in a Polish and then a German version. (First appearance in English?) In it he gave either the modern model-theoretic definition of (semantic) logical consequence, or the basis for that modern notion. The question of whether Tarski's notion was the modern one turns on the question of whether he intended to admit models with varying domains (and in particular, models with domains of different cardinalities). This question is currently being debated in the philosophical literature.

Tarski ends his paper 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. Thus, the talk "What are Logical Notions?" can be viewed as continuing the work of "On the Concept of Logical Consequence."

Much of the recent discussion over the treatment of varying domains in this paper was stimulated by (Etchemendy 1999).

A new translation of this paper has recently been produced (Tarski 2002). It gives extensive details of the differences between the German and Polish versions of the paper and corrects a number of mistranslations in the previous translation.

What are logical notions?

A theory of Tarski's that has been attracting attention in the recent philosophical literature is outlined in his "What are Logical Notions?" (Tarski 1986). This is an edited version of a talk that Tarski first 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 was derived from the Erlangen programme of the German 19th century Mathematician, Felix Klein. (Tarski was preceded in applying the Erlangen Program to logic by (Mautner 1946) as well as possibly by an article by the Italian mathematician Silva.)

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-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 (equilateral triangles from non-equilateral triangles, for instance). Continuous transformations (which can intuitively be thought of as transformations which allow non-uniform stretching, compression, bending, and twisting, but no ripping or gluing) allow us to distinguish a polygon from an annulus (ring with a hole in the centre), but does not allow us to distinguish two polygons from each other.

Tarski's proposal was to demarcate the logical notions by considering all possible one-one transformations of a domain onto itself. (By domain here is meant the universe of discourse of a model for the semantic theory of a logic. A one-one transformation of a set onto itself is also known as an automorphism.) If one identifies the truth-value True with the domain set and the truth-value False with the empty set, then the following sorts of operations are counted as logical under the proposal:

1) 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.)
2) Individuals 
No individuals, provided the domain has at least 2 members.
3) Predicates 
The one-placed total and null predicates (the predicate that has all members of the domain in its extension and the predicate that has no members of the domain in its extension).
The two-placed total and null predicates, as well as the identity and diversity predicates (the predicate with the set of all ordered pairs of domain members as its extension, the predicate with the empty set as extension, the predicate with the set of all order-pairs <a, a> where a is a member of the domain and the predicate with the set of all order-pairs <a, b> in its extension, where a and b are distinct members of the domain.
n-ary predicates in general: all predicates definable from the identity predicate together with conjunction, disjunction and negation (up to any ordinality, finite or infinite).
4) 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."
5) Set-Theoretic relations 
Relations such as inclusion, intersection and union applied to subsets of the domain are logical in the present sense.
6) Set-theoretic membership 
Tarski ended his lecture with a discussion of whether the set theory relation of membership 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 of) mathematics is a part of logic.) He pointed out that if you develop set-theory along the lines of a type-theory, set membership does count as logical, whereas if you develop your set theory axiomatically, as in Zermelo-Fraenkel set theory, it counts as extralogical.
7) Logical notions of higher order 
Tarski confined his discussion to operations of first-order logic. However, there is nothing about his proposal that explicitly 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 the results of (Lindenbaum and Tarski 1936) where Tarski and Lindenbaum proved that all the logical operations of Russell and Whitehead's Principia Mathematica are invariant under one-one transformations of the domain onto itself.

The present proposal is also employed in (Tarski and Givant 1987), Tarski's last publication that was completed after his death.

Tarski's proposal was discussed in more recent work of Feferman and McGee.

Solomon Feferman's paper (Feferman 1999) raises problems for the proposal and suggests a modification. Feferman's suggestion is to substitute preservation by arbitrary homomorphism for Tarski's preservation by automorphisms. In essence, this suggestion is made to circumvent the difficulties that 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.

Vann McGee's paper (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, disjunction and quantification over arbitrarily long sequences of variables. In both cases, "arbitrarily long" admits lengths of any ordinality, finite or infinite.


Many of Tarski's more important papers are collected in (Tarski 1983). This includes "The Concept of Truth in Formalized Languages" and "On the Concept of Logical Consequence" discussed above.

  • (Etchemendy 1999) John Etchemendy, The Concept of Logical Consequence, Stanford: CSLI Publications, 1999 ISBN 1575861941
  • (Feferman 1999) Solomon Feferman, Logic, Logics, and Logicism, Notre Dame Journal of Formal Logic 40 (1999) 31-54.
  • (Feferman and Feferman 2004) Anita B Feferman and Solomon Feferman, "Alfred Tarski : Life and Logic", Cambridge University Press, 2004 ISBN 0521802407
  • (Givant 1986) Steven Givant "Bibliography of Alfred Tarski", Journal of Symbolic Logic 51 (1986), 913-941.
  • (Givant 1991) Steven Givant "A portrait of Alfred Tarski", Mathematical Intelligencer 13 (1991), 16-32.
  • (Kirkham 1992) Richard Kirkham Theories of Truth, Cambridge: MIT Press, 1992.
  • (Lindenbaum and Tarski 1936) Adolf Lindenbaum and Alfred Tarski 'On the Limitations of Deductive Theories', (1936) 384-392, in (Tarski 1983)
  • (Mautner 1946) F. I. Mautner 'An Extension of Klein's Erlanger Program: Logic as Invariant-Theory', American Journal of Mathematics, Vol. 68. 345-384.
  • (McGee 1996) Vann McGee, "Logical Operations", Journal of Philosophical Logic, Vol. 25 (1996), 567-580.
  • (Tarski 1944) Alfred Tarski, The Semantical Concept of Truth and the Foundations of Semantics, Philosophy and Phenomenological Research 4 (1944)
  • (Tarski 1983) Alfred Tarski, Logic, Semantics, Metamathematics, 2nd. edition (edited by J. Corcoran) (Indianapolis: Hackett, 1983) (1st edition edited and translated by J. H. Woodger, Oxford 1956).
  • (Tarski 1986) Alfred Tarski, "What are Logical Notions?", edited by John Corcoran, History and Philosophy of Logic, Vol. 7 (1986) 143-154
  • (Tarski 2002) Alfred Tarski, "On the Concept of Following Logically" trans. Magda Stroińska and David Hitchcock. History and Philosophy of Logic 23: 155-196.
  • (Tarski and Givant 1987) Alfred Tarski and Steven Givant, A Formalization of Set Theory Without Variables, (Providence, RI: American Mathematical Society 1987)
  • (Vaught 1986) Robert L. Vaught, "Alfred Tarski's Work in Model Theory", Journal of Symbolic Logic, Vol. 51 (1986), 869-882.

See also

External links

de:Alfred Tarski nl:Alfred Tarski fr:Alfred Tarski ja:アルフレト・タルスキ pl:Alfred Tarski sv:Alfred Tarski