Schiller Joe Scroggs in [9] established remarkable facts concerning “normal” extensions of the modal sentential calculus S5, the most notable of these facts being that all such proper extensions have finite characteristic matrices. The major import of the present paper is that like facts hold for the relevant sentential calculus R-Mingle (RM). Robert K. Meyer in [6] has obtained an important completeness result for RM, which will play a central role in our results. However, in §2 we shall obtain a new proof of Meyer's result as a by-product of the algebraic logic that we develop in §1. Also in §2 we shall obtain the promised results for extensions of RM. In §3 we shall provide a strong completeness theorem for RM by generalizing the semantics of Meyer.

A denumerable structure is said to be recursive iff its universe is a recursive subset of the natural numbers and its relations and operations are recursive. For example, the standard model of number theory is recursive. A structure is said to be recursively presentable iff it is isomorphic to a recursive structure. For example, a Boolean algebra generated by ℵ0 free generators is easily seen to be recursively presentable. (For basic facts concerning Boolean algebras, the reader is referred to R. Sikorski [9] and A. Tarski and A. Mostowski [10].)

An initial segment of hyperdegrees is a set S of hyperdegrees such that whenever h ∈ S and k ≦ h then k ∈ S. The main results of this paper affirm the existence of initial segments having certain order types. In particular, if L is a finite distributive lattice then L is isomorphic to an initial segment of hyperdegrees [Theorem 1]; as a consequence the elementary theory of the ordering of hyperdegrees is recursively undecidable [Corollary 1].

A theory formulated in a countable predicate calculus can have at most nonisomorphic countable models. It has been conjected (e.g., in [4]) that if it has an uncountable number of such models then it has exactly such. Of course, this would follow immediately if one assumed the continuum hypothesis.

In this paper we show that if a theory has more than ℵ1 (i.e., at least ℵ2) isomorphism types of countable models then it has exactly . Our results generalize immediately to theories in Lω1ω and even to pseudo-axiomatic classes in Lω1ω . In this last case, a result of H. Friedman shows that it is the best possible result.

Since about 1955, recursive, (hyper-)arithmetic and well-orderings have been investigated by many authors. Now we shall generally consider analytic well-orderings and compare their representation-capacities for ordinals.

Let K be a class of predicates. Then, R is called a Kwell-ordering if R is a binary relation of natural numbers belonging to the class K and satisfies the following conditions:

(i) R(x, y) ∧ R(y, x) → x = y;

(ii) x, y ∈ D(R) → R(x, y) ∨ R(y, x), where D(R) is the domain of R, that is to say, the set {x ∣ (∃y)[R(x, y) ∨ R(y, x)]};

(iii) R(x, y) ∧ R(y, z) → R(x, z);

(iv) .

The strong homogeneity conjecture asserts that, for any Turing degree, a, there is a jump preserving isomorphism from the upper semilattice of degrees to the upper semilattice of degrees above a. Rogers [3, p. 261] states that this problem is open and notes that its truth would simplify many proofs about degrees. It is, in fact, false. More precisely, let 0 be the smallest degree and let 0(n) be the nth iterated jump of 0, as defined in [3, pp. 254–256].

In the monograph [1] of Chang and Keisler, a considerable extent of model theory of the first order continuous logic (that is, roughly speaking, many-valued logic with truth values from a topological space) is ingeniously developed without using any notion of provability.

In this paper we shall define the notion of provability in continuous logic as well as the notion of matrix, which is a natural extension of one in finite-valued logic in [2], and develop the syntax and semantics of it mostly along the line in the preceding paper [2]. Fundamental theorems of model theory in continuous logic, which have been proved with purely model-theoretic proofs (i.e. those proofs which do not use any proof-theoretic notions) in [1], will be proved with proofs which are natural extensions of those in two-valued logic.

In this paper we prove two theorems. They answer questions raised by Myhill in 1956. (We recall the well-known fact that Myhill's invention of the maximal set in 1956 [2] stemmed from his attempt to prove I below.)

I. There exists an axiomatizable, essentially undecidable theory in standard formalization such that all axiomatizable extensions of are finite extensions.

II. There exists an axiomatizable but undecidable theory in standard formalization such that

(a) has a consistent, complete, decidable extension ,

(b) If is an axiomatizable extension of then either

(i) is a finite extension of , or

(ii) is a finite extension of .

The algebras studied in this paper were suggested to the author by William Craig as a possible substitute for cylindric algebras. Both kinds of algebras may be considered as algebraic versions of first-order logic. Cylindric algebras can be introduced as follows. Let ℒ be a first-order language, and let be an ℒ-structure. We assume that ℒ has a simple infinite sequence ν 0, ν 1, … of individual variables, and we take as known what it means for a sequence ν 0, ν 1, … of individual variables, and we take as known what it means for a sequence x = 〈x 0, x 1, …〉 of elements of to satisfy a formula ϕ of ℒ in . Let ϕ be the collection of all sequences x which satisfy ϕ in . We can perform certain natural operations on the sets ϕ , of basic model-theoretic significance: Boolean operations = cylindrifications diagonal elements (0-ary operations) . In this way we make the class of all sets ϕ into an algebra; a natural abstraction gives the class of all cylindric set algebras (of dimension ω). Thus this method of constructing an algebraic counterpart of first-order logic is based upon the notion of satisfaction of a formula by an infinite sequence of elements. Since, however, a formula has only finitely many variables occurring in it, it may seem more natural to consider satisfaction by a finite sequence of elements; then ϕ becomes a collection of finite sequences of varying ranks (cf. Tarski [10]). In forming an algebra of sets of finite sequences it turns out to be possible to get by with only finitely many operations instead of the infinitely many ci 's and dij 's of cylindric algebras. Let be the class of all algebras of sets of finite sequences (an exact definition is given in §1).

In [1] it is shown that for every sequence x = 〈xn : n ∈ ω〉 ∈ Xω Λ there is an isol xω (essentially an immunized product) such that

Here we have used the notation: Λ = the isols, ω = the nonnegative integers, pn is the nth prime rational integer starting with p0 = 2, ∣ denotes divisibility and ∤ its negation. If p is an arbitrary prime, py ∣ x, pz ∣ x, and y < z then py+1 ∣ x. In particular since y ∈ ω is comparable with every element of Λ, the conditions py ∣ x and py+1 ∤ x uniquely determine y. Thus every sequence x ∈ Xωω is uniquely determined by an xω satisfying (1) and consequently may be used as a “code” for that sequence. In Theorem 1 it is shown that (1) does not uniquely determine the values of an arbitrary sequence x ∈ XωΛ, however in Theorem 3 we find a different scheme which does. At the very end of the paper we give some reasons why coding theorems are useful. It should also be mentioned that for a coding theorem to be meaningful it is necessary to restrict the operations by which a sequence can be recaptured from its code. Otherwise a triviality results. Our coding theorem will allow all operations which are first order definable in Λ with respect to addition, multiplication, and exponentiation. We conjecture that the latter operation is really necessary.

In [8] S. J. Maslov gives a positive solution to the decision problem for satisfiability of formulas of the form

in any first-order predicate calculus without identity where h, k, m, n are positive integers, αi, βi are signed atomic formulas (atomic formulas or negations of atomic formulas), and ∧, ∨ are conjunction and disjunction symbols, respectively (cf. [6] for a related solvable class). In this paper we show that the decision problem is unsolvable for formulas that are like those considered by Maslov except that they have prefixes of the form ∀x∃y1 … ∃yk∀z. This settles the decision problems for all prefix classes of formulas for formulas that are in prenex conjunctive normal form in which all disjunctions are binary (have just two terms). In our concluding section we report results on decision problems for related classes of formulas including classes of formulas in languages with identity and we describe some special properties of formulas in which all disjunctions are binary including a property that implies that any proof of our result, that a class of formulas is a reduction class for satisfiability, is necessarily indirect. Our proof is based on an unsolvable combinatorial tag problem.

There are well-known embeddings of intuitionistic logic into S4 and of classical logic into S5. In this paper we give a related embedding of (first order) classical logic directly into (first order) S4, with or without the Barcan formula. If one reads the necessity operator of S4 as ‘provable’, the translation may be roughly stated as: truth may be replaced by provable consistency. A proper statement will be found below. The proof is based ultimately on the notion of complete sequences used in Cohen's technique of forcing [1], and is given in terms of Kripke's model theory [3], [4].

Martin [4, Theorems 1 and 2] proved that a Turing degree a is the degree of a maximal set if, and only if, a′ = 0″. Lachlan has shown that maximal sets have minimal many-one degrees [2, §1] and that every nonrecursive r.e. Turing degree contains a minimal many-one degree [2, Theorem 4]. Our aim here is to show that any r.e. Turing degree a of a maximal set contains an infinite number of maximal sets whose many-one degrees are pairwise incomparable; hence such Turing degrees contain an infinite number of distinct minimal many-one degrees. This theorem has been proved by Yates [6, Theorem 5] in the case when a = 0′.

The need for this theorem first came to our attention as a result of work done by the author [3, Theorem 2.3]. There we looked at the structure / obtained from the recursive functions of one variable under the equivalence relation f ~ g if, and only if, f(x) = g(x) a.e., that is, for all but finitely many x ∈ , where M is a maximal set, and M is its complement. We showed that / 1 ≡ / 2 if, and only if, 1 = m 2, i.e., 1. and 2 have the same many-one degree. However, it might be possible that some Turing degree of a maximal set contains exactly one many-one degree of a maximal set. Theorem 1 was proved to show that this was not the case, and hence that the theory of / is not an invariant of Turing degree.

The first minimal degree construction is due to Spector [7]. To this Sacks [5] has added the priority method of Friedberg [1] and Muchnik [4] to obtain a minimal degree less than 0′. Sacks' methods have been modified in several directions to obtain minimal degrees satisfying various incomparability conditions.

Let be a standard formalization of type theory. In [6] Kreisel introduced N-models for . These are general models in the sense of [1] in which the numerals have their standard denotations.

If ξ is a closed term of we shall denote the object denoted by ξ in the N-model M by ξM. In particular, ξ* is the object denoted by ξ in the standard model of .

In [3] Henkin made the observation that certain second-order existential formulas may be thought of as the Skolem normal forms of formulas of a language which is first-order in every respect except its incorporation of a form of partially-ordered quantification. One formulation of this sort of language is the closure of a first-order language under the formation rule that Qφ is a formula whenever φ is a formula and Q, which is to be thought of as a quantifier-prefix, is a system of partial order whose universe is a set of quantifiers. Although he introduced this idea in a discussion of infinitary logic, Henkin went on to discuss its application to finitary languages, and he concluded his discussion with a theorem of Ehrenfeucht that the incorporation of an extremely simple partially-ordered quantifier-prefix (the quantifiers ∀x, ∀y, ∃v, and ∃w, with the ordering {〈∀x, ∃v〉, 〈∀y, ∃w〉}) into any first-order language with identity gives a language capable of expressing the infinitary quantifier ∃zκ0x.

This paper deals with a fundamental problem in the theory of recursion on initial segments of the ordinal numbers which was originated by Kripke [4] and Platek [8]. Following Kreisel-Sacks [3], we define a notion of relative recursiveness for this abstract recursion theory which allows us to speak of a function ƒ being weakly recursive in a set A via a partial recursive function g; this makes it reasonable to speak of partial recursive functions as ‘reduction procedures’. We say that a reduction procedure g is intrinsically consistent if for any set A there is a partial function ƒ which is weakly recursive in A via g. It is an elementary result of ordinary recursion theory that an arbitrary reduction procedure can be replaced in a uniform manner by an intrinsically consistent reduction procedure without the loss of any function f being reducible to any set A. In §3 we show that for recursion theory on the ordinals less than any infinite cardinal the analogous result is consistent with the axioms of set theory. In §5 we show that for all other cases of abstract recursion theory the analogous result fails in a very strong way to be true.

A set S of degrees is said to be an initial segment if c ≤ d ∈ S→-c∈S. Shoenfield has shown that if P is the lattice of all subsets of a finite set then there is an initial segment of degrees isomorphic to P. Rosenstein [2] (independently) proved the same to hold of the lattice of all finite subsets of a countable set. We shall show that “countable set” may be replaced by “set of cardinality at most that of the continuum.” This result is also an extension of [3, Corollary 2 to Theorem 15], which states that there is a sublattice of degrees isomorphic to the lattice of all finite subsets of 2 N . (A sublattice of degrees is a subset closed under ∪ and ∩; an initial segment closed under ∪ is necessarily a sublattice, but not conversely.)

It seems worth noting that the proof of the present result was preceded in time by our proof [4] of the analogous theorem for hyperdegrees, and is in fact an adaptation of that proof. Thus the present work has been influenced much more directly by the Gandy-Sacks forcing construction of a minimal hyperdegree [1] than by previous work on initial segments of degrees.