Ever since Spector's brilliant application of measure theory to recursion theory in 1958 [6] it has been realized that measure theory promotes sweeping simplifications in the theory of degrees. Results previously thought to be pathological were shown by Spector, and later Sacks [4], [5], to hold for almost all degrees (“almost all” in the sense of Lebesgue measure), often with much simpler proofs. Good examples of this phenomenon are Spector's demonstration that almost all pairs of sets are of incomparable degree (as an immediate consequence of Fubini's theorem) and Sacks' exquisitely simple deduction from this result that almost every degree is the join of two incomparable degrees (for if a random sequence is decomposed into its even and odd parts, the result is a random pair).

The present paper attempts to vindicate the feeling that almost all degrees behave in a simple manner by showing that if the quantifier in the theory of degrees with ′(jump), ∪ (join) and ∩ (meet) is taken to be (almost ∀a) instead of (∀a) then the theory is decidable. We are able to use ∩ because it will be shown that if t1, t2 are any terms built from degree variables a1, …, am with ′ and ∪ then t1 ∩ t2 exists for almost all a1, …, am. Thus the “almost all” theory presents a sharp contrast to the standard theory, where ∩ is not always defined (Kleene-Post [1]) and which is known to be undecidable (Lachlan [2]).

Let T be a countable, small simple theory. In this paper, we prove that for such T, the notion of Lascar strong type coincides with the notion of strong type, over an arbitrary set.

In this paper we consider various properties of Jensen's □ principles and use them to construct several examples concerning the so-called Novák number of partially ordered sets.

In §1 we give the relevant definitions and review some facts about □ principles. Apart from some simple observations most of the results in this section are known.

In §2 we consider the Novák number of partially ordered sets and, using □ principles, give counterexamples to the productivity of this cardinal function. We also formulate a principle, show by forcing that it is consistent and use it to construct an ℵ2-Suslin tree T such that forcing with T × T collapses ℵ1.

In §3 we briefly consider games played on partially ordered sets and relate them to the problems of the previous section. Using a version of □ we give an example of a proper partial order such that the game of length ω played on is undetermined.

In §4 we raise the question of whether the Novák number of a homogenous partial order can be singular, and show that in some cases the answer is no.

We assume familiarity with the basic techniques of forcing. In §1 some facts about large cardinals (e.g. weakly compact cardinals are -indescribable) and elementary properties of the constructible hierarchy are used. For this and all undefined terms we refer the reader to Jech [10].

We prove that no restriction of the sine function to any (open and nonempty) interval is definable in 〈R, +, ·, ×, <, exp, constants〉, and that no restriction of the exponential function to an (open and nonempty) interval is definable in 〈R, +, ·, <, sin0, constants〉, where sin0(x) = sin(x) for x ∈ [—π, π], and sin0(x) = 0 for all x ∉ [—π, π].

The least possible jump for a degree of unsolvability a is its join a ∪ 0′ with 0′. Friedberg [1] showed that each degree b ≥ 0′ is the jump of a degree a realizing least possible jump (i.e., satisfying the equation a′ = a ∪ 0′). Sacks (cf. Stillwell [8]) showed that most (in the sense of Lebesgue measure) degrees realize least possible jump. Nevertheless, degrees not realizing least possible jump are easily found (e.g., any degree b ≥ 0′) even among the degrees <0′ (cf. Shoenfield [5]) and the recursively enumerable (r.e.) degrees (cf. Sacks [3]).

A degree is called minimal if it is minimal in the natural partial ordering of degrees excluding least element 0. The existence of minimal degrees <0” was first shown by Spector [7]; Sacks [3] succeeded in replacing 0” by 0′ using a priority argument. Yates [9] asked whether all minimal degrees <0′ realize least possible jump after showing that some do by exhibiting minimal degrees below each r.e. degree. Cooper [2] subsequently showed that each degree b > 0′ is the jump of a minimal degree which, as corollary to his method of proof, realizes least possible jump. We show with the aid of a simple combinatorial device applied to a minimal degree construction in the manner of Spector [7] that not all minimal degrees realize least possible jump. We have observed in conjunction with S. B. Cooper and R. Epstein that the new combinatorial device may also be applied to minimal degree constructions in the manner of Sacks [3], Shoenfield [6] or [4] in order to construct minimal degrees <0′ not realizing least possible jump. This answers Yates' question in the negative. Yates [10], however, has been able to draw this as an immediate corollary of the weaker result by carrying out the proof in his new system of prioric games.

We study first-order logic with two variables FO2 and establish a small substructure property. Similar to the small model property for FO2 we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse the satisfiability problem for FO2 under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO2 has the finite model property and is complete for non-deterministic exponential time, just as for plain FO2. With two equivalence relations, FO2 does not have the finite model property, but is shown to be decidable via a construction of regular models that admit finite descriptions even though they may necessarily be infinite. For three or more equivalence relations, FO2 is undecidable.

The purpose of this paper is to define and investigate a new (equational) class of algebras, which we call semi-De Morgan algebras, as a common abstraction of De Morgan algebras and distributive pseudocomplemented lattices. We were first led to this class of algebras in 1979 (in Brazil) as a result of our attempt to extend both the well-known theorem of Glivenko (see [4, Theorem 26]) and Lakser's characterization of principal congruences to a setting more general than that of distributive pseudocomplemented lattices. In subsequent years, our work in [20] on a subvariety of Ockham algebras, first considered by Berman [3], renewed our interest in semi-De Morgan algebras by providing new examples. It seems worth mentioning that these new algebras may also turn out to be useful in resolving a conjecture made in [22] to unify certain strikingly similar results on Heyting algebras with a dual pseudocomplement (see [21]) and Heyting algebras with a De Morgan negation (see [22]).

In §2 we introduce semi-De Morgan algebras and prove the main theorem, which, roughly speaking, states that certain elements of a semi-De Morgan algebra form a De Morgan algebra. Several applications then follow, including new axiomatizations of distributive pseudocomplemented lattices, Stone algebras and De Morgan algebras.

We show that a set has an η-representation in a linear order if and only if it is the range of a 0′-computable limitwise monotonic function. We also construct a Δ3 Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey.

Both syntactic and semantic solutions are given for the entailment problem of duality theory. The test algebra theorem provides both a syntactic solution to the entailment problem in terms of primitive positive formula and a new derivation of the corresponding result in clone theory, viz. the syntactic description of Inv(Pol(R)) for a given set R of unitary relations on a finite set. The semantic solution to the entailment problem follows from the syntactic one, or can be given in the form of an algorithm. It shows, in the special case of a purely relational type, that duality-theoretic entailment is describable in terms of five constructs, namely trivial relations, intersection, repetition removal, product, and retractive projection. All except the last are concrete, in the sense that they are described by a quantifier-free formula. It is proved that if the finite algebra M generates a congruence-distributive variety and all subalgebras of M are subdirectly irreducible, then concrete constructs suffice to describe entailment. The concept of entailment appropriate to strong dualities is also introduced, and described in terms of coordinate projections, restriction of domains, and composition of partial functions.

This paper answers some questions which naturally arise from the Spector-Gandy proof of their theorem that the π1 1 sets of natural numbers are precisely those which are defined by a Σ1 1 formula over the hyperarithmetic sets. Their proof used hierarchies on recursive linear orderings (H-sets) which are not well orderings. (In this respect they anticipated the study of nonstandard models of set theory.) The proof hinged on the following fact. Let e be a recursive linear ordering. Then e is a well ordering if and only if there is an H-set on e which is hyperarithmetic. It was implicit in their proof that there are recursive linear orderings which are not well orderings, on which there are H-sets. Further information on such nonstandard H-sets (often called pseudohierarchies) can be found in Harrison [4]. It is natural to ask: on which recursive linear orderings are there H-sets?

In Friedman [1] it is shown that there exists a recursive linear ordering e that has no hyperarithmetic descending sequences such that no H-set can be placed on e. In [1] it is also shown that if e is a recursive linear ordering, every point of which has an immediate successor and either has finitely many predecessors or is finitely above a limit point (heretofore called adequate) such that an H-set can be placed on e, then e has no hyperarithmetic descending sequences. In a related paper, Friedman [2] shows that there is no infinite sequence xn of codes for ω-models of the arithmetic comprehension axiom scheme such that each x n+ 1 is a set in the ω-model coded by xn , and each x n+1 is the unique solution of P(xn , x n+1) for some fixed arithmetic P.

Consider modal propositional formulae, constructed using proposition-letters, connectives and the modal operators □ and ⋄. The semantic structures are frames, i.e., pairs <W, R> with R ⊆ W2. Let F, V be variables ranging respectively over frames and functions from the set of proposition-letters into the powerset of W. Then the relation

may be defined, for arbitrary formulae α, following the Kripke truth-definition. From this relation we may further define

Now, to every modal formula α there corresponds some property Pα of R. A particular example is obtained by considering the well-known translation of modal formulae into formulae of monadic second-order logic with a single binary first-order predicate. For these particular Pα we have

for all F and w ∈ W. These formulae Pα are, however, rather intractable and more convenient ones can often be found. An especially interesting case occurs when Pα may be taken to be some first-order formula. For example, it can be seen that

for all F and w ∈ W. It is customary to talk about a related correspondence, namely when for all F we have

Note that this correspondence holds whenever the first one above holds.

A natural deduction formulation is given for the intermediate logic called MH by Gabbay in [4]. Proof-theoretic methods are used to show that every deduction can be normalized, that MH is the weakest intermediate logic for which the Glivenko theorem holds, and that the Craig-Lyndon interpolation theorem holds for it.

In this paper we prove the Chomsky Conjecture (all languages recognized by the Lambek calculus are context-free) for both the full Lambek calculus and its product-free fragment. For the latter case we present a construction of context-free grammars involving only product-free types.

The implicational fragment of the logic of relevant implication, R→ is known to be decidable. We show that the implicational fragment of the logic of ticket entailment, T→ is decidable. Our proof is based on the consecution calculus that we introduced specifically to solve this 50-year old open problem. We reduce the decidability problem of T→ to the decidability problem of R→. The decidability of T→ is equivalent to the decidability of the inhabitation problem of implicational types by combinators over the base {B, B′, I, W}.

We study the class of elementary submodels of a large superstable homogeneous model. We introduce a rank which is bounded in the superstable case, and use it to define a dependence relation which shares many (but not all) of the properties of forking in the first order case. The main difference is that we do not have extension over all sets. We also present an example of Shelah showing that extension over all sets may not hold for any dependence relation for superstable homogeneous models.

As proved recently, the satisfaction problem for all prenex formulae in the set-theoretic Bernays-Shönfinkel-Ramsey class is semi-decidable over von Neumann's cumulative hierarchy. Here that semi-decidability result is strengthened into a decidability result for the same collection of formulae.

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.

Modal reduction principles (MRPs) are modal formulas of the following form: Mp → Np, where M, N are (possibly empty) sequences of modal operators (i.e. □ or ◊). The notation M, N will be used to abbreviate such an MRP. We study a certain semantic correspondence between modal formulas and relational properties and obtain two main results. (1) On transitive semantic structures every MRP corresponds to a first-order relational property. (2) For the general case a syntactic criterion exists for distinguishing modal formulas with corresponding first-order properties from the others.