Alfred Tarski started contributing to set theory at a time when the Zermelo-Fraenkel axiom system was not yet fully formulated and as simple a concept as that of the inaccessible cardinal was not yet fully defined. At the end of Tarski's career the basic concepts of the three major areas and tools of modern axiomatic set theory, namely constructibility, large cardinals and forcing, were already clearly defined and were in the midst of a rapid successful development. The role of Tarski in this development was somewhat similar to the role of Moses showing his people the way to the Promised Land and leading them along the way, while the actual entry of the Promised Land was done mostly by the next generation. The theory of large cardinals was started mostly by Tarski, and developed mostly by his school. The mathematical logicians of Tarski's school contributed much to the development of forcing, after its discovery by Paul Cohen, and to a lesser extent also to the development of the theory of constructibility, discovered by Kurt Gödel. As in other areas of logic and mathematics Tarski's contribution to set theory cannot be measured by his own results only; Tarski was a source of energy and inspiration to his pupils and collaborators, of which I was fortunate to be one, always confronting them with new problems and pushing them to gain new ground.

Tarski's interest in set theory was probably aroused by the general emphasis on set theory in Poland after the First World War, and by the influence of Wactaw Sierpinski, who was one of Tarski's teachers at the University of Warsaw. The very first paper published by Tarski, [21], was a paper in set theory.

Tarski made a fundamental contribution to our understanding of R, perhaps mathematics’ most basic structure. His theorem is the following.

To any formula ϕ(X1, …, Xm) in the vocabulary {0, 1, +, ·, <} one can effectively associate two objects: (i) a quantifier free formula (X 1, …, Xm ) in

(1) the same vocabulary, and (ii) a proof of the equivalence ϕ ↔ that uses only the axioms for real closed fields. (Reminder: real closed fields are ordered fields with the intermediate value property for polynomials.)

Everything in (1) has turned out to be crucial: that arbitrary formulas are considered rather than just sentences, that the equivalence ϕ ↔ holds in all real closed fields rather than only in R; even the effectiveness of the passage from ϕ to has found good theoretical uses besides firing the imagination.

We begin this survey with some history in §1. In §2 we discuss three other influential proofs of Tarski's theorem, and in §3 we consider some of the remarkable and totally unforeseen ways in which Tarski's theorem functions nowadays in mathematics, logic and computer science.

I thank Ward Henson, and in particular Wilfrid Hodges without whose constant prodding and logistic support this article would not have been written.

Any list of Alfred Tarski's achievements would mention his decision procedure for real-closed fields. He proved a number of other less publicized decidability results too. We shall survey these results. After surveying them we shall ask what Tarski had in mind when he proved them. Today our emphases and concepts are sometimes different from those of Tarski in the early 1930s. Some of these changes are the direct result of Tarski's own fundamental work in model theory during the intervening years.

Tarski's work on decidable theories is important not just for the individual decidability theorems themselves. His method for all these decidability results was elimination of quantifiers, and he systematically used this method to prove a range of related theorems about completeness and definability. He also led several of his students to do important work using this same method. Tarski's use of quantifier elimination has had a deep and cumulative influence on model theory and the logical treatment of algebraic theories.

We thank Solomon Feferman, Steven Givant, Haragauri Gupta, Yuri Gurevich. Angus Macintyre, Gregory Moore, Robert Vaught and the referee for helpful discussions and comments. Also we thank Madame Maria Mostowska and Roman Murawski for sending us material from Polish libraries.

In this essay we discuss Tarski's work on what he called the methodology of the deductive sciences, or more briefly, borrowing the terminology of Hilbert, metamathematics, The clearest statement of Tarski's views on this subject can be found in his textbook Introduction to logic [41m].1 Here he describes the tasks of metamathematics as “the detailed analysis and critical evaluation of the fundamental principles that are applied in the construction of logic and mathematics”. He goes on to describe what these fundamental principles are: All the expressions of the discipline under consideration must be defined in terms of a small group of primitive expressions that seem immediately understandable. Furthermore, only those statements of the discipline are accepted as valid that can be deduced by precisely defined and universally accepted means from a small set of axioms whose validity seems evident. The method of constructing a discipline in strict accordance with these principles is known as the deductive method, and the disciplines constructed in this manner are called deductive systems. Since contemporary mathematical logic is one of those disciplines that are subject to these principles, it itself is a deductive science. Tarski then goes on to say:

This identification of mathematics with the deductive sciences is in our view one of the distinctive aspects of Tarski's work. Another characteristic feature is his broad view of what constitutes the domain of metamathematical investigations. A clue to this aspect of his work can also be found in Chapter 6 of Introduction to logic . After a discussion of the notions of completeness and consistency, he remarks that the investigations concerning these topics were among the most important factors contributing to a considerable extension of the domain of methodological studies, and caused even a fundamental change in the whole character of the methodology of deductive sciences.

Tarski's writings on the concepts of truth and logical consequence rank among the most influential works in both logic and philosophy of the twentieth century. Because of this, it would be impossible to give a careful and accurate account of how far that influence reaches and of the complex route by which it spread. In logic, Tarski's methods of defining satisfaction and truth, as well as his work pioneering general model-theoretic techniques, have been entirely absorbed into the way the subject is presently done; they have become part of the fabric of contemporary logic, material presented in the initial pages of every modern textbook on the subject. In philosophy, the influence has been equally pervasive, extending not only to work in semantics and the philosophies of logic and language, but to less obviously allied areas such as epistemology and the philosophy of science as well.

Rather than try to chart the wide-ranging influence of these writings or catalog the important research they have inspired, I will concentrate on various confusions and misunderstandings that continue to surround this work. For in spite of the extensive attention the work has received in the past fifty years, especially in the philosophical literature, misunderstandings of both conceptual and historical sorts are still remarkably widespread. Indeed in the philosophical community, recent reactions to Tarski's work on truth range from Karl Popper's “intense joy and relief” at Tarski's “legitimation” of the notion [1974, p. 399], to Hilary Putnam's assessment that “as a philosophical account of truth, Tarski's theory fails as badly as it is possible for an account to fail” [1985, p. 64]. Opinions have not exactly converged.

In his published work and even more in conversations, Tarski emphasized what he thought were important philosophical aspects of his work. The English translation of his more philosophical papers [56m] was dedicated to his teacher Tadeusz Kotarbiński, and in informal discussions of philosophy he often referred to the influence of Kotarbiński. Also, the influence of Leśniewski, his dissertation adviser, is evident in his early papers. Moreover, some of his important papers of the 1930s were initially given to philosophical audiences. For example, the famous monograph on the concept of truth ([33m], [35b]) was first given as two lectures to the Logic Section of the Philosophical Society in Warsaw in 1930. Second, his paper [33], which introduced the concepts of ω-consistency and ω-completeness as well as the rule of infinite induction, was first given at the Second Conference of the Polish Philosophical Society in Warsaw in 1927. Also [35c] was based upon an address given in 1934 to the conference for the Unity of Science in Prague; [36] and [36a] summarize an address given at the International Congress of Scientific Philosophy in Paris in 1935. The article [44a] was published in a philosophical journal and widely reprinted in philosophical texts. This list is of course not exhaustive but only representative of Tarski's philosophical interactions as reflected in lectures given to philosophical audiences, which were later embodied in substantial papers. After 1945 almost all of Tarski's publications and presentations are mathematical in character with one or two minor exceptions. This division, occurring about 1945, does not, however, indicate a loss of interest in philosophical questions but is a result of Tarski's moving to the Department of Mathematics at Berkeley. There he assumed an important role in the development of logic within mathematics in the United States.

In this paper we consider the problem of lifting properties of the Fréchet ideal Iκ = {X ⊆ κ: ∣X∣ < κ} on a regular uncountable cardinal κ, to an analogue about Iκλ , the ideal of not unbounded subsets of Pκλ. With this in mind, in §1 we introduce and study the class of seminormal λ-generated ideals on Pκλ. We shall see that ideals belonging to this class display properties which are clearly analogous to those of the Fréchet ideal on κ (for instance, with regard to saturation, normality and weak selectivity) and yet are closely related to Iκλ . Our results here show that if λ<λ = λ, then many restrictions of Iκλ are weakly selective, nowhere precipitous and, quite suprisingly, seminormal (but nowhere normal). These latter two results suggest the question of whether any restriction of Iκλ can ever be normal. In §2 we prove that if κ is strongly inaccessible, λ<κ = 2 λ and NS κλ , the ideal of nonstationary subsets of Pκλ, has a mild selective property, then NS κλ ∣A = Iκλ ∣A for some stationary A ⊆ Pκλ.

In [1] Baumgartner showed that if κ is weakly compact and P is the collection of indescribable subsets of κ, then P → (P, κ)2. As a Pκλ analogue of indescribability, Carr (see [3]–[5]) introduced the λ-Shelah property, but was unable to derive the natural Pκλ analogue of Baumgartner's result, (where NSh κλ is the normal ideal on Pκλ induced by the λ-Shelah property). In §3 we show that the problem lies in the fact that, as far as we know, NSh κλ is not sufficiently distributive, and derive conditions which are sufficient and, in a sense, necessary to yield partitions related to .

In the paper mentioned in the title (this Journal, vol. 52 (1987), pp. 208–213), it is shown that if ⊨ “V = HC is recursively inaccessible” is ω-standard -nonstandard, then = s.p.() has at most four r. e. degrees. They are 0 = deg(∅), = deg{e ∣ We is a recursive well-ordering of ω}, = deg{R ∣ ⊨ “R codes a well-ordering”}, and ∨ . Furthermore, 0 < < ∨ and 0 < . Then it is claimed that < < ∨ and = ∨ if are each possible. In fact, < < ∨ always.

The mistake in the argument is that the model ≤ T is really a structure on a set, which we may as well take as ω: there is an R ⊆ ω × ω, R ≤ T , and ‹ω, R› ≃ . So a copy of coded as a relation on ω is ≤ over . But there is no reason to think that the restriction of the isomorphism of and ‹ω, R› to is Σ 1().

A dilator D is a functor from ON to itself commuting with direct limits and pull-backs. A dilator D is a flower iff D(x) is continuous. A flower F is regular iff F(x) is strictly increasing and F(f)(F(z)) = F(f(z)) (for f ϵ ON(x,y), z ϵ X).

Equalization is the following axiom: if F, G ϵ Flr (class of regular flowers), then there is an H ϵ Flr such that F ° H = G ° H. From this we can deduce that if ℱ is a set ⊆ Flr, then there is an H ϵ Flr which is the smallest equalizer of ℱ (it can be said that H equalizes ℱ iff for every F, G ϵ ℱ we have F ° H = G ° H). Equalization is not provable in set theory because equalization for denumerable flowers is equivalent to -determinacy (see a forthcoming paper by Girard and Kechris).

Therefore it is interesting to effectively find, by elementary means, equalizers even in the simplest cases. The aim of this paper is to prove Girard and Kechris's conjecture: “ is the (smallest) equalizer for Flr < ω” (where Flr < ω denotes the set of finite regular flowers). We will verify that is an equalizer of Flr < ω; we will sketch the proof that it is the smallest one at the end of the paper. We will denote by H.

Le rêve secret de tout logicien, c’est de prouver un résultat mathématique significatif avec des moyens de fortune; ce rêve se réalise parfois de manière quelque peu biaisée, le théorème obtenu n’étant qu’une version trop simplifiée, ou bien trop adaptée aux besoins de la logique, pour convaincre un mathématicien normal. C’est pour cela que j’annonce d’emblée la couleur, et que je précise les règles du jeu: la version du théorème de Borel-Tits que je vais montrer, concernant les groupes algébriques simples sur un corps de base algébriquement clos, sera considérée comme pratiquement évidente par un géomètre; mais c’est, à mon avis, la seule qui ait un intérêt pour un théoricien des modèles.

Quand on entreprend ainsi de redémontrer une version simple d’un résultat par ailleurs bien connu, le seul intérêt est dans la méthode: ce que je veux, ici, c’est présenter une preuve qui n’utilise aucune information, ou presque, sur la structure algébrique de ces groupes; il est même souhaitable d’oublier qu’il s’agit de groupes linéaires! Elle repose sur des résultats généraux concernant les groupes de rang de Morley fini, dus à divers auteurs, dont le principal, Boris Iosifovič Zil′ber, a déjà fait une tentative similaire [Zil′ber 1984]; je poursuis ici cette tentative, mais en me limitant à des arguments encore moins spécifiques au contexte de la géométrie.

Si je fais ainsi, ce n’est pas pour donner l’impression que l’unique ambition de la théorie des modèles est de montrer des résultats triviaux par des méthodes triviales.

Le plus souvent, la logique reste une discipline à la périphérie des mathématiques, qu’elle observe de l’extérieur, sans y pénétrer vraiment. C’est un discours sur les mathematiques qui ne dit rien au mathématicien; il n’y reconnait pas son activité favorite, ni ne croit qu’elle puisse avoir une influence sur sa pratique.

L’illustration la plus extrême de cette tradition, ce sont les “reverse mathematics” de Harvey Friedman, qui connaissent le succès que l’on sait. Je veux parler ici d’une tendance toute opposée, secrétée par les développements contemporains de la théorie des modèles, qui promet des positions beaucoup plus directes.

Elle se cristalise autour de l’étude des groupes stables; l’apparition de groupes n’a rien d’inattendu dans un contexte mathématiquement signifiant: un groupe, c’est ce qui garantit une structure non-triviale (ceci n’est pas un simple argument terroriste: il y a des théoremes pour le soutenir); quant à la stabilité, c’est une hypothèse de controle structurel, au large champ d’application, et qu’on pourra dépasser quand seront résolus les problèmes posés dans le cadre stable.

The notion of o-minimality was formulated by Pillay and Steinhorn [PS] building on work of van den Dries [D]. Roughly speaking, a theory T is o-minimal if whenever M is a model of T then M is linearly ordered and every definable subset of the universe of M consists of finitely many intervals and points. The theory of real closed fields is an example of an o-minimal theory.

We examine the structure of the countable models for T, T an arbitrary o-minimal theory (in a countable language). We completely characterize these models, provided that T does not have 2 ω countable models. This proviso (viz. that T has fewer than 2 ω countable models) is in the tradition of classification theory: given a cardinal α, if T has the maximum possible number of models of size α, i.e. 2 α , then no structure theorem is expected (cf. [Sh1]).

O-minimality is introduced in §1. §1 also contains conventions and definitions, including the definitions of cut and noncut. Cuts and noncuts constitute the nonisolated types over a set.

In §2 we study a notion of independence for sets of nonisolated types and the corresponding notion of dimension.

In §3 we define what it means for a nonisolated type to be simple. Such types generalize the so-called “components” in Pillay and Steinhorn's analysis of ω-categorical o-minimal theories [PS]. We show that if there is a nonisolated type which is not simple then T has 2 ω countable models.

Let be a complete Boolean algebra and G a finite simple group in the Scott-Solovay -valued model V () of set theory. If we observe G outside V (), then we get a new group which is denoted by Ĝ. In general, Ĝ is not finite nor simple. Nevertheless Ĝ satisfies every property satisfied by a finite simple group with some translation. In this way, we can get a class of groups for which we can use a well-developed theory of the finite simple groups. We call Ĝ Boolean simple if G is simple in some V (). In the same way we define Boolean simple rings. The main purpose of this paper is a study of structures of Boolean simple groups and Boolean simple rings. As for Boolean simple rings, K. Eda previously constructed Boolean completion of rings with a certain condition. His construction is useful for our purpose.

The present work is a part of a series of systematic applications of Boolean valued method. The reader who is interested in this subject should consult with papers by Eda, Nishimura, Ozawa, and the author in the list of references.

An r.e. degree a ≠ 0, 0′ is called strongly noncappable if it has no inf with any incomparable r.e. degree. We show the existence of a high strongly noncappable degree.

Let K be an algebraically closed field and let L be its canonical language; that is, L consists of all relations on K which are definable from addition, multiplication, and parameters from K. Two sublanguages L 1 and L 2 of L are definably equivalent if each relation in L 1 can be defined by an L 2-formula with parameters in K, and vice versa. The equivalence classes of sublanguages of L form a quotient lattice of the power set of L about which very little is known. We will not distinguish between a sublanguage and its equivalence class.

Let L m denote the language of multiplication alone, and let L a denote the language of addition alone. Let f ∈ K [X, Y] and consider the algebraic function defined by f (x, y) = 0 for x, y ∈ K. Let L f denote the language consisting of the relation defined by f. The possibilities for L m ∨ L f are examined in §2, and the possibilities for L a ∨ L f are examined in §3. In fact the only comprehensive results known are under the additional hypothesis that f actually defines a rational function (i.e., when f is linear in one of the variables), and in positive characteristic, only expansions of addition by polynomials (i.e., when f is linear and monic in one of the variables) are understood. It is hoped that these hypotheses will turn out to be unnecessary, so that reasonable generalizations of the theorems described below to algebraic functions will be true. The conjecture is that L covers L m and that the only languages between L a and L are expansions of L a by scalar multiplications.

The purpose of this paper is to study logical implications which are much weaker than the implication of intuitionistic logic.

In §1 we define the system SI (system of Simple Implication) which is obtained from intuitionistic logic by restricting the inference rules of intuitionistic implication. The implication of the system SI is called the “simple implication” and denoted by ⊃, where the simple implication ⊃ has the following properties:

(1) The simple implication ⊃ is much weaker than the usual intuitionistic implication.

(2) The simple implication ⊃ can be interpreted by the notion of provability, i.e., we have a very simple semantics for SI so that a sentence A ⊃ B is interpreted as “there exists a proof of B from A”.

(3) The full-strength intuitionistic implication ⇒ is definable in a weak second order extension of SI; in other words, it is definable by help of a variant of the weak comprehension schema and the simple implication ⊃. Therefore, though SI is much weaker than the intuitionistic logic, the second order extension of SI is equivalent to the second order extension of the intuitionistic logic.

(4) The simple implication is definable in a weak modal logic MI by the use of the modal operator and the intuitionistic implication ⇒ with full strength. More precisely, A ⊃ B is defined as the strict implication of the form ◽(A ⇒ B).

In §1, we show (3) and (4). (2) is shown in §2 in a more general setting.

Semantics by introduction rules of logical connectives has been studied from various points of view by many authors (e.g. Gentzen [4], Lorentzen [5], Dummett [1], [2], Prawitz [8]. Martin-Löf [7], Maehara [6]). Among them Gentzen (in §§10 and 11 of [4]) introduced such a semantics in order to justify logical inferences and the mathematical induction rule. He observed that all of the inference rules of intuitionistic arithmetic, except for those on implication and negation, are justified by means of his semantics, but justification of the inference rules on implication and negation contains a circular argument for the interpretation by introduction rules, where the natural interpretation of A ⊃ B by ⊃-introduction rule is “there exists a proof of B from A ” (cf. §11 of Gentzen [4]).

We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P −) together with Σ2 -collection (BΣ2). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither lown nor high n-1, while true, cannot be established in P− + BΣn+1 . Consequently, no bounded fragment of first order arithmetic establishes the facts that the highn and lown jump hierarchies are proper on the recursively enumerable degrees.

A countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.

We present a downward Löwenheim-Skolem theorem which transfers downward formulas from L∞,ω to , ω. The simplest instance is:

Theorem 1. Let λ > κ be infinite cardinals, and let L be a similarity type of cardinality κ at most. For every L-structure M of cardinality λ and every X ⊆ M there exists a model N ≺ M containing the set X of power ∣X∣ · κ such that for every pair of finite sequences a, b ∈ N

The following theorem is an application:

Theorem 2. Let λ<κ, T ∈ , ω, and suppose χ is a Ramsey cardinal greater than λ. If T has the (χ, , ω)-unsuperstability property, then T has the (χ, , ω)-unsuperstability property.