We study extensions of Presburger arithmetic with a unary predicate R and we show that under certain conditions on R, R is sparse (a notion introduced by A. L. Semënov) and the theory of 〈ℕ, +, R〉 is decidable. We axiomatize this theory and we show that in a reasonable language, it admits quantifier elimination. We obtain similar results for the structure 〈ℚ, +, R〉.

We show that the following results in the classical theory of unbounded linear operators on Hilbert spaces can be proved within the framework of Bishop's constructive mathematics: the Kato-Rellich theorem, the spectral theorem. Stone's theorem, and the self-adjointness of the most common quantum mechanical operators, including the Hamiltonians of electro-magnetic fields with some general forms of potentials.

Let k ⊂ K be a field extension, where K is an algebraically closed field of any characteristic and k is the prime field. Recall the following property of Hilbert Schemes (see, for example, [1], Proposition 1.16): Suppose ⊂ × S is a flat family of closed subschemes of parametrised by a scheme S/k. Then for every closed subscheme Z ⊂ in , if [Z] denotes the Hilbert point of Z in Hilb() then the residue field of Hilb() at [Z] is the minimal field of definition for Z. Intuitively, this says that as a family parametrised by Hilb(), each fibre of lies above a point whose “co-ordinates” generate its minimal field of definition.

In the following note we are concerned with a more naive form of the above situation, for which we wish to give an elementary account. Suppose ϕ(x,y) is a system of polynomial equations over k (in variables x = (x1,…, xm) and parameters y = (y1, …, yn)), such that

is a family of (possibly reducible) affine varieties in Km. Each nonempty member of this family has a unique minimal field of definition. The question arises as to whether it is possible to express this family of varieties using parameters that come, pointwise, from these minimal fields of definition. That is, is there a system of polynomial equations ψ(x, z) over k, such that each ψ(x, b) with b ∈ KN is of the form Va for some a ∈ Kn; and such that each Va ∈ is defined by ψ(x, b) for some b ∈ KN whose coordinates generate the minimal field of definition for Va? Moreover, we would like b to be obtained definably from a.

Let (X, T) be a topological space and *X a nonstandard extension of X. Sets of the form *G. where G ∈ T, form a base for the “standard” topology ST on *X. The topological space (*X, ST) will be used to study compactifications of (X, T) in a systematic way.

In this paper we introduce a recursive notation system O(Π3) of ordinals. An element of the notation system is called an ordinal diagram. The system is designed for proof theoretic study of theories of Π3-reflection. We show that for each α < Ω in O(Π3) a set theory KP Π3 for Π3-reflection proves that the initial segment of O(Π3) determined by α is a well ordering. Proof theoretic study for such theories will be reported in [ 4].

The logical system P-W is an implicational non-commutative intuitionistic logic denned by axiom schemes B − (b → c) → (a → b) → a → c. B′ = (a → b) → (b → c) → a → c. I - a → a with the rules of modus ponens and substitution. The P-W problem is a problem asking whether α - β holds if α → β and β → α are both provable in P-W. The answer is affirmative. The first to prove this was E. P. Martin by a semantical method.

In this paper, we give the first proof of Martin's theorem based on the theory of simply typed λ-calculus. This proof is obtained as a corollary to the main theorem of this paper, shown without using Martin's Theorem, that any closed hereditary right-maximal linear (HRML) λ-term of type α → α is βη-reducible to λxx. Here the HRML λ-terms correspond, via the Curry-Howard isomorphism, to the P-W proofs in natural deduction style.

In recent years, there has been renewed interest in the development of formal languages for describing mereological (part-whole) and topological relationships between objects in space. Typically, the non-logical primitives of these languages are properties and relations such as ‘x is connected’ or ‘x is a part of y’, and the entities over which their variables range are, accordingly, not points, but regions: spatial entities other than regions are admitted, if at all, only as logical constructs of regions. This paper considers two first-order mereotopological languages, and investigates their expressive power. It turns out that these languages, notwithstanding the simplicity of their primitives, are surprisingly expressive. In particular, it is shown that infinitary versions of these languages are adequate to express (in a sense made precise below) all topological relations over the domain of polygons in the closed plane.

We provide a general framework for studying the expansion of strongly minimal sets by adding additional relations in the style of Hrushovski. We introduce a notion of separation of quantifiers which is a condition on the class of expansions of finitely generated models for the expanded theory to have a countable ω-saturated model. We apply these results to construct for each sufficiently fast growing finite-to-one function μ from ‘primitive extensions’ to the natural numbers a theory Tμ of an expansion of an algebraically closed field which has Morley rank 2. Finally, we show that if μ is not finite-to-one the theory may not be ω-stable.

A bracket abstraction algorithm is a means of translating λ-terms into combinators. Broda and Damas, in [1], introduce a new, rather natural set of combinators and a new form of bracket abstraction which introduces at most one combinator for each λ-abstraction. This leads to particularly compact combinatory terms. A disadvantage of their abstraction process is that it includes the whole Schönfinkel [4] algorithm plus two mappings which convert the Schönfinkel abstract into the new abstract. This paper shows how the new abstraction can be done more directly, in fact, using only 2n − 1 algorithm steps if there are n occurrences of the variable to be abstracted in the term. Some properties of the Broda-Damas combinators are also considered.

We give a new proof of the classification of ℵ0-categorical quasivarieties by using Morita equivalence to reduce to term minimal quasivarieties.

We consider a set generic over the arithmetic sets. A subset A of the natural numbers is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every -set of strings S, there is a string σ ⊂ A such that σ ∈ S or no extension of σ is in S. By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, let D(≤ a) denote the set of degrees which are recursive in a.

We say a is a strong minimal cover of g if every degree strictly below a is less than or equal to g. In this paper we show that there are a degree a and a 1-generic degree g < a such that a is a strong minimal cover of g. This easily implies that there is a 1-generic degree without the cupping property. Jockusch [7] showed that every 2-generic degree has the cupping property. Slaman and Steel [17] and independently Cooper [3] showed that there are recursively enumerable degrees a and b < a such that no degree c < a joins b above a. Take a 1-generic degree g below b. Then g does not have the cupping property.

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space.

For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models.

This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that the Borel cardinalities of the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action.

One of the first things to be addressed concerns the complexity of these equivalence relations. This question for appears in [1].

We discuss ways in which a typical one-dimensional Brownian motion can be approximated by oscillations which are encoded by finite binary strings of high descriptive complexity. We study the recursive properties of Brownian motions that can be thus obtained.

Here we investigate the classes of representable directed cylindric algebras of dimension α introduced by Németi [12]. can be seen in two different ways: first, as an algebraic counterpart of higher order logics and second, as a cylindric algebraic analogue of Quasi-Projective Relation Algebras. We will give a new, “purely cylindric algebraic” proof for the following theorems of Németi: (i) is a finitely axiomatizable variety whenever α ≥ 3 is finite and (ii) one can obtain a strong representation theorem for if one chooses an appropriate (non-well-founded) set theory as foundation of mathematics. These results provide a purely cylindric algebraic solution for the Finitization Problem (in the sense of [11]) in some non-well-founded set theories.

In [1], examples of types of U-rank 1 (i.e., minimal types) in the theories of separably closed fields were constructed, en route to displaying certain dimension phenomena. We construct here additional examples with U-rank 1 and of various transcendence degrees over arbitrary separably closed fields. Our examples include ones which are minimal but of infinite transcendence degree, i.e., not thin. Our interest in building new examples was piqued after seeing the role played by minimal types over separably closed fields in Hrushovski's analysis of abelian varieties. This article is the result of several working sessions between the authors at Wesleyan University and Paris 7, and was completed during the Model Theory of Fields program at MSRI in 1998. We are grateful for the hospitality and support of all three institutions. We thank Elisabeth Bouscaren and Françoise Delon for reading an earlier version of this paper, providing useful suggestions and corrections.

We characterize the 3-stratiflable theorems of NF as a 3-stratifiable extension of NF3: and show that NF is equiconsistent with TT plus raising type axioms for sentences asserting the existence of some predicate over an atomic Boolean algebra.

In this paper we set out the basic model theory of differential fields of characteristic 0, which have finitely many commuting derivations. We give axioms for the theory of differentially closed differential fields with m derivations and show that this theory is ω-stable, model complete, and quantifier-eliminable, and that it admits elimination of imaginaries. We give a characterization of forking and compute the rank of this theory to be ωm + 1.

In this paper we construct a non-CM -trivial stable theory in which no infinite field is interpretable. In fact our theory will also be trivial and ω-stable, but of infinite Morley rank. A long term aim would be to find a non CM-trivial theory which has finite Morley rank (or is even strongly minimal) and does not interpret a field. The construction in this paper is direct, and is a “3-dimensional” version of the free pseudoplane. In a sense we are cheating: the original point of the notion of CM-triviality was to describe the geometry of a strongly minimal set, or even of a regular type. In our example, non-CM-triviality will come from the behaviour of three orthogonal regular types.

A stable theory is said to be CM-trivial if whenever A ⊆ B and acl(Ac) ∩ acl(B) = acl(A) in Teq, then Cb(stp(c/A)) ⊆ Cb(stp(c/B)). ( An infinite stable field will not be CM-trivial.) The notion is due to Hrushovski [3], where he gave several equivalent definitions, as well as showing that his new strongly minimal sets constructed “ab ovo” were CM-trivial. The notion was studied further in [6] where it was shown that CM-trivial groups of finite Morley rank are nilpotent-by-finite. These results were generalized in various ways to the superstable case in [8].

We exhibit a construction which produces for every Turing machine T with two halting states μ0 and μ−1, an algebra B(T) (finite and of finite type) with the property that the variety generated by B(T) is residually large if T halts in state μ−1, while if T halts in state μ0 then this variety is residually bounded by a finite cardinal.

Let X be a compact metric space. A closed set K ⊆ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) > r is allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA0, WKL0 and ACA0. We also give some applications of these concepts by discussing some versions of the Tietze extension theorem. In particular we prove an RCA0 version of this result for weakly located closed sets.