We continue the investigation of the Laver ideal ℓ0 and Miller ideal m0 started in [GJSp] and [GRShSp]; these are the ideals on the Baire space associated with Laver forcing and Miller forcing. We solve several open problems from these papers. The main result is the construction of models for t < add(ℓ0), < add(m0), where add denotes the additivity coefficient of an ideal. For this we construct amoeba forcings for these forcings which do not add Cohen reals. We show that = ω2 implies add(m0) ≤ . We show that , implies cov(ℓ0) ≤ +, cov(m0) ≤ + respectively. Here cov denotes the covering coefficient. We also show that in the Cohen model cov(m0) < holds. Finally we prove that Cohen forcing does not add a superperfect tree of Cohen reals.

The primary relation studied in recursion theory is that of relative complexity: A set or function A (of natural numbers) is reducible to one B if, given access to information about B, we can compute A. The primary reducibility is that of Turing, A ≤TB, where arbitrary (Turing) machines, φe, can be used; access to information about (the oracle) B is unlimited and the lengths of computations are potentially unbounded. Many other interesting reducibilities result from restricitng one or more of these facets of the procedure. Thus, for example, the strongest notion considered is one-one reducibility on sets: A ≤1B iff there is a one-one recursive (= effective) function f such that x Є A ⇔ f(x) Є B. Many-one (≤m) reducibility simply allows f to be many-one. Other intermediate reducibilities include truth-table (≤tt) and weak truth-table (≤wtt). The latter imposes a recursive bound f(x) on the information about B that can be used to compute A(x). The former also bounds the length of computations by requiring that the computation of A(x) from B halt in at most f(x) many steps.

Each such reducibility r defines a notion of degree, degr(A) = {B : A ≤rB ∧ B ≤rA}, and a corresponding structure of the r-degrees ordered by r-reducibility. (We typically denote the degree of A by a.) A major theme in recursion theory has been the investigation of the relation between a set's place in these orderings (the algebraic properties of its degree) and other algorithmic, set-theoretic or definability type notions of complexity. Important examples of such other notions include rates of growth of functions, the types of approximation procedures which converge to the given function or set and the (syntactic) complexity of defining the set (or function) in arithmetic or analysis.

Tense logics in the bimodal propositional language are investigated with respect to the Finite Model Property. In order to prove positive results techniques from investigations of modal logics above K4 are extended to tense logic. General negative results show the limits of the transfer.

Jónsson and Tarski [1951] introduced the notion of a Boolean algebra with (additive) operators (for short, a Bo). They showed that every Bo can be extended to a complete and atomic Bo satisfying certain additional conditions, and that any two complete, atomic extensions of satisfying these conditions are isomorphic over . Henkin [1970] extended these results to Boolean algebras with generalized (i.e., weakly additive) operators. The particular complete, atomic extension of studied by Jónsson and Tarski is called the perfect extension of , and is denoted by +. It is very useful in algebraic investigations of classes of algebras that are associated with logics.

Interesting examples of Bos abound in algebraic logic, and include relation algebras, cylindric algebras, and polyadic and quasi-polyadic algebras (with or without equality). Moreover, there are several important constructions that, when applied to certain Bos, lead to other, derived Bos. Obvious examples include the formation of subalgebras, homomorphic images, relativizations, and direct products. Other examples include the Boolean algebra of ideal elements of a Bo, the neat β;-reduct of an α-dimensional cylindric algebra (β; < α), and the relation algebraic reduct of a cylindric algebra (of dimension at least 3). It is natural to ask about the relationship between the perfect extension of a Bo and the perfect extension of one of its derived algebras ′: Is the perfect extension of the derived algebra just the derived algebra of the perfect extension? In symbols, is (′)+ = (+)′? For example, is the perfect extension of a subalgebra, homomorphic image, relativization, or direct product, just the corresponding subalgebra, homomorphic image, relativization, or direct product of the perfect extension (up to isomorphisms)? Is the perfect extension of the Boolean algebra of ideal elements, or the neat reduct of a cylindric algebra, or the relation algebraic reduct of a cylindric algebra just the Boolean algebra of ideal elements, or the neat β;-reduct, or the relation algebraic reduct, of the perfect extension? We shall prove a general result in this direction; namely, if the derived algebra is constructed as the range of a relatively multiplicative operator, then the answer to our question is “yes”. We shall also give examples to show that in “infinitary” constructions, our question can have a spectacularly negative answer.

This paper considers o-minimal expansions of the structure —the ordered additive reals. More particularly we consider the case when the expansions are “eventually nonlinear” (see below), and find that multiplication is actually definable in all cases except when the structure is “eventually almost linear”, which is a rare special case in which multiplication is obviously not definable. Thus the main theorem established is:

Theorem 1.1. For an o-minimal expansion of , if is eventually non-almost-linear then multiplication is definable in.

(A structure is eventually almost linear iff every definable function f is of the form f(x) = λx + c + ε(x) on some interval (K, ∞), where λ, c Є ℝ and ε is a function of x which tends to 0 faster than any negative power of x as x → +∞. Otherwise, i.e. if there is a definable function which is not of this form, it is eventually non-almost-linear.)

This is proved in §4.1, after §§2 and 3 have established technology concerning the rate of growth of functions and approximating derivatives.

In §4.2 an analogy is made with the result of exponentiation being definable in a polynomially unbounded o-minimal expansion of ℝ as an ordered field (see [Mi]). In fact, by means of the isomorphism x ↦ ln(x) we see that Theorem 1.1 also implies this latter result.

Unless otherwise stated, all structures considered in the paper have ℝ as their universe and all functions are real functions.

We study o-minimal expansions of Archimedean totally ordered groups. We first prove that any such expansion must be elementarily embeddable via a unique (provided some nonzero element is 0-definable) elementary embedding into a unique o-minimal expansion of the additive ordered group of real numbers . We then show that a definable function in an o-minimal expansion of enjoys good differentiability properties and use this to prove that an Archimedean real closed field is definable in any nonsemilinear expansion of . Combining these results, we obtain several restrictions on possible o-minimal expansions of arbitrary Archimedean ordered groups and in particular of the rational ordered group.

We are accustomed to regarding K as the weakest modal logic admitting of a relational semantics in the style made popular by Kripke. However, in a series of papers which demonstrates a startling connection between modal logic and the theory of paraconsistent inference, Ray Jennings and Peter Schotch have developed a generalized relational frame theory which articulates an infinite hierarchy of sublogics of K, each expressing a species of “weakly aggregative necessity”. Recall that K is axiomatized, in the presence of N and RM, by the schema of “binary aggregation”

For each n ≥ 1, the weakly aggregative modal logic Kn is axiomatized by replacing K with the schema of “n-ary aggregation”

which is an n-ary relaxation, or weakening, of K. Note that K1 = K.

In [3], the authors claim without proof that Kn is determined by the class of frames F = (W, R), where W is a nonempty set and R is an (n + 1)-ary relation on W, under the generalization of Kriple's truth condition according to which □α is true at a point w in W if and only if α is true at one of x1,…,xn for all x1,…, xn in W such that Rw, x1,…, xn.

We present a canonical form for definable subsets of algebraically closed valued fields by means of decompositions into sets of a simple form, and do the same for definable subsets of real closed valued fields. Both cases involve discs, forming “Swiss cheeses” in the algebraically closed case, and cuts in the real closed case. As a step in the development, we give a proof for the fact that in “most” valued fields F, if f(x), g(x) ∈ F[x] and v is the valuation map, then the set {x: v(f(x)) ≤ v(g(x))} is a Boolean combination of discs; in fact, it is a finite union of Swiss cheeses. The development also depends on the introduction of “valued trees”, which we define formally.

Pretopologies were introduced in [S], and there shown to give a complete semantics for a propositional sequent calculus BL, here called basic linear logic, as well as for its extensions by structural rules, ex falso quodlibet or double negation. Immediately after Logic Colloquium '88, a conversation with Per Martin-Löf helped me to see how the pretopology semantics should be extended to predicate logic; the result now is a simple and fully constructive completeness proof for first order BL and virtually all its extensions, including the usual, or structured, intuitionistic and classical logic. Such a proof clearly illustrates the fact that stronger set-theoretic principles and classical metalogic are necessary only when completeness is sought with respect to a special class of models, such as the usual two-valued models.

To make the paper self-contained, I briefly review in §1 the definition of pretopologies; §2 deals with syntax and §3 with semantics. The completeness proof in §4, though similar in structure, is sensibly simpler than that in [S], and this is why it is given in detail. In §5 it is shown how little is needed to obtain completeness for extensions of BL in the same language. Finally, in §6 connections with proofs with respect to more traditional semantics are briefly investigated, and some open problems are put forward.

The collection of branches (maximal linearly ordered sets of nodes) of the tree <ωω (ordered by inclusion) forms an almost disjoint family (of sets of nodes). This family is not maximal — for example, any level of the tree is almost disjoint from all of the branches. How many sets must be added to the family of branches to make it maximal? This question leads to a series of definitions and results: a set of nodes is off-branch if it is almost disjoint from every branch in the tree; an off-branch family is an almost disjoint family of off-branch sets; and is the minimum cardinality of a maximal off-branch family.

Results concerning include: (in ZFC) , and (consistent with ZFC) is not equal to any of the standard small cardinal invariants or = 2ω. Most of these consistency results use standard forcing notions—for example, in the Cohen model.

Many interesting open questions remain, though—for example, whether .

Suppose that G is a group that is not finitely generated. Then the cofinality of G, written c(G), is denned to be the least cardinal λ such that G can be expressed as the union of a chain of λ proper subgroups. If κ is an infinite cardinal, then Sym(κ) denotes the group of all permutations of the set κ = {α∣α < κ}. In [1], Macpherson and Neumann proved that c(Sym(κ)) > κ for all infinite cardinals κ. In [4], we proved that it is consistent that c(Sym(ω)) and 2ω can be any two prescribed regular cardinals, subject only to the obvious requirement that c(Sym(ω)) ≤ 2ω. Our first result in this paper is the analogous result for regular uncountable cardinals κ.

Theorem 1.1. Let V ⊨ GCH. Let κ, θ, λ ∈ V be cardinals such that

(i) κ and θ are regular uncountable, and

(ii) κ < θ ≤ cf(λ).

Then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that if G is ℙ-generic then V[G] ⊨ c(Sym(κ)) = θ ≤ λ = 2κ.

Theorem 1.1 will be proved in §2. Our proof is based on a very powerful uniformization principle, which was shown to be consistent for regular uncountable cardinals in [2].

We define a complete theory SHFe of separably closed fields of finite invariant e (=degree of imperfection) which carry an infinite stack of Hasse-derivations. We show that SHFe has quantifier elimination and eliminates imaginaries.

A. M.Pitts in [Pi] proved that is a bi-Heyting category satisfying the Lawvere condition. We show that the embedding Φ: → Sh(P0, J0) into the topos of sheaves, (P0 is the category of finite rooted posets and open maps, J0 the canonical topology on P0) given by H ↦ HA(H, (−)) : P0 → Set preserves the structure mentioned above, finite coproducts, and subobject classifier; it is also conservative. This whole structure on can be derived from that of Sh(P0, J0) via the embedding Φ. We also show that the equivalence relations in are not effective in general. On the way to these results we establish a new kind of duality between and a category of sheaves equipped with certain structure defined in terms of Ehrenfeucht games. Our methods are model-theoretic and combinatorial as opposed to proof-theoretic as in [Pi].

By using the notion of a simplified (κ, 1)-morass, we construct κ-thin-tall, κ-thin-thick and, in a forcing extension, κ-very thin-thick superatomic Boolean algebras for every infinite regular cardinal κ.

We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC1 -circuits.

We investigate in an algebraic setting the question of which logical languages can express the properties integral, permutational, and rigid for algebras of relations.

We show that it is consistent with ZFC (relative to large cardinals) that every infinite Boolean algebra B has an irredundant subset A such that 2∣A∣ = 2∣B∣. This implies in particular that B has 2∣B∣ subalgebras. We also discuss some more general problems about subalgebras and free subsets of an algebra.

The result on the number of subalgebras in a Boolean algebra solves a question of Monk from [6]. The paper is intended to be accessible as far as possible to a general audience, in particular we have confined the more technical material to a “black box” at the end. The proof involves a variation on Foreman and Woodin's model in which GCH fails everywhere.