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.

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.

In [1], Sacks points out that there is one fundamental question: which true statements of ordinary recursion theory remain true when appropriately extended to metarecursion theory?

A particular interest is taken in the question [1]:

Q6. How does one define the jump operator for metarecursion theory? (A satisfactory definition should have the property that if A is metarecursive in B, then the jump of A is metarecursive in the jump of B.)

In [2], Kreisel and Sacks give some definitions of predicates and functions analogous to those of Kleene as follows:

The T-predicate of [2] is analogous to that of Kleene [3]. Its definition is

where e is the Gödel number of a finite system of equations E and t(e, s) is a special metarecursive function which indexes “deductions” from E.

U(e, s) is a metarecursive function such that if t(e, s) = 〈e, M, N, x, y〉, then U(e,s) = y.

Two partial functions {e} s and {e} are

Then e is intrinsically consistent if for all x, s 1 and s 2, if t(e, S 1) = 〈e, M 1 N 1, x, y 1〉, t(e, s 2) = 〈e, M 2, N 2, x, y 2〉 and (M 1 ∪ M 2) ∩ (N 1 ∪ N 2) = ∅, then y 1 = y 2.

The enumeration, given a first-order sentence , of all sentences deducible from in the first-order predicate calculus, and the enumeration, given a non-negative integer n, of the recursively enumerable set Wn, are two well-known examples of effective processes. But are these processes really distinct? Indeed, might there not exist a Gödel numbering of the sentences of first-order logic such that for each n, if n is the number assigned to the sentence , then Wn is the set of numbers assigned to all sentences deducible from ? If this were the case, the first sort of enumeration would just be a particular instance of the second.

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.

Let ε stand for the set of all numbers (i.e., nonnegative integers), V for the class of all sets (i.e., subcollections of ε) and for the family of all functions (i.e., mappings from a subset of ε into ε). If ƒ is a function, we write δƒ and ρƒ for its domain and range respectively. The relation of inclusion is denoted by ⊂ and that of proper inclusion by ⊆.

Recursive equivalence types are an effective or recursive analogue of cardinal numbers. They were introduced by Dekker in the early 1950's. The richness of various theories related to the recursive equivalence types is demonstrated in this paper by showing that the theory of any countable relational structure can be embedded in or interpreted in these theories. A more complete summary is presented in the last paragraph of this section.

Let E = {0,1, 2, …} be the natural numbers. If α ⊆ E, β ⊆ E, and there is a 1-1 partial recursive function f such that the image under f of α is β, α and β are called recursively equivalent (see [3]). The recursive equivalence type or RET of α, denoted 〈α〉, is the class of all β recursively equivalent to α. Addition of RETs is defined by 〈α〉 + 〈β〉 = 〈{2x ∣ x ∈ α} ∪ 〈{2x + 1 ∣ x ∈ β}〉. The partial ordering ≤ is defined on the RETs by A ≤ B iff (EC)(A + C = B). An RET, X, is called an isol if X ≠ X + 1 or, equivalently, if no representative of X is recursively equivalent to a proper subset of itself. The isols are thus the recursive analogue of the Dedekind-finite cardinals.

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

If X is a set, [Χ] ω will denote the set of countably infinite subsets of X. ω is the set of natural numbers. If S is a subset of [ω] ω , we shall say that S is Ramsey if there is some infinite subset X of ω such that either [Χ] ω ⊆ S or [Χ] ω ∩ S = 0. Dana Scott (unpublished) has asked which sets, in terms of logical complexity, are Ramsey.

The principal theorem of this paper is: Every Σ 1 1 (i.e., analytic) subset of [ω] ω is Ramsey (for the Σ, Π notations, see Addison [1]). This improves a result of Galvin-Prikry [2] to the effect that every Borel set is Ramsey. Our theorem is essentially optimal because, if the axiom of constructibility is true, then Gödel's Σ2 1 Π2 1 well-ordering of the set of reals [3], having the convenient property that the set of ω-sequences of reals enumerating initial segments is also Σ2 1 ∩ Π2 1, rather directly gives a Σ2 1 ∩ Π2 1 set which is not Ramsey. On the other hand, from the assumption that there is a measurable cardinal we shall derive the conclusion that every Σ 2 1 (i.e., PCA) is Ramsey. Also, we shall explore the connection between Martin's axiom and the Ramsey property.

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

Let be a version of class set theory admitting urelemente, and with AC (= axiom of choice) replaced by AC0 (= axiom of choice for sets of finite sets), ω = nonnegative integers, and Δ = Dedekind cardinals. Let be an arbitrarily quantified positive first order sentence in functors for + and ·. Let ƒ0, … , ƒ κ - 1 be function variables and the universal sentence obtained from by replacing existential quantifiers by the ƒ1 as Skolem functions.

Morley conjectured that if an infinite first-order theory T is categorical in the power |T| > ℵ0, then it has a model of power < |T| Here we affirm this conjecture for the case |T|ℵ0=|T|.

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