By language we understand a lower predicate calculus with identity and (perhaps) relation and function symbols. It is convenient to allow for more than one sort of variable. Now each individual constant (if there are any) is of a specified sort, the formal expressions R(t1, … tn), f(t1,…, tn) are well formed only if the terms t1, …, tn are of specified sorts determined by the relation symbol R and the function symbol f, and the term f(t1, …, tn) (if well formed) is of a sort determined by f. We admit s = t as well formed, no matter what the sorts of s and t.

An ω-set is a subset of the recursive ordinals whose complement with respect to the recursive ordinals is unbounded and has order type ω. This concept has proved fruitful in the study of sets in relation to metarecursion theory. We prove that the metadegrees of the sets coincide with those of the meta-r.e. ω-sets. We then show that, given any set, a metacomplete set can be found which is weakly metarecursive in it. It then follows that weak relative metarecursiveness is not a transitive relation on the sets, extending a result of G. Driscoll [2, Theorem 3.1]. Coincidentally, we discuss the notions of total and complete regularity. Finally, we solve Post's problem for the transitive closure of weak relative metarecursiveness. We recommend the reader look at pp. 324–328 of the fundamental article [6] of Kreisel and Sacks before proceeding. He will find there a proof of the following very basic fact: a subset of the integers is iff it is metarecursively enumerable (metafinite).

Zdzislaw Cackowski [1], commenting on ideas of Rubinštejn [3], points out that it is possible for two questions with the same answer to have different “content”.1 In the present paper we shall adopt a more general semantical approach to the question of identity of problems and will distinguish between equivalence and isomorphism.

We use the word “number” for “nonnegative integer” and “set” for collection of numbers. The set of all numbers is denoted by ε and the empty set by ο. We write ⊂ for the relation of inclusion and ⊆ for that of proper inclusion. If ƒ is a function from a subset of ε into ε, its domain and range are denoted by δƒ and ρƒ respectively. For any collection Γ of entities, card Γ or card (Γ) stands for the cardinality of Γ. The cardinality of the continuum is denoted by c.

It has been known for some time that there is a primitive recursive permutation of the nonnegative integers whose inverse is recursive but not primitive recursive. For example one has this result apparently for the first time in Kuznecov [1] and implicitly in Kent [2] or J. Robinson [3], who shows that every singularly recursive function ƒ is representable as

where A, B, C are primitive recursive and B is a permutation.

Since Cohen [1] showed the independence of the axiom of choice from the other axioms of ZF, a number of people have used his forcing technique to show how badly choice can fail while certain vestiges of it remain. Many of these arguments involve the introduction of a generic sequence or generic set of generic sets of ordinals into a countable standard model of ZF + V = L. The desired results then follow by the use of clever permutation and forcing arguments. (See Cohen [2, pp. 136–142].)

Given separate though similar proofs of the finite model property for individual modal calculi such as S5, S4, S2, and the Feys-von Wright system T, the problem arises of generalising the arguments and establishing the property for modal calculi en masse. In other words, we would like to be able to show in one fell swoop that any modal calculus satisfying certain general syntactic conditions has the finite model property.

In [3] F. P. Ramsey proved as a theorem of Zermelo-Fraenkel set theory (ZF) with the Axiom of Choice (AC) the following result:

(1) Theorem. Let A be an infinite class. For each integer n and partition {X, Y} of the size n subsets of A, there exists an infinite subclass of A all of whose size n subsets are contained in only one of X or Y.

The uniform halting problem (UH) can be stated as follows.

Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID).

An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [3, p. 118]) we assume that in an ID the tape must be blank except for some finite numbers of squares. If we remove this restriction the UH becomes the immortality problem (IP). The UH should not be confused with the initialised uniform halting problem (whether or not a TM has an immortal ID when started in a specified state) which can easily be shown to be undecidable (see e.g. Minsky [3, p. 151]).

Let q0, q1,… be a standard enumeration of all partial recursive functions of one variable. For each i, let wi = range qi and for any recursively enumerable (r.e.) set α, let θα = {n | wn = α}. If A is a class of r.e. sets, let θA = the index set of A = {n | wn ∈ A}. It is the purpose of this paper to classify the possible recursive isomorphism types of index sets of finite classes of r.e. sets. The main theorem will also provide an answer to the question left open in [2] concerning the possible double isomorphism types of pairs (θα, θβ) where α ⊂ β.

It is known that the theorems of the intuitionist predicate calculus are exactly those formulas which are valid in every Heyting algebra (that is, pseudo-Boolean algebra). The simplest kind of Heyting algebra is a linearly ordered set. This paper concerns the question of determining all formulas which are valid in every linearly ordered Heyting algebra. The question is of interest because it is a particularly simple case intermediate between the intuitionist and classical logics. Also the interpretation of implication is such that in general there exists no nondiscrete Hausdorff topology for which this operation is continuous.

Let ƒ be a real number. It is well known [7] that the set of rational numbers which are less than ƒ is a recursive set if and only if ƒ is representable as the limit of a recursive, recursively convergent sequence of rational numbers. In this paper we replace the condition that the set of rational numbers less than ƒ is recursive by the condition that this set is at various points in the Kleene hierarchy, and we replace the recursive, recursively convergent limit by a variety of other recursive limiting processes.

Consider the predicate of natural numbers defined by:

where R is recursive. If, as usual, the variable ƒ ranges over ωω (the set of functions from natural numbers to natural numbers) then this is just the usual normal form for Π11 sets. If, however, ƒ ranges over 2ω (the set of functions from ω into {0, 1}) then every such predicate is recursively enumerable.3 Thus the second type of formula is generally ignored. However, the reduction just mentioned requires proof, and the proof uses some form of the Brower-König Infinity Lemma.

In [1, §4], my ‘proof’ that GH1 has the finite model property is incorrect; there are considerable obscurities towards the end of §1, particularly on p. 33; and I should have exhibited the finite models for GH1. In §1 of this paper I expand the analysis of the sub-directly irreducible models for GH1 which I give in §1 of [1]. In §2 I give a correct proof that GH1 has the finite model property. In §3 I exhibit these finite models as models on certain ordered sets.

In this paper a special type of co-ordinal, called rich, is studied. Basic properties of rich co-ordinals are proved in §1. In §2 rich co-ordinals are seen to be the co-ordinals occurring in paths which are addition isomorphic to initial segments of the classical ordinals. The results of §1 are applied to obtain information about and examples of such paths. In the next section the order types of rich co-ordinals with a given field, X, is seen to be determined essentially by the finite divisors of X. RETs satisfying various divisibility conditions are constructed in §4.

In this paper we show how the assumption of the generalized continuum hypothesis (GCH) can be removed or partially removed from proofs in Zermelo-Frankel set theory (ZF) of statements expressible in the simple theory of types. We assume the reader is familiar with the latter language, especially with the classification of formulas and sentences of that language into Σκη and Πκη form (cf. [1]) and with how that language can be relatively interpreted into the language of ZF.

The results of the present paper were announced in [1]. The work is divided into our parts. In the first part we define relations (relations between relational struc tures) and we show their connection with the equivalence of the languages LΚ,λ (Theorem 1). The relations generalize the games Gn (n < ω) of Ehrenfeucht (see [2]) and the conditions (i)–(ii) which were used by Karp in [5].

The problem of finding an infinite set of natural numbers which contains no subsets of higher (Turing) degree was first posed by W. Miller [3] and was brought to our attention by C. G. Jockusch, Jr., who proved that such a set, if it existed, could not be hyperarithmetic.2 In this paper we construct an infinite set which is not recursive in any of its coinfinite subsets, and thus contains no subset of higher degree. Our original proof made use of the result (attributed to Ehrenfeucht) that every subset of 2ω which is open (in the standard topology) is “Ramsey”.