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

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

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.

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.

The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter (“successor set”) is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable Boolean algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets.

The notion of a “partition relation”, as it has been studied in the context of set theory for the past several years, was inspired by the following theorem of F. P. Ramsey [14]:

Theorem 0.1. Let n be a positive integer and let {A, B} be a partition of those subsets of the nonnegative integers containing exactly n elements. Then there exists an infinite subset x of the nonnegative integers all of whose n-element subsets are contained in only one of A or B. (Any such set x is said to be “homogeneous” for the partition.)

The hyperarithmetical hierarchy assigns a degree of unsolvability hγ to each constructive ordinal γ. This assignment has the properties that h0 is the recursive degree and hγ+1 is the jump h′γ of hγ. For a limit ordinal λ < ω1 it is not so easy to define hγ. The original definitions used systems of notations for ordinals, see Spector [6]. There are also later notation-free definitions due to Shoenfield (unpublished) and to Hensel and Putnam [4].

The intuitionistic propositional logic I has the following disjunction property

This property does not characterize intuitionistic logic. For example Kreisel and Putnam [5] showed that the extension of I with the axiom

has the disjunction property. Another known system with this propery is due to Scott [5], and is obtained by adding to I the following axiom:

In the present paper we shall prove, using methods originally introduced by Segerberg [10], that the Kreisel-Putnam logic is decidable. In fact we shall show that it has the finite model property, and since it is finitely axiomatizable, it is decidable by [4]. The decidability of Scott's system was proved by J. G. Anderson in his thesis in 1966.