In this paper we consider certain formal properties of deductive systems which, in special cases, reduce to the property of ω-consistency; and we then seek to understand the significance of these properties by relating them to the use of models in providing interpretations of the deductive systems.

The notion of ω-consistency arises in connection with deductive systems of arithmetic. For definiteness, let us suppose that the system is a functional calculus whose domain of individuals is construed as the set of natural numbers, and that the system possesses individual constants ν0, ν1, ν2, … such that νi functions as a name for the number i. Such a system is called ω-consistent, if there is no well-formed formula A(x) (in which x is the only free variable) such that A(ν0), A(ν1), A(ν2), … and ∼(x)A(x) are all formal theorems of the system, where A(νi) is the formula resulting from A(x) by substituting the constant νi for each free occurrence of the individual variable x.

Now consider an arbitrary applied functional calculus F, and let Γ be any non-empty set of its individual constants. In imitation of the definition of ω-consistency, we may say that the system F is Γ-consistent, if it contains no formula A(x) (in which x is the only free variable) such that ⊦ A (α) for every constant α in Γ, and also ⊦ ∼(x)A(x) (where an occurrence of “⊦” indicates that the formula which it precedes is a formal theorem). We easily see that the condition of Γ-consistency is equivalent to the condition that the system F contain no formula B(x) such that ⊦ ∼ B(α) for each α in Γ, and also ⊦ (∃x)B(x).

We use some simple facts about the wtt-degrees of r.e. sets together with a construction to answer some questions concerning the join and meet operators in the r.e. degrees. The construction is that of an r.e. Turing degree a with just one wtt-degree in a such that a is the join of a minimal pair of r.e. degrees. We hope to illustrate the usefulness of studying the stronger reducibility orderings of r.e. sets for providing information about Turing reducibility.

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4, K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if l1 and l2 are classes of transitive frames such that their depth cannot be bounded by any fixed n < ω, then the logic of the class {5ℑ1 × ℑ2 ∣ ℑ1 ∈ l1, ℑ2, ∈ l2} is undecidable. (On the contrary, the product of, say, K4 and the logic of all transitive Kripke frames of depth ≤ n, for some fixed n < ω, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and Π11-complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.

The present work may perhaps be seen as a point of convergence of two historically distinct sequences of results. One sequence of results started with the work of Tennenbaum [59] who showed that there could be no nonstandard recursive model of the system PA of first order Peano arithmetic. Shepherdson [65] on the other hand showed that the system of arithmetic with open induction was sufficiently weak to allow the construction of nonstandard recursive models. Between these two results there remained for many years a large gap occasioned by a general lack of interest in weak systems of arithmetic. However Dana Scott observed that the addition alone of a nonstandard model of PA could not be recursive, while more recently McAloon [82] improved these results by showing that even for the weaker system of arithmetic with only bounded induction, neither the addition nor the multiplication of a nonstandard model could be recursive.

Another sequence of results starts with the work of Lessan [78], and independently Jensen and Ehrenfeucht [76], who showed that the structures which may be obtained as the reducts to addition of countable nonstandard models of PA are exactly the countable recursively saturated models of Presburger arithmetic. More recently, Cegielski, McAloon and the author [81] showed that the above result holds true if PA is replaced by the much weaker system of bounded induction.

However in both the case of the Tennenbaum phenomenon and in that of the recursive saturation of addition the problem remained open as to how strong a system was really necessary to generate the required phenomenon. All that was clear a priori was that open induction was too weak to produce either result.

Let κ < λ be regular uncountable cardinals. Using a finite support iteration (in fact a matrix iteration) of ccc posets we obtain the consistency of . If μ is a measurable cardinal and μ < κ < λ, then using similar techniques we obtain the consistency of .

We show that the modal propositional logic G, originally introduced to describe the modality “it is provable that”, is also sound for various interpretations using filters on ordinal numbers, for example the end-segment filters, the club filters, or the ineffable filters. We also prove that G is complete for the interpretation using end-segment filters. In the case of club filters, we show that G is complete if Jensen's principle □κ holds for all κ < ℵω; on the other hand, it is consistent relative to a Mahlo cardinal that G be incomplete for the club filter interpretation.

Throughout this paper, the letters α, β, κ, λ will denote infinite cardinals. Other Greek letters range over the ordinals.

The following definition is taken from Chang [1].

We interpret the basic notions of topological dynamics in the model-theoretic setting, relating them to generic types of definable group actions and their generalizations.

We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a classification of the reducts of the logic of equality. It turns out that there exists a continuum of such reducts. Equivalently, expressed in the language of universal algebra, we classify those locally closed clones over a countable domain which contain all permutations of the domain.

In this note is proved the following:

Theorem. Iƒ A × B is universal and one oƒ A, B is r.e. then one of A, B is universal.

Let α, τ be 1-argument recursive functions such that x goes to (σ(χ), τ(χ)) is a (1–1) map of the natural numbers onto all ordered pairs of natural numbers. A set A of natural numbers is called universal if every r.e. set is (many-one) reducible to A; A × B is called universal if the set

A modal theory Z using the Guaspari witness comparison signs ≤, < is developed. The theory Z is similar to, but weaker than, the theory R of Guaspari and Solovay. Nevertheless, Z proves the independence of the Rosser fixed-point. A Kripke semantics for Z is presented and some arithmetical interpretations of Z are investigated. Then Z is enriched to ZI by adding a new modality sign for interpretability and by axioms expressing some facts about interpretability of theories. Two arithmetical interpretations of ZI are presented. The proofs of the validity of the axioms of ZI in arithmetical interpretations use some strengthening of Solovay's result about interpretability in Gödel-Bernays set theory.

This paper is a continuation of An abstract form of the Church-Rosser theorem. I (this Journal, vol. 35 (1969), pp. 545–560). In Part I, the Church-Rosser property was deduced from abstract premises (A1)–(A8). The original draft of Part II contained some applications of this result, and a fairly simple abstract result by which the Church-Rosser property could be extended from λβ-reduction to λβη-reduction (Curry's notation [3, Chapter 3]). But since this draft was written, these results have been obtained independently and improved by other workers, and a simple and natural new proof for λβ-reduction has been discovered by W. W. Tait and P. Martin-Löf (see §11 later, and [17, §2.4.3]).

So the main purpose of the present Part II is merely to justify the claim in Part I that the abstract theorem does cover the case of λβ-reduction (and various modifications). I shall also include a summary of the main kinds of Church-Rosser proofs. The paragraph and theorem numbers in Part II will continue from those of Part I.

In §§5 and 6 below, Theorem 1 will be specialised to reductions defined by replacements of parts of expressions by others (Theorems 2 and 2A). At the end of §6 an important subclass of such reductions will be treated (Theorem 3).

In §7, Theorem 3 will be applied to prove the Church-Rosser property for combinatory weak reduction [10, §11B], with or without type-restrictions and extra “arithmetical” reduction-rules (Theorems 4 and 5). (In the original draft Theorem 5 was deduced directly from Theorem 2A; the present intervening Theorem 3 is an independent result of B. Rosen [7].)

Let and be two countable relational models of the same first order language. If the models are nonisomorphic, there is a unique countable ordinal α with the property that

i.e. and are L∞ω-equivalent up to quantifier-rank α but not up to α + 1. In this paper we consider models and of cardinality ω1 and construct trees which have a similar relation to and as a above. For this purpose we introduce a new ordering T ≪ T′ of trees, which may have some independent interest of its own. It turns out that the above ordinal α has two qualities which coincide in countable models but will differ in uncountable models. Respectively, two kinds of trees emerge from α. We call them Scott trees and Karp trees, respectively. The definition and existence of these trees is based on an examination of the Ehrenfeucht game of length ω1 between and . We construct two models of power ω1 with mutually noncomparable Scott trees.

This article is a continuation of our search for tautologies that are hard even for strong propositional proof systems like EF. cf. [14, 15]. The particular tautologies we study, the τ-formulas. are obtained from any /poly map g; they express that a string is outside of the range of g, Maps g considered here are particular pseudorandom generators. The ultimate goal is to deduce the hardness of the τ-formulas for at least EF from some general, plausible computational hardness hypothesis.

In this paper we introduce the notions of pseudo-surjective and iterable functions (related to free functions of [15]). These two properties imply the hardness of the τ-formulas from the function but unlike the hardness they are preserved under composition and iteration. We link the existence of maps with these two properties to the provability of circuit lower bounds, and we characterize maps g yielding hard τ-formulas in terms of a hitting set type property (all relative to a propositional proof system). We show that a proof system containing EF admits a pseudo-surjective function unless it simulates a proof system WF introduced by Jeřábek [11]. an extension of EF.

We propose a concrete map g as a candidate function possibly pseudo-surjective or free for strong proof systems. The map is defined as a Nisan-Wigderson generator based on a random function and on a random sparse matrix. We prove that it is iterable in a particular way in resolution, yielding the output/input ratio n3 −ε (that improves upon a direct construction of Alekhnovich et al. [2]).

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.

Recall that a theory is said to be almost strongly minimal if in every model every element is in the algebraic closure of a strongly minimal set. In 1970 Hodges and Macintyre conjectured that there is a natural number n such that every ℵ0-categorical almost strongly minimal theory is Σn axiomatizable. Recently Ahlbrandt and Baldwin [A-B] proved that if T is ℵ0-categorical and almost strongly minimal, then T is Σn axiomatizable for some n. This result also follows from Ahlbrandt and Ziegler's results on quasifinite axiomatizability [A-Z]. In this paper we will refute Hodges and Macintyre's conjecture by showing that for each n there is an ℵ0-categorical almost strongly minimal theory which is not Σn axiomatizable.

Before we begin we should note that in all these examples the complexity of the theory arises from the complexity of the definition of the strongly minimal set. It is still open whether the conjecture is true if we allow a predicate symbol for the strongly minimal set.

We will prove the following result.

Theorem. For every n there is an almost strongly minimal ℵ0-categorical theory T with models M and N such that N is Σn elementary but not Σn + 1 elementary.

To show that these theories yield counterexamples to the conjecture we apply the following result of Chang [C].

Theorem. If T is a Σn axiomatizable theory categorical in some infinite power, M and N are models of T and N is a Σn elementary extension of M, then N is an elementary extension of M.

In previous papers, Post, Webb, Götlind and the present author have described some Sheffer functions (in Swift's terminology, “independent binary generators”) in m-valued logic. Professor J. Dean Swift has recently isolated the symmetric Sheffer functions of 3-valued logic. In the present paper, we will prove some properties of Sheffer functions in m-valued logic and isolate all of the Sheffer functions of 3-valued logic.

Before we proceed we will define some terms which we will find convenient. A set of functions in m-valued logic is functionally complete, if the set of the functions which can be defined explicitly from the functions of the set is exactly the set of all functions of m-valued logic. A function is functionally complete, if its unit set is functionally complete. A Sheffer function is a two-place functionally complete function. If i and j are truth values (1 i, j ≤ m), we will say i ~ j (D), if D is a decomposition of the truth values 1, …, m into 2 or more disjoint non-empty classes and i and j are elements of the same class. A binary function f(p, q) satisfies the substitution law for a decomposition D, if for any truth values h, i, j, k, whenever h ~ j (D) and i~k(D), then f(h, i) ~ f(j, k) (D). The function f(p,q) satisfies the co-substitution law for D, if for any truth values h, i, j, k, whenever f(h, i) ~ f(j, k) (D), then h ~ j (D) or i ~ k (D). We will say f(p, q) has the proper substitution property, if there is a decomposition of the truth values into less than m classes for which it satisfies the substitution law.

Through the ability of arithmetic to partially define truth and the ability of infinite integers to simulate limit processes, nonstandard models of arithmetic automatically have a certain amount of saturation: Any encodable partial type whose formulae all fall into the domain of applicability of a truth definition must, by finite satisfiability and Overspill, be nonstandard-finitely satisfiable—whence realized. This fact was first exploited by A. Robinson, who in Robinson [1963] cited the unrealizability in a given model of a certain encodable partial type to prove Tarski's Theorem on the Undefinability of Truth. A decade later, H. Friedman brought this phenomenon to the public's attention by using it to establish impressive embeddability criteria for countable nonstandard models of arithmetic. Subsequently, Wilkie considered models expandable to “strong theories” and, among such models, complemented Friedman's embeddability criteria with elementary embeddability and isomorphism criteria. Oddly enough, the fact that some kind of saturation property was being employed was not explicitly acknowledged in any of this work.

It is in the unpublished dissertation of Wilmers that these submerged saturation properties first surfaced. [As I have only seen accounts of it (most notably Murawski [1976/1977]) and not the dissertation itself, what I have to say about it will not quite be accurate. (Indeed, the referee has refuted, without providing alternate information, every conjecture I have made about the contents of this thesis.)

Up to now, most constructed calculi had the following common property: Whenever the rules of formation of a calculus laid down that expressions of the designs ‘Pa’, ‘Qa’, ‘Pb’ were sentences—‘P’ and ‘Q’ being first-level one-place predicates, ‘a’ and ‘b’ individual-symbols—, ‘Qb’ was a sentence too, according to the same rules. This self-imposed restriction of the logicians is historically understandable, since calculi of this common feature have a certain simplicity which differently constructed calculi will not have. So far, calculi of this type have proved to be sufficient for the formalization of mathematics and small parts of other sciences. We may ask ourselves, however, whether such a restriction will still be desirable when attempting to construct calculi covering more ground. It is quite possible that insistence on this kind of simplicity will involve a greater complexity in other respects. Inquiry into types of calculi which do not possess this simplicity should therefore be of some interest. To such an inquiry we are led also from another point of view. More and more stress has been laid in recent researches on the construction of calculi which should show close connection with ordinary languages, and it is obvious that ordinary language does not have the mentioned property. To use an example given by Carnap: Whereas ‘This stone is red,’ ‘Aluminium is red,’ ‘This stone weighs five pounds’ are all meaningful sentences of ordinary English, ‘Aluminium weighs five pounds’ is not and it does not matter in this connection whether we formulate this fact by saying that ‘Aluminium weighs five pounds,’ though grammatically an impeccable sentence, is logically meaningless, or whether we prefer the more modern formulation that this word-sequence does not form a sentence at all.