In this paper we introduce the notion of a first order topological structure, and consider various possible conditions on the complexity of the definable sets in such a structure, drawing several consequences thereof.

Our aim is to develop, for a restricted class of unstable theories, results analogous to those for stable theories. The “material basis” for such an endeavor is the analogy between the field of real numbers and the field of complex numbers, the former being a “nicely behaved” unstable structure and the latter the archetypal stable structure. In this sense we try here to situate our work on o-minimal structures [PS] in a general topological context. Note, however, that the p-adic numbers, and structures definable therein, will also fit into our analysis.

In the remainder of this section we discuss several ways of studying topological structures model-theoretically. Eventually we fix on the notion of a structure in which the topology is “explicitly definable” in the sense of Flum and Ziegler [FZ]. In §2 we introduce the hypothesis that every definable set is a Boolean combination of definable open sets. In §3 we introduce a “dimension rank” on (closed) definable sets. In §4 we consider structures on which this rank is defined, and for which also every definable set has a finite number of definably connected definable components. We show that prime models over sets exist under such conditions.

Our main goal in this paper is to establish a Glimm-Effros type dichotomy for arbitrary analytic equivalence relations.

The original Glimm-Effros dichotomy, established by Effros [Ef], [Ef1], who generalized work of Glimm [G1], asserts that if an Fσ equivalence relation on a Polish space X is induced by the continuous action of a Polish group G on X, then exactly one of the following alternatives holds:

(I) Elements of X can be classified up to E-equivalence by “concrete invariants” computable in a reasonably definable way, i.e., there is a Borel function f: X → Y, Y a Polish space, such that xEy ⇔ f(x) = f(y), or else

(II) E contains a copy of a canonical equivalence relation which fails to have such a classification, namely the relation xE0y ⇔ ∃n∀m ≥ n(x(n) = y(n)) on the Cantor space 2ω (ω = {0,1,2, …}), i.e., there is a continuous embedding g: 2ω → X such that xE0y ⇔ g(x)Eg(y).

Moreover, alternative (II) is equivalent to:

(II)′ There exists an E-ergodic, nonatomic probability Borel measure on X, where E-ergodic means that every E-invariant Borel set has measure 0 or 1 and E-nonatomic means that every E-equivalence class has measure 0.

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 .

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.

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.

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.

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.

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.

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

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.

Let G be a locally compact abelian group, Γ its dual group, and μ its Haar measure. For a function f: G → C, the Fourier transform of f is defined by

for every γ ∈ Γ.

We extend this definition for a function f on G, whose values are pairwise commutable normal operators in a Hilbert space. Then we study harmonic analysis for this extended Fourier transform.

Our method is Boolean valued analysis as introduced in [11] and [12]. Instead of developing the theory in a step-by-step manner, we shall develop a general machinery showing how to transform classical theorems to theorems in our situation.

In Chapter 1, we summarize the basic knowledge on Hilbert space, on Boolean valued model of set theory, and on Boolean valued analysis. In Chapter 2, we develop the theory of integration. Since we deal with unbounded operators as well as bounded operators, we need a new theory of integration. For a separable Hilbert space, the value of our integration coincides with the value of the usual integration with an adequate generalization for unbounded operators.

In Chapter 3, we establish machinery for our transfer principle and carry out the transformation of many classical theorems to theorems for our case.

When studying the model theory of

the first observation is that the integers can be defined as

Since ∂exp is subject to all of Gödel's phenomena, this is often also the last observation. After Wilkie proved that ℝexp is model complete, one could ask the same question for ∂exp, but the answer is negative.

Proposition 1.1. ∂expis not model complete

Proof. If ∂exp is model complete, then every definable set is a projection of a closed set. Since ∂ is locally compact, every definable set is Fσ. The same is true for the complement, so every definable set is also Gδ. But, since ℤ is definable, ℚ is definable and a standard corollary of the Baire Category Theorem tells us that ℚ is not Gδ.

Still, there are several interesting open questions about ∂exp.

• Is ℝ definable in ∂exp?

• (quasiminimality) Is every definable set countable or co-countable? (Note that this is true in the structure (∂, ℤ, +, ·) where we add a predicate for ℤ).

• (Mycielski) Is there an automorphism of ∂exp other than the identity and complex conjugation?1

A positive answer to the first question would tell us that ∂exp is essentially second order arithmetic, while a positive answer to the second would say that integers are really the only obstruction to a reasonable theory of definable sets.

A fascinating, novel approach to ∂exp is provided by Zilber's [6] pseudoexponentiation. Let L be the language {+, · E, 0, 1}.

The language of the basic logic of proofs extends the usual propositional language by forming sentences of the sort x is a proof of F for any sentence F. In this paper a complete axiomatization for the basic logic of proofs in Heyting Arithmetic HA was found.

Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call and , and , show that suffices to prove B.C.T.II. Some model theory of and its importance in view of Hilbert's program is discussed, as well as applications of our results to functional analysis.

The results in this paper were motivated by the following result due to R. Solovay.

Theorem 1 (Solovay). Let M be a nonstandard model of Peano's first order axioms P and let I ⊂e M (i.e. ϕ ≠ ⊂ M and I is closed under < and successor). Then for each of the functions we can define J ⊆e I in ‹M, I› such that J is closed under that function. (∣x∣ denotes [log2(x)].)

Proof. Just notice that the cuts defined by

are successively closed under

In view of Theorem 1, the following question was raised by R. Solovay: Can we define J ⊆ I in ‹M, I› such that J is closed under exponentiation? In Theorem 2 we show that the answer is “no”. Theorem 3 is based on Theorem 2 and extends the technique to cuts which are models of subsystems of P.

To prove both theorems we shall need an estimate due to R. Parikh (see [1], especially the proof of Theorem 2.2a). For the sake of completeness, and also to introduce some notation we shall sketch Parikh's estimate in the next section. At all times we shall give the easiest estimates which still work rather than the sharpest ones.

The choice construct (choose x: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert's ε operator, but in the main part of the paper we consider the case when all choices are independent.

Wiener, in 1914, reduced the theory of relations to that of classes by construing relations as classes of ordered pairs and defining the ordered pair in turn on the basis of class theory alone.1 The definition, as improved by Kuratowski,2 identifies the ordered pair x;y with uxyi(ix U iy).

In terms of Russell's theory of types, x;y in the above sense is two types higher than x and y. Even when we abandon Russell's theory of fixed types of objects in favor of a theory of stratified formulae,3 there is still significance in saying that ‘x;y’ is of type 2 relative to ‘x’ and ‘y’—meaning that a test of the stratification of any context involves assigning a higher number by 2 to ‘x;y’ than to ‘x’ and ‘y’.