The present work was inspired by Mostowski's paper [3] in which he considers classes of sequences of real numbers, and associated sets of primitive recursive real numbers. The present treatment will differ from that of [3] in that we consider the real numbers in (0, ∞), instead of just those in (0, 1), but this will make little difference. In §1 we develop a general theory, and in §2 we show the relation of this theory to the results contained in [3], and to those of other authors.

Let be the class of recursively enumerable (r.e.) sets with infinite complements. A set M ϵ is maximal if every superset of M which is in is only finitely different from M. In [1] Friedberg shows that maximal sets exist, and it is an easy consequence of this fact that every non-simple set in has a maximal superset. The natural question which arises is whether or not this is also true for every simple set (Ullian [2]). In the present paper this question is answered negatively. However, the main concern of this paper is with demonstrating, and developing a few consequences of, what might be called the “density” of hyperhypersimple sets.

A basic concept of the theory of models is that of elementary equivalence of similar relational systems: two such systems are said to be elementarily equivalent if they satisfy the same first-order statements or, in other words, if they have the same (first-order) complete theory. It is possible to reformulate this notion of elementary equivalence of systems within the framework of algebraic logic by replacing theories by algebraic structures derived from them or more directly from the systems which are models of these theories. To any such theory T (or model of it), is indeed associated a locally finite polyadic algebra with equality, the underlying Boolean algebra of which is simply the well-known Tarski-Lindenbaum algebra of the theory. It is not hard to prove (see Section 6.1) that two systems are elementarily equivalent iff (i.e. if and only if) they have isomorphic polyadic. algebras. The possibility of replacing theories by algebraic structures and of reducing the purely logical concept of elementary equivalence to the algebraic one of isomorphism can be exploited to give a purely algebraic treatment of model-theoretic problems and suggests natural questions concerning these structures. The present paper illustrates that possibility.

This paper was suggested by some work of Alan Ross Anderson on deontic logic. Anderson proposed in [1] that the various deontic modalities (‘it is obligatory that’, ‘it is forbidden that’, ‘it is permitted that’, etc.) should be defined in terms of the ordinary alethic modalities (‘it is necessary that’, ‘it is possible that’, etc.). The definition I shall consider is not in fact Anderson's own, though it is closely related to it. His definition, as set out in [1], involves the idea of an (unspecified) penalty or sanction. A forbidden action is defined as one whose commission entails the application of the sanction; an obligatory action is one whose omission entails the application of the sanction.

This note will characterize those partial functions which are partial recursive under an arbitrary “renaming” of the integers.

The formal result. Let I be the non-negative integers. For any partial function f on I into I, and for any permutation σ of I, let fσ be the partial function which f becomes when the integers are renamed according to σ. That is, let fσ = σfσ−1 in the sense that fσ(x) is defined whenever σ−1(х) ∊ Dom f.

In a work widely quoted and applied,3 Craig has shown that if A and C are any formulas of predicate logic such that A├C, then there is a formula B such that (i) A├B and B├C, and (ii) each predicate symbol occurring in B occurs both in A and in C.4 If, in this theorem, we replace the syntactic notion of derivability, ├, by the semantical notion of consequence, ╞, the resulting proposition is of course equally valid, for by the (strong) completeness theorem of predicate logic5 the relations ├ and ╞ coincide in extension.

The purpose of this paper is to provide a partial logical analysis of a few concepts that may be classified as value concepts or as concepts that are closely related to value concepts. Among the concepts that will be considered are striving for, doing, believing, knowing, desiring, ability to do, obligation to do, and value for. Familiarity will be assumed with the concepts of logical necessity, logical possibility, and strict implication as formalized in standard systems of modal logic (such as S4), and with the concepts of obligation and permission as formalized in systems of deontic logic. It will also be assumed that quantifiers over propositions have been included in extensions of these systems.

Since publication of our account of the early history of the Association for Symbolic Logic in the September 1962 issue of its Journal, the fact has been called to our attention that — because much of the correspondence at that time is no longer available and we had therefore to depend on our memory — we failed to mention an important item of that early history.

This was a letter from Professor Paul Weiss to the Editor of Philosophy of Science, which appeared in the April, 1934, issue of that periodical. This letter, entitled “A Home for Logic,” called attention to the fact that papers on logic were scattered in heterogeneous periodicals, and suggested that the Philosophy of Science Association take under its wing the establishment of a Logical Association.

Following Robinson [3], we say that a first-order sentence S is persistent with respect to a set of sentences K if, whenever S is true in a model M of K, then S is true in every extension of M that is also a model of K. Robinson proved in [3] that:

(T) In order that the sentence S be persistent with respect to the set K it is necessary and sufficient that there be some existential sentence Y such that the sentence S↔Y is deducible from K.

Two questions were left open in [1]. 1) Do W(σ) and W(r) have the same many-one degree for any σ, τ such that ωη+1.2 ≤ σ < τ < ωη+2? 2) Is W(σ) many-one reducible to W(r) for any σ, τ such that ωη+1.2 ≤ σ < τ < ωη+2? We answered the second question affirmatively in [2]. In this paper we answer the first question in the negative. From the results of [1] [2] and this paper we have a complete picture of the many-one degrees of the predicates e ∈ W(σ)

Recent interest in Łukasiewicz' Lℵ0, raises the question whether this axiomatic system can be simplified [2]. It is known that Łukasiewicz' fourth axiom CCCPQCQPCQP is dependent [4] p. 51. The axiomatic system resulting from deleting the fourth axiom from Lℵ0 will be shown to be “minimal” in the sense that the axioms and rules of inference are mutually independent; consequently, no further simplification of Lℵ0, is possible. By switching basic operators, however, simplified modifications of Lℵ0, can be constructed.

As is well known, some paradoxes arise through inadequate analysis of the meanings of terms in a language, an adequate analysis showing that the paradoxes arise through a lack of separation of an object theory and a metatheory. Under such an adequate analysis in which parts of the metatheory are modelled in the object theory, the paradoxes give way to remarkable theorems establishing limitations of the object theory.

Such a modelling is often accomplished by a Gödel numbering. Here we shall use a somewhat different technique in axiomatic set theory, from which we shall reap a few results having the effect of comparing the strength of various axiom schema of comprehension for sets and classes (cf. the numbered results of §§5–7). Similar results were obtained by A. Mostowski [7] using Gödel numbering (cf. 5.3 and 7.3 below).

In this note we partly answer a question left open in [1, p. 52] by proving the following theorem.

Theorem. Supposep0≧2, ωn+1·p0≦σ<ωn+1(p0+1). Then W(σ) is uniformly many-one reducible to W(τ) for τ≧(ωn+1·p0)+1.

To prove this theorem we need only show that there is a recursive function f(e) such that if ∣e∣<σ, then ∣f(e)<(ωn+1·p0)+1, while if ∣e∣ ≮ σ, f(e)∉W. (For the notations see [2].)

This paper answers negatively the chief remaining open questions concerning the separation properties of first-order prefix classes of structures (discussed by Addison [2], pp. 26–37).

1. Preliminaries. The first and second separation properties and the reduction property are defined for arbitrary classes of subsets of an arbitrary set.

This addendum supplies details of the proof in 3.6 of our paper Disjunction and existence under implication in elementary intuition-istic formalisms in this Journal, vol. 27 (1962), pp. 11–18, as promised in Footnote 8 of that paper (p. 16 lines 11 and 16, for “├” read “|”).

A congruence-substitution (or free substitution with change of bound variables) on a formula E with result F consists in, simultaneously, substituting for each of the free variables of E in all its free occurrences a respective term and replacing each bound occurrence of a variable in E by a respective variable, so that (a) each image in F of a free occurrence of a variable in E is free (IM p. 410) and (b) each image in F of a bound occurrence of a variable in E is bound by the corresponding quantifier (i.e. if the j-th quantifier in E binds the original occurrence, then the j-th quantifier in F binds the image).