It is shown constructively that a strongly extensional function of bounded variation on an interval is regulated, in a sequential sense that is classically equivalent to the usual one.

Unfoldable cardinals are preserved by fast function forcing and the Laver-like preparations that fast functions support. These iterations show, by set-forcing over any model of ZFC, that any given unfoldable cardinal κ can be made indestructible by the forcing to add any number of Cohen subsets to κ.

We formulate and prove a combinatorial property assuming AD + V = L(ℝ). As a consequence, we show that every regular κ which is either a Suslin cardinal or the successor of a Suslin cardinal is -supercompact. In particular, all the projective ordinals are -supercompact.

A maximal almost disjoint (mad) family ⊆ [ω]ω is Cohen-stable if and only if it remains maximal in any Cohen generic extension. Otherwise it is Cohen-unstable. It is shown that a mad family. .is Cohen-unstable if and only if there is a bijection G from ω to the rationals such that the sets G[A]. A ∈ are nowhere dense. An ℵ0-mad family, . is a mad family with the property that given any countable family ℬ ⊂ [ω]ω such that each element of ℬ meets infinitely many elements of in an infinite set there is an element of meeting each element of ℬ in an infinite set. It is shown that Cohen-stable mad families exist if and only if there exist ℵ0-mad families. Either of the conditions b = c or a < cov() implies that there exist Cohen-stable mad families. Similar results are obtained for splitting families. For example, a splitting family. . is Cohen-unstable if and only if there is a bijection G from ω to the rationals such that the boundaries of the sets G[S], S ∈ are nowhere dense. Also. Cohen-stable splitting families of cardinality ≤ κ exist if and only if ℵ0-splitting families of cardinality ≤ κ exist.

It is proved that Vaught's conjecture is true for modules over an arbitrary countable hereditary noetherian prime ring.

This paper concerns Tarski's use of the term “model” in his 1936 paper “On the Concept of Logical Consequence.” Against several of Tarski's recent defenders. I argue that Tarski employed a non-standard conception of models in that paper. Against Tarski's detractors. I argue that this nonstandard conception is more philosophically plausible than it may appear. Finally, I make a few comments concerning the traditionally puzzling case of Tarski's ω-rule example.

We show that all the projective ordinals are supercompact through their supremum and a ways beyond.

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0′. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

We can use the compositional semantics of Hodges [9] to show that any compositional semantics for logics of imperfect information must obey certain constraints on the number of semantically inequivalent formulas. As a corollary, there is no compositional semantics for the ‘independence-friendly’ logic of Hintikka and Sandu (henceforth IF) in which the interpretation in a structure A of each 1 -ary formula is a subset of the domain of A (Corollary 6.2 below proves this and more). After a fashion, this rescues a claim of Hintikka and provides the proof which he lacked:

… there is no realistic hope of formulating compositional truth-conditions for [sentences of IF], even though I have not given a strict impossibility proof to that effect.

(Hintikka [6] page 110ff.) One curious spinoff is that there is a structure of cardinality 6 on which the logic of Hintikka and Sandu gives nearly eight million inequivalent formulas in one free variable (which is more than the population of Finland).

We thank the referee for a sensible change of notation, and Joel Berman and Stan Burris for bringing us up to date with the computation of Dedekind's function (see section 4). Our own calculations, utterly trivial by comparison, were done with Maple V.

The paper Hodges [9] (cf. [10]) gave a compositional semantics for a language with some devices of imperfect information. The language was complicated, because it allowed imperfect information both at quantifiers and at conjunctions and disjunctions.

The recursion theorem in abstract partially ordered algebras, such as operative spaces and others, is the most fundamental result of algebraic recursion theory. The primary aim of the present paper is to prove this theorem for iterative operative spaces in full generality. As an intermediate result, a new and rather large class of models of the combinatory logic is obtained.

We present a basis for the admissible rules of intuitionistic propositional logic. Thereby a conjecture by de Jongh and Visser is proved. We also present a proof system for the admissible rules, and give semantic criteria for admissibility.

The field K((G)) of generalized power series with coefficients in the field K of characteristic 0 and exponents in the ordered additive abelian group G plays an important role in the study of real closed fields. Conway and Gonshor (see [2, 4]) considered the problem of existence of non-standard irreducible (respectively prime) elements in the huge “ring” of omnific integers, which is indeed equivalent to the existence of irreducible (respectively prime) elements in the ring K((G≤0)) of series with non-positive exponents. Berarducci (see [1]) proved that K((G≤0)) does have irreducible elements, but it remained open whether the irreducibles are prime i.e., generate a prime ideal. In this paper we prove that K((G≤0)) does have prime elements if G = (ℝ, +) is the additive group of the reals, or more generally if G contains a maximal proper convex subgroup.

We show that in the lattice of classes there are initial segments [∅, P] = (P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a class P such that L is isomorphic to the lattice (P)*, which is (P). modulo finite differences. For the 2-element lattice, we obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new class P constructed, P has a single, non-computable limit point and (P)* has three elements, corresponding to ∅, P and a minimal class P0 ⊂ P, The element corresponding to P0 has no complement in the lattice. On the other hand, the theory of (P) is shown to be decidable.

A class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then (P)* is always a Boolean algebra. We show that if P is a decidable class and (P) is not a Boolean algebra, then the theory of (P) interprets the theory of arithmetic and is therefore undecidable.

A vast and interesting family of natural semantics lor belief revision is defined. Suppose one is given a distance d between any two models. One may then define the revision of a theory K by a formula α as the theory defined by the set of all those models of α that are closest, by d. to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions.

The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations.

It is shown that FO2 over ordered, respectively wellordered. domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is essentially the same as for plain unconstrained FO2. namely non-deterministic exponential time.

In contrast FO2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings. wellorderings. or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO2 and computation tree logic CTL.

We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[nk] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = VAR[O[1]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.

We introduce a new cardinal characteristic r*. related to the reaping number r. and show that

• posets of size < r* which add reals add unbounded reals;

• posets of size < r which add unbounded reals add Cohen reals.

We also show that add() ≤ min(r. r*). It follows that posets of size < add() which add reals add Cohen reals.

This improves results of Roslanowski and Shelah [RS] and of Zapletal [Z].

If K is a field of finite Morley rank, then for any parameter set A ⊆ Keq the prime model over A is equal to the model-theoretic algebraic closure of A. A field of finite Morley rank eliminates imaginaries. Simlar results hold for minimal groups of finite Morley rank with infinite acl(∅).

A model = (M. E, …) of Zermelo-Fraenkel set theory ZF is said to be 0-like. where E interprets ∈ and θ is an uncountable cardinal, if ∣M∣ = θ but ∣{b ∈ M: bEa}∣ < 0 for each a ∈ M, An immediate corollary of the classical theorem of Keisler and Morley on elementary end extensions of models of set theory is that every consistent extension of ZF has an ℵ1-like model. Coupled with Chang's two cardinal theorem this implies that if θ is a regular cardinal 0 such that 2<0 = 0 then every consistent extension of ZF also has a 0+-like model. In particular, in the presence of the continuum hypothesis every consistent extension of ZF has an ℵ2-like model. Here we prove:

Theorem A. If 0 has the tree property then the following are equivalent for any completion T of ZFC:

(i) T has a 0-like model.

(ii) Ф ⊆ T. where Ф is the recursive set of axioms {∃κ (κ is n-Mahlo and “Vκis a Σn-elementary submodel of the universe”): n ∈ ω}.

(iii) T has a λ-like model for every uncountable cardinal λ.

Theorem B. The following are equiconsistent over ZFC:

(i) “There exists an ω-Mahlo cardinal”.

(ii) “For every finite language , all ℵ2-like models of ZFC() satisfy the schemeФ().

Introduction. In his monograph On Numbers and Games [7], J. H. Conway introduced a real-closed field containing the reals and the ordinals as well as a great many other numbers including ω, ω, /2, 1/ω, and ω − π to name only a few. Indeed, this particular real-closed field, which Conway calls No, is so remarkably inclusive that, subject to the proviso that numbers—construed here as members of ordered “number” fields—be individually definable in terms of sets of von Neumann-Bernays-Gödel set theory with Global Choice, henceforth NBG [cf. 21, Ch. 4], it may be said to contain “All Numbers Great and Small.” In this respect, No bears much the same relation to ordered fields that the system of real numbers bears to Archimedean ordered fields. This can be made precise by saying that whereas the ordered field of reals is (up to isomorphism) the unique homogeneous universal Archimedean ordered field, No is (up to isomorphism) the unique homogeneous universal orderedfield [14]; also see [10], [12], [13].

However, in addition to its distinguished structure as an ordered field, No has a rich hierarchical structure that (implicitly) emerges from the recursive clauses in terms of which it is defined. This algebraico-tree-theoretic structure, or simplicity hierarchy, as we have called it [15], depends upon No's (implicit) structure as a lexicographically ordered binary tree and arises from the fact that the sums and products of any two members of the tree are the simplest possible elements of the tree consistent with No's structure as an ordered group and an ordered field, respectively, it being understood that x is simpler than y just in case x is a predecessor of y in the tree.