The material presented here belongs to the model theory of the Lκ, λ languages. Our results are either infinitary analogs of important theorems in finitary model theory, or else show that such analogs do not exist.

For example, it is well known that whenever i, and , have the same true Lω, ω sentences (i.e., are elementarily equivalent) for i = 1, 2, then the cardinal sums 1 + 2 and + have the same true Lω, ω sentences, and the direct products 1 · 2 and · have the same true Lω, ω sentences [3]. We show that this is true when ‘Lω, ω’ is replaced by ‘Lκ, λ’ if and only if κ is strongly inaccessible. For Lω1, ω this settles a question, posed by Lopez-Escobar [7].

In §3 we give a complete description of the expressive power of those sentences of Lκ, λ in which the identity symbol is the only relation symbol which occurs. This extends a result by Hanf [4].

Let K be an algebraically closed field of any characteristic, complete with respect to the non-trivial ultrametric absolute value ∣·∣: K → ℝ+. By R denote the valuation ring of K, and by ℘ its maximal ideal. We work within the class of subanalytic sets defined in [5], but our results here also hold for the strongly subanalytic sets introduced in [11] as well as for those subanalytic sets considered in [6]. Let X ⊂ R1 be subanalytic. In [8], we showed that there is a decomposition of X as a union of a finite number of special sets U ⊂ R1 (see below). In this note, in Theorem 1.6, we obtain a version of this result which is uniform in parameters, thereby answering a question brought to our attention by Angus Macintyre. It follows immediately from Theorem 1.6 that the theory of K in the language (see [5] and [6]) is C-minimal in the sense of [3] and [9]. The analogous uniformity result in the p-adic case was recently proved in [12].

Definition 1.1. (i) A disc in R1 is a set of one of the two following forms:

A special set in R1 is a disc minus a finite union of discs.

(ii) R-domains u ⊂ Rm, and their associated rings of analytic functions, , are defined inductively as follows. Rm is an R-domain and , the ring of strictly convergent power series in X1,…, Xm over K. If u is an R-domain with associated ring , (where K 〈X, Y〉 〚ρ〛S is a ring of separated power series, see [5, §2] and [1, §1]) and f, have no common zero on u and ◸ ϵ {<, ≤}, then

is an R-domain and

where J is the ideal generated by I and f − gZ (Z is a new variable) if ◸ is ≤, and

where J is the ideal generated by I and f − gτ (τ a new variable) if ◸ is <. (See [8, Definition 2.2].) R-domains generalize the rational domains of [2, §7.2.3]. It is true, but not easy to prove, that only depends on u as a point set, and is independent of the particular representation of u.

We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, is a countable structure with finite signature, and d is a degree, we say that has αth-jump degreed if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of with universe ω in which the functions and relations have degree at most c. We show that every degree d ≥ 0(ω) is the ωth jump degree of a Boolean algebra, but that for n < ω no Boolean algebra has nth-jump degree d < 0(n). The former result follows easily from work of L. Feiner. The proof of the latter result uses the forcing methods of J. Knight together with an analysis of various equivalences between Boolean algebras based on a study of their Stone spaces. A byproduct of the proof is a method for constructing Stone spaces with various prescribed properties.

As is well-known, the Bernays-Schönfinkel-Ramsey class of all prenex ∃*∀*-sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are ∈ and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for the BSR class is proved by following a purely semantic approach, the remaining part of the decidability result being postponed to a forthcoming paper.

It is well known that every field (formally, real field ) has an algebraic closure (real-closure ). This is to say is an algebraic extension of which is algebraically closed (real-closed). Of course, certain properties of carry over to . In particular, M. O. Rabin has proved in [3] that the algebraic closure—which is of course unique up to isomorphism—of a computable field is computable. The purpose of this note is to establish an analogue of Rabin's theorem for formally real fields. It is clear that a direct analogue can be formulated only in the case of ordered fields, for otherwise there may be many (nonisomorphic) such .

In algebra, the properties of having the (strong) amalgamation property and epis being surjective are well investigated; see the survey [10]. In algebraic logic it is shown that to these algebraic properties there correspond interesting logical properties, see e.g. [15], [12], [4], and [8, p. 311, Problem 10 and the remark below it]. In the present paper we show that the varieties Crsα (of cylindric-relativised set algebras) and Boα (of Boolean algebras with operators) have the strong amalgamation property. These contrast to the following result proved in Pigozzi [15]: No class K with Gsα ⊆ K ⊆ CAα has amalgamation property. Note that Gsα ⊆ Crsα ⊆ Boα and CAα ⊆ Boα. For related results see [3], [1], [16], [11]. For more connections with logic and abstract model theory see [14] and §4.3 of [9].

BA denotes the class of all Boolean algebras. Let α be any ordinal. From now on, throughout in the paper, α is an arbitrary but fixed ordinal. Recall from [7, p. 430, Definition 2.7.1] that an α-dimensional BA with operators, a Boα, is an algebra = 〈A, + −, ci, dij〉i, j ∈ α of the same similarity type as CAα's such that , is a BA and the operations ci (i ∈ α) are additive, i.e., ⊨ ci(x + y) = cix + ciy for all i ⊨ α. If ⊨ Boα then I is called the Boolean reduct of . Note that BA = Bo0. A Boα is said to be normal if {ci 0 = 0: i ∈ α} is valid in it, and a Boα is said to be extensive if {x ≤ cix: i ∈ α} is valid in it. Boα's were introduced in [17].

The class Crsα of all cylindric-relativised set algebras is defined in Definition 1.1.1 (iii) of [8, p. 4]. We give a definition in the present paper, too—see Definition 5 below. It is shown in [13] that ICrsα is a variety.

Our main result is (i) of Theorem 1 below, but we obtain (ii)–(vi), too, as a byproduct from the proof.

By analyzing how one obtains the Stone space of the reduced product of an indexed collection of Boolean algebras from the Stone spaces of those algebras, we derive a topological construction, the “reduced coproduct”, which makes sense for indexed collections of arbitrary Tichonov spaces. When the filter in question is an ultrafilter, we show how the “ultracoproduct” can be obtained from the usual topological ultraproduct via a compactification process in the style of Wallman and Frink. We prove theorems dealing with the topological structure of reduced coproducts (especially ultracoproducts) and show in addition how one may use this construction to gain information about the category of compact Hausdorff spaces.

The study of pseudo-algebraically closed fields (henceforth called PAC) started with the work of J. Ax on finite and pseudo-finite fields [1]. He showed that the infinite models of the theory of finite fields are exactly the perfect PAC fields with absolute Galois group isomorphic to , and gave elementary invariants for their first order theory, thereby proving the decidability of the theory of finite fields. Ax's results were then extended to a larger class of PAC fields by M. Jarden and U. Kiehne [21], and Jarden [19]. The final word on theories of PAC fields was given by G. Cherlin, L. van den Dries and A. Macintyre [10], see also results by Ju. Ershov [13], [14]. Let K be a PAC field. Then the elementary theory of K is entirely determined by the following data:

• The isomorphism type of the field of absolute numbers of K (the subfield of K of elements algebraic over the prime field).

• The degree of imperfection of K.

• The first-order theory, in a suitable ω-sorted language, of the inverse system of Galois groups al(L/K) where L runs over all finite Galois extensions of K.

They also showed that the theory of PAC fields is undecidable, by showing that any graph can be encoded in the absolute Galois group of some PAC field. It turns out that the absolute Galois group controls much of the behaviour of the PAC fields. I will give below some examples illustrating this phenomenon.

We study the uniform computational content of Ramsey’s theorem in the Weihrauch lattice. Our central results provide information on how Ramsey’s theorem behaves under product, parallelization, and jumps. From these results we can derive a number of important properties of Ramsey’s theorem. For one, the parallelization of Ramsey’s theorem for cardinality n ≥ 1 and an arbitrary finite number of colors k ≥ 2 is equivalent to the n-th jump of weak Kőnig’s lemma. In particular, Ramsey’s theorem for cardinality n ≥ 1 is ${\bf{\Sigma }}_{n + 2}^0$-measurable in the effective Borel hierarchy, but not ${\bf{\Sigma }}_{n + 1}^0$-measurable. Secondly, we obtain interesting lower bounds, for instance the n-th jump of weak Kőnig’s lemma is Weihrauch reducible to (the stable version of) Ramsey’s theorem of cardinality n + 2 for n ≥ 2. We prove that with strictly increasing numbers of colors Ramsey’s theorem forms a strictly increasing chain in the Weihrauch lattice. Our study of jumps also shows that certain uniform variants of Ramsey’s theorem that are indistinguishable from a nonuniform perspective play an important role. For instance, the colored version of Ramsey’s theorem explicitly includes the color of the homogeneous set as output information, and the jump of this problem (but not the uncolored variant) is equivalent to the stable version of Ramsey’s theorem of the next greater cardinality. Finally, we briefly discuss the particular case of Ramsey’s theorem for pairs, and we provide some new separation techniques for problems that involve jumps in this context. In particular, we study uniform results regarding the relation of boundedness and induction problems to Ramsey’s theorem, and we show that there are some significant differences with the nonuniform situation in reverse mathematics.

Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.

We define a characteristic and definable subgroup F*(G) of any group G of finite Morley rank that behaves very much like the generalized Fitting subgroup of a finite group. We also prove that semisimple subnormal subgroups of G are all definable and that there are finitely many of them.

In recent years model theorists have been studying various sheaf-theoretic notions as they apply to model theory. For quite a while however, a sheaf of structures was considered to be just a local homeomorphism between topological spaces such that each stalk Sx = p−1(x) is a model-theoretic structure and such that certain maps are continuous. Some of the model-theoretic work done with this notion of a sheaf of structures are the papers by Carson [2] and Macintyre [7]. Soon came the idea of considering a sheaf of structures not just as a collection of structures glued together in some continuous way, but rather as some sort of generalized structure. A significant model-theoretic study of sheaves in this new sense became possible only after the development of the theory of topoi. As F.W. Lawvere pointed out in [6], this represents the advance of mathematics (in our case the advance of model theory) from metaphysics to dialectics.

A topos is the rather ingenious evolution of the notion of a Grothendieck topos [13]. It provides us with the idea that an object of a topos (e.g. the topos of sheaves over a topological space) may be thought of as a generalized set. Furthermore, all first-order logical operations have an interpretation in a topos, hence we may talk about generalized structures. Angus Macintyre suggested that some of his model-theoretic results about sheaves of structures may be understood better and perhaps simplified by doing model theory inside a topos of sheaves.

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic.

Let π be a set of primes. We will call a group π-separated if it can be decomposed as a central product of a π-torsion group of bounded exponent and a π-radicable group. It is easy to see that an abelian π-separated group can in fact be decomposed as a direct product of bounded and π-radicable factors (Lemma 1.1 below). A poly-π-separated group is one which can be obtained from π-separated groups by forming a finite series of group extensions. We will show here:

Theorem 1. Every poly-π-separated nilpotent group is π-separated.

The need for such a result arises in model theory in the case that π is the set of all primes, in which case we refer simply to separated and poly-separated groups. In connection with the conjecture that ω-stable simple groups are algebraic, it is useful to have a structure theory for solvable ω-stable groups analogous to the theory available in the algebraic case over algebraically closed fields. In particular the structure of nilpotent ω-stable groups is of interest, for example in connection with the known result [Zi1], [Ne] that the derived subgroup of a connected solvable ω-stable group of finite Morley rank is nilpotent.

As a model-theoretic application of Theorem 1 we obtain:

Theorem 2. If G is an ω-stable nilpotent group then G may be decomposed as a central product B * D with B and D 0-definable subgroups, B torsion of bounded exponent, and D radicable. In particular, B and D are ω-stable. Furthermore, ω · rk(B ∩ D) ≤ rk D.

Corollary. The ω-stable groups of finite Morley rank are exactly the central products B * D of ω-stable nilpotent groups of finite Morley rank with B torsion of bounded exponent, D radicable, and B ∩ D finite.

In addition to the purely algebraic Theorem 1, these results depend on Macintyre's characterization [Mac] of the ω-stable abelian groups as exactly the separated ones.

In [1] and [2] D. Lewis formulates his counterfactual logic VC as follows. The language contains the connectives ∧, ∨, ⊃, ¬ and the binary connective ≤. A ≤ B is read as “A is at least as possible as B”. The following connectives are defined in terms of ≤.

A < B: = ¬(B ≤ A) (it is more possible that A than that B).

◊ A ≔ ¬(⊥ ≤ A) (⊥ is the false formula; A is possible).

□ A ≔ ⊥ ≤ ¬A (A is necessary).

(if A were the case, then B would be the case).

(if A were the case, then B might be the case).

and are two counterfactual conditional operators. (AB) iff ¬(A ¬B).

The following axiom system VC is presented by D. Lewis in [1] and [2]: V: (1) Truthfunctional classical propositional calculus.

We study descriptive set theory in the space by letting trees with no uncountable branches play a similar role as countable ordinals in traditional descriptive set theory. By using such trees, we get, for example, a covering property for the class of -sets of .

We call a family of trees universal for a class of trees if ⊆ and every tree in can be order-preservingly mapped into a tree in . It is well known that the class of countable trees with no infinite branches has a universal family of size ℵ1. We shall study the smallest cardinality of a universal family for the class of trees of cardinality ≤ ℵ1 with no uncountable branches. We prove that this cardinality can be 1 (under ¬CH) and any regular cardinal κ which satisfies (under CH). This bears immediately on the covering property of the -subsets of the space .

We also study the possible cardinalities of definable subsets of . We show that the statement that every definable subset of has cardinality <ωn or cardinality is equiconsistent with ZFC (if n ≥ 3) and with ZFC plus an inaccessible (if n = 2).

Finally, we define an analogue of the notion of a Borel set for the space and prove a Souslin-Kleene type theorem for this notion.

Venn constructed diagrams of up to five simply connected regions that overlapped each other once in each possible way of overlapping. Although Venn did not prove that his diagrams were constructible for more than five simply connected regions — in fact, he preferred to have a doubly connected region in his 5-class diagram — he summarized his method of construction with an intuitive argument: “But for merely theoretical purposes the rule of formulation would be very simple. It would merely be to begin by drawing any closed figure, and then proceed to draw others, subject to the one condition that each is to intersect once and once only all the existing subdivisions produced by those which had gone before.” The method of construction given below leads to a simple topological proof that Venn diagrams can be constructed for any number of simply connected regions.

On June 4, 1925, Hilbert delivered an address to the Westphalian Mathematical Society in Miinster; that was, as a quick calculation will convince you, almost exactly sixty years ago. The address was published in 1926 under the title Über das Unendliche and is perhaps Hilbert's most comprehensive presentation of his ideas concerning the finitist justification of classical mathematics and the role his proof theory was to play in it. But what has become of the ambitious program for securing all of mathematics, once and for all? What of proof theory, the very subject Hilbert invented to carry out his program? The Hilbertian ambition reached out too far: in its original form, the program was refuted by Gödel's Incompleteness Theorems. And even allowing more than finitist means in metamathematics, the Hilbertian expectations for proof theory have not been realized: a constructive consistency proof for second-order arithmetic is still out of reach. (And since that theory provides a formal framework for analysis, it was considered by Hilbert and Bernays as decisive for proof theory.) Nevertheless, remarkable progress has been made. Two separate, but complementary directions of research have led to surprising insights: classical analysis can be formally developed in conservative extensions of elementary number theory; relative consistency proofs can be given by constructive means for impredicative parts of second order arithmetic. The mathematical and metamathematical developments have been accompanied by sustained philosophical reflections on the foundations of mathematics. This indicates briefly the main themes of the contributions to the symposium; in my introductory remarks I want to give a very schematic perspective, that is partly historical and partly systematic.

In [15], [16] G. Kreisel introduced the no-counterexample interpretation (n.c.i.) of Peano arithmetic. In particular he proved, using a complicated ε-substitution method (due to W. Ackermann), that for every theorem A (A prenex) of first-order Peano arithmetic PA one can find ordinal recursive functionals of order type < ε0 which realize the Herbrand normal form AH of A.

Subsequently more perspicuous proofs of this fact via functional interpretation (combined with normalization) and cut-elimination were found. These proofs however do not carry out the no-counterexample interpretation as a local proof interpretation and don't respect the modus ponens on the level of the nocounterexample interpretation of formulas A and A → B. Closely related to this phenomenon is the fact that both proofs do not establish the condition (δ) and—at least not constructively—(γ) which are part of the definition of an ‘interpretation of a formal system’ as formulated in [15].