In the literature of symbolic logic there are many examples of systems having free variables ranging over truth-values, individuals, or predicates. But, though many such systems are equipped with universal and existential quantifiers (and though many other quantifiers, e.g., for exactly one, are thereby definable), the problem of free variables corresponding to such constants has been neglected.

A partially ordered (p.o.) set (P, ≼) is represented by the recursively enumerable (r.e.) class C if (P, ≼) is order isomorphic to (C, ⊆), that is to the p.o. set consisting of C ordered by the inclusion relation. (P, ≼.) is representable if it is represented by some r.e. class. N will denote the set of natural numbers.

Let ε and Λ denote the sets of all nonnegative integers and isols respectively. Let σ be any subset of ε. Following [6], we shall denote the recursive equivalence type of a by Req(σ) and write σ≃τ when Req(σ) = Req(τ).

Let L be a first order predicate language with two sorts of variables and a single dyadic predicate letter whose first place is to be filled by variables of one sort and whose second place is to be filled by variables of the other sort. In answer to a question of M. H. Löb we show that there is no decision procedure for determining whether or not a sentence of L is universally valid.

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.

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.

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 α ⊂ β.

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.

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

A. N. Prior in [9] has suggested an approach towards a second order logic of existence where, following medieval logicians, we distinguish “between predicates (like ‘is red’, ‘is hard’, etc.) which entail existence, and predicates (like ‘is thought to be red’, ‘is thought of’, etc.) which do not.”2 Let us refer to attributes (including relational attributes) which are designated by the former kind of predicate as existence attributes, or for brevity, e-attributes.

In this paper we continue our investigation of the Dedekind cardinals which was initiated in [2]. Those results are summarized below. Let ω be the finite cardinals and Δ the Dedekind cardinals. In [7] Myhill defined a class of functions ƒ: Χκω→ω, which he called the combinatorial functions, and which he applied to the study of recursive equivalence types.

The question, “What do initial segments of the degrees of unsolvability look like?” has interested recursive function theorists for several years. Sacks [4] hypothesized that Sis a finite initial segment of degrees if and only if S is order-isomorphic to a finite initial segment of some upper semilattice with a least element. Lachlan [2] suggested the generalization, S is an initial segment of degrees if S is order-isomorphic to some countable upper semilattice with both least and greatest elements.