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].

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) .

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 .

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.

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 this paper we investigate the possibility of extending Friedberg's enumeration of the recursively enumerable (r.e.) sets without duplication [1, p. 312] to meta-recursion theory. It turns out that all of our proposed extensions are impossible save one: the metarecursively enumerable (meta-r.e.) sets can be enumerated without duplication, but only if all the recursive ordinals are used as indices (Theorems 1 and 2). The sets cannot be so enumerated, even if the index set is all recursive ordinals (Theorems 3 and 4). As a corollary, one proves there is no predicate P(n, x) with the property that for each set A there is exactly one integer n for which A = {x ∣ P(n, x)}. We also discuss enumerations of nonempty, infinite, and coinfinite and meta-r.e. sets.

The purpose of this paper is to provide a formal system which is (a) adequate (functionally complete), (b) consistent, and (c) complete, relative to 3-valued logic with one designated value, and for which, furthermore, (d) a simple normal form theorem, and (e) the Craig-Lyndon Interpolation Theorem [1], [2] holds.

It is well known that every field (formally, real field ) has an algebraic closure (real-closure ). This is to say is an algebraic extension of which is algebraically closed (real-closed). Of course, certain properties of carry over to . In particular, M. O. Rabin has proved in [3] that the algebraic closure—which is of course unique up to isomorphism—of a computable field is computable. The purpose of this note is to establish an analogue of Rabin's theorem for formally real fields. It is clear that a direct analogue can be formulated only in the case of ordered fields, for otherwise there may be many (nonisomorphic) such .

The first of this sequence of papers [21] surveyed the progress that has been made in embedding partially ordered sets as initial segments of the uncountable upper semilattice D of degrees of unsolvability. The principal concern of the present and subsequent parts will be with initial segments of the countable upper semilattice D (≦0(1)) of degrees ≦0(1); a summary appeared in [21].

In this paper a number of nonstandard systems of predicate logic with or without identity, are translated with subsystems of applied standard system of predicate logic with identity. There are nonstandard theories of quantification which, following [16], are described as inclusive systems; their theorems are valid in all domains, including the empty domain. Theories of quantification which allow for the substitution of denotationless terms for free variables, are described, following [21], as systems of free logic; they are said to be free of the requirement that all singular terms must have denotations. Free logics and inclusive logics may each be of the other type. A nonstandard theory of identity, described, following [12] as a theory of nonreflexive identity, may be combined with a standard or with a nonstandard theory of quantification. Another kind of nonstandard system of predicate logic examined is a nonstandard version of a system of monadic predicate logic in which a distinction is made between sentence and predicate negation, and which is nonstandard in the sense that the laws relating sentence and predicate negation diverge from the standard ones. In the systems examined, this is combined with an inclusive quantification theory.