In this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability D, the existence of an RPCF whose word problem is of degree D and an RPCF with axiom whose-decision problem is also of degree D. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees.

The application of priority arguments to study the structure of the upper semilattice of α-r.e. α-degrees for all admissible ordinals α was first done successfully by Sacks and Simpson [5] who proved that there exist incomparable α-r.e. α-degrees. Lerman and Sacks [3] studied the existence of minimal pairs of α-r.e. α-degrees, and proved their existence for all admissible ordinals α which are not refractory. We continue the study of the α-r.e. α-degrees, and prove that no minimal pair of α-r.e. α-degrees can have as least upper bound the complete α-r.e. α-degree.

The above-mentioned theorem was first proven for α = ω by Lachlan [1]. Our proof for α = ω differs from Lachlan's in that we eliminate the use of the recursion theorem. The proofs are similar, however, and a knowledge of Lachlan's proof will be of considerable aid in reading this paper.

We assume that the reader is familiar with the basic notions or α-recursion theory, which can be found in [2] or [5].

Throughout the paper a will be an arbitrary admissible ordinal. We identify a set A ⊆ α with its characteristic function, A(x) = 1 if x ∈ A, and A(x) = 0 if x ∉ A.

If A ⊆ α and B ⊆ α, then A ⊕ B will denote the set defined by

A ⊕ B(x) = A(y) if x = λ + 2z, λ is a limit ordinal, z < ω and y = λ + z,

= B(y) if x = λ + 2z + 1, λ is a limit ordinal, z < ω, and y = λ + z.

A very important example of almost strongly minimal theories are the algebraically closed fields. A. Macintyre has shown [3] that every ω1-categorical field is algebraically closed. Therefore every ω1-categorical field is almost strongly minimal. It will be shown that not every ω1-categorical ring is almost strongly minimal.

Let R0 be the factor ring C[y/(y2), where C[y] is the ring of polynomials in the indeterminate y over the field of complex numbers and (y2) the ideal generated by y2 in C[y].

It is straightforward to prove that R0 has the following properties:

1. R0 is a commutative ring with identity.

2. R0 is of characteristic 0.

3. For every polynomial p(x) = ∑ a1x1 ∈ R0[x] with of ai2 ≠ 0 for some i > 0 there is an a ∈ R0 such that p(a) · p(a) = 0.

4. For all x, y ∈ R0 such that x2 = 0 and y ≠ 0 there exists a z ∈ R0 with y · z = x.

5. There is an x ≠ 0 such that x2 = 0.

These properties can be ∀∃-axiomatised in a countable first order logic (see [4]). Let T be the set of these sentences. With Theorem 7 we get that T is model-complete.

If R is a model of T then I shall denote {a ∈ R ∣ a2 = 0}.

The results that follow are intended to be understood as informal counterparts to formal theorems of Zermelo-Fraenkel set theory with choice. Basic notation not explained here can usually be found in [5]. It will also be necessary to assume a knowledge of the fundamentals of boolean and generic extensions, in the style of Jech's monograph [3]. Consistency results will be stated as assertions about the existence of certain complete boolean algebras, B, C , etc., either outright or in the sense of a countable standard transitive model M of ZFC augmented by hypotheses about the existence of various large cardinals. Proofs will usually be phrased in terms of the forcing relation ⊩ over such an M, especially when they make heavy use of genericity. They are then assertions about Shoenfield-style P -generic extensions M(G), in which the ‘names’ are required without loss of generality to be elements of M B = (V B )M, B is the boolean completion of P in M (cf. [3, p. 50]: the notation there is RO(P)), the generic G is named by Ĝ ∈ M B such that (⟦p ∈ Ĝ⟧ B = p and (cf. [11, p. 361] and [3, pp. 58–59]), and for p ∈ P and c 1, …, cn ∈ M B , p ⊩ φ(c 1, …, cn ) iff ⟦φ(c 1, …, cn )⟧B ≥ p (cf. [3, pp. 61–62]).

Some prior acquaintance with large cardinal theory is also needed. At this writing no comprehensive introductory survey is yet in print, though [1], [10], [12]and [13] provide partial coverage. The scheme of definitions which follows is intended to fix notation and serve as a glossary for reference, and it is followed in turn by a description of the results of the paper. We adopt the convention that κ, λ, μ, ν, ρ and σ vary over infinite cardinals, and all other lower case Greek letters (except χ, φ, ψ, ϵ) over arbitrary ordinals.

This paper is concerned with extending some basic results from classical model theory to modal logic.

In §1, we define the majority of terms used in the paper, and explain our notation. A full catalogue would be excessive, and we cite [3] and [7] as general references.

Many papers on modal logic that have appeared are concerned with (i) introducing a new modal logic, and (ii) proving a weak completeness theorem for it. Theorem 1, in §2, in many cases allows us to conclude immediately that a strong completeness theorem holds for such a logic in languages of arbitrary cardinality. In particular, this is true of S4 with the Barcan formula.

In §3 we strengthen Theorem 1 for a number of modal logics to deal with the satisfaction of several sets of sentences, and so obtain a realizing types theorem. Finally, an omitting types theorem, generalizing the result for classical logic (see [5]) is proved in §4.

Several consequences of Theorem 1 are already to be found in the literature. [2] gives a proof of strong completeness in languages of arbitrary cardinality of various logics without the Barcan formula, and [8] for some logics in countable languages with it. In the latter case, the result for uncountable languages is cited, without proof, in [1], and there credited to Montague. Our proof was found independently.

Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with respect to the complete sets of other reducibilities. It is shown that q-cylindrification is an order-preserving map from the r.e. T-degrees to the r.e. S-degrees. Consequently, T-complete sets are precisely the r.e. sets whose q-cylindrifications are S-complete.

We study in this paper the projective ordinals , where = sup{ξ: ξis the length of a Δn 1prewellordering of the continuum}. These ordinals were introduced by Moschovakis in [8] to serve as a measure of the “definable length” of the continuum. We prove first in §2 that projective determinacy implies , for all even n > 0 (the same result for odd n is due to Moschovakis). Next, in the context of full determinacy, we partly generalize (in §3) the classical fact that δ1 1 = ℵ1 and the result of Martin that δ3 1 = ℵω+1 by proving that , where λ2n+1 is a cardinal of cofinality ω. Finally we discuss in §4 the connection between the projective ordinals and Solovay's uniform indiscernibles. We prove among other things that ∀α(α # exists) implies that every δn 1 with n ≥ 3 is a fixed point of the increasing enumeration of the uniform indiscernibles.

In [4], Kunen used iterated ultrapowers to show that if U is a normal κ-complete nontrivial ultrafilter on a cardinal κ then L[U], the class of sets constructive from U, has only the ultrafilter U ∩ L[U] and this ultrafilter depends only on κ. In this paper we extend Kunen's methods to arbitrary sequences U of ultrafilters (provided that they fulfill a coherency condition) and obtain generalizations of these results (§3). In particular we answer Problem 1 of Kunen and Paris [5] which asks whether the number of ultrafilters on κ can be intermediate between 1 and 22κ. If there is a normal κ-complete ultrafilter U on κ such that {α < κ: α is measurable} ∈ U then there is an inner model with exactly two normal ultrafilters on κ, and if κ is super-compact then there are inner models having κ+ +, κ+ or any cardinal less than or equal to κ normal ultrafilters (§4).

These methods also show that several properties of L which had been shown to hold for L[U] also hold for L[U]: using an idea of Silver we show that in L[U] the generalized continuum hypothesis is true, there is a Souslin tree, and there is a well-ordering of the reals. In addition we generalize a result of Kunen to characterize the countaby complete ultrafilters of L[U].

A finite set of tiles (unit squares with colored edges) is said to tile the plane if there exists an arrangement of translated (but not rotated or reflected) copies of the squares which fill the plane in such a way that abutting edges of the squares have the same color. The problem of whether there exists a finite set of tiles which can be used to tile the plane but not in any periodic fashion was proposed by Hao Wang [9] and solved by Robert Berger [1]. Raphael Robinson [7] gives a more detailed history and a very economical solution to this and related problems; we will assume that the reader is familiar with §4 of [7]. In 1971, Dale Myers asked whether there exists a finite set of tiles which can tile the plane but not in any recursive fashion. If we make an additional restriction (called the origin constraint) that a given tile must be used at least once, then the positive answer is given by the main theorem of this paper. Using the Turing machine constructed here and a more complicated version of Berger and Robinson's construction, Myers [5] has recently solved the problem without the origin constraint.

Given a finite set of tiles T 1, …, Tn , we can describe a tiling of the plane by a function f of two variables ranging over the integers. f(i, j) = k specifies that the tile Tk is to be placed at the position in the plane with coordinates (i, j). The tiling will be said to be recursive if f is a recursive function.

In this sequel to [7] the method of the consistency proof presented there is extended to provide a proof of the ω-consistency of the systems of number theory which were there shown consistent. This proof yields sharp bounds on the ordinal recursions required to establish the κ-consistency of these systems. The main technical innovation of this proof is the extension of what are essentially the methods of Ackermann [1] for handling finite sets of critical formulae of the first and second kinds to apply as well to sets of critical formulae in which the rank ordering is transfinite. The notation, definitions, and results of [7] will be presupposed throughout; we suggest the reader keep a copy of that paper at hand.

The intuitionistic propositional logic I has the following (disjunction) property

.

We are interested in extensions of the intuitionistic logic which are both decidable and have the disjunction property. Systems with the disjunction property are known, for example the Kreisel-Putnam system [1] which is I + (∼ϕ → (ψ ∨ α))→ ((∼ϕ→ψ) ∨ (∼ϕ→α)) and Scott's system I + ((∼ ∼ϕ→ϕ)→(ϕ ∨ ∼ϕ))→ (∼∼ϕ ∨ ∼ϕ). It was shown in [3c] that the first system has the finite-model property.

In this note we shall construct a sequence of intermediate logics Dn with the following properties:

These systems are presented both semantically and syntactically, using the remarkable correspondence between properties of partially ordered sets and axiom schemata of intuitionistic logic. This correspondence, apart from being interesting in itself (for giving geometric meaning to intuitionistic axioms), is also useful in giving independence proofs and obtaining proof theoretic results for intuitionistic systems (see for example, C. Smorynski, Thesis, University of Illinois, 1972, for independence and proof theoretic results in Heyting arithmetic).

In this paper we show the finite controllability of the Maslov class of formulas of pure quantification theory (specified immediately below). That is, we show that every formula in the class has a finite model if it has a model at all. A signed atomic formula is an atomic formula or the negation of one; a binary disjunction is a disjunction of the form A1 ⋁ A2, where A1 and A2 are signed atomic formulas; and a formula is Krom if it is a conjunction of binary disjunctions. Finally, a prenex formula is Maslov if its prefix is ∃···∃∀···∀∃···∃ and its matrix is Krom.

A number of decidability results have been obtained for formulas classified along these lines. It is a consequence of Theorems 1.7 and 2.5 of [4] that the following are reduction classes (for satisfiability): the class of Skolem formulas, that is, prenex formulas with prefixes ∀···∀∃···∃, whose matrices are conjunctions one conjunct of which is a ternary disjunction and the rest of which are binary disjunctions; and the class of Skolem formulas containing identity whose matrices are Krom. Moreover, the following results (for pure quantification theory, that is, without identity) are derived in [1] and [2]: the classes of prenex formulas with Krom matrices and prefixes ∃∀∃∀, or prefixes ∀∃∃∀, or prefixes ∀∃∀∀ are all reduction classes, while formulas with Krom matrices and prefixes ∀∃∀ comprise a decidable class. The latter class, however, is not finitely controllable, for it contains formulas satisfiable only over infinite universes. The Maslov class was shown decidable by Maslov in [11].

In [1] the ω-consistency of arithmetic was proved by a method which yields fine ordinal bounds for κ-consistency, κ ≥ 1. In this paper these bounds are shown to be best possible. The ω-consistency of a number-theoretic system S can be expressed thus: for all sentences ∃xM,

where ProvS is the proof predicate for S, if n is a nonnegative integer then n is the formal numeral (of S) for n, and if G is a formula then ˹G˺ is the Gödel number of G. The κ-consistency of S is the restriction of (1) to Σκ0 sentences ∃xM. The proof in [1] establishes the no-counterexample interpretation of (1), that is, the existence of a constructive functional Φ such that, for all sentences ∃xM, all numbers p, and all functions f,

(see [1, §2]). A functional Φ is an ω-consistency functional for S if it satisfies (2) for all sentences ∃xM, and a κ-consistency functional for S if it satisfies (2) for all Σκ0 sentences ∃xM.

The systems considered in [1] are those obtained from classical first-order arithmetic Z, including the schema for definition of primitive recursive (p.r.) functions, by adjoining, for some p.r. well-founded ordering ≺ of the nonnegative integers, the axiom schema

that is, the least number principle on ≺; it is equivalent to the schema of transfinite induction on ≺.

There is a PCA well-ordering of the real line if and only if there is a real from which every real is constructible.

Let Q be the class of closed quantificational formulas ∀x∃u∀yM without identity such that M is a quantifier-free matrix containing only monadic and dyadic predicate letters and containing no atomic subformula of the form Pyx or Puy for any predicate letter P. In [DKW] Dreben, Kahr, and Wang conjectured that Q is a solvable class for satisfiability and indeed contains no formula having only infinite models. As evidence for this conjecture they noted the solvability of the subclass of Q consisting of those formulas whose atomic subformulas are of only the two forms Pxy, Pyu and the fact that each such formula that has a model has a finite model. Furthermore, it seemed likely that the techniques used to show this subclass solvable could be extended to show the solvability of the full class Q, while the syntax of Q is so restricted that it seemed impossible to express in formulas of Q any unsolvable problem known at that time.

In 1966 Aanderaa refuted this conjecture. He first constructed a very complex formula in Q having an infinite model but no finite model, and then, by an extremely intricate argument, showed that Q (in fact, the subclass Q2 defined below) is unsolvable ([Aa1], [Aa2]). In this paper we develop stronger tools in order to simplify and extend the results of [Aa2]. Specifically, we show the unsolvability of an apparently new combinatorial problem, which we shall call the linear sampling problem (defined in §1.2 and §2.3). From the unsolvability of this problem there follows the unsolvability of two proper subclasses of Q, which we now define. For each i ≥ 0, let Pi be a dyadic predicate letter and let Ri be a monadic predicate letter.

We show that there is a finite set of tiles which can tile the plane but not in any recursive way. This answers a natural sequel to Hao Wang's problem of the existence of a finite set of tiles which can tile the plane but not in any periodic way. In the proof, an elaboration of Robinson's method of transforming origin-constrained problems into unconstrained problems is applied to Hanf's origin-constrained tiling of Part I. We will assume familiarity with §§2, 3, and 7 of [3].

Following Robinson, we will mark the edges of our tiles with symbols and configurations of arrow heads and tails as well as with colors. The matching condition for abutting tiles will be that the symbols on adjacent edges must be identical, every arrow head must match with a tail, every tail with a head, and the colors must be the same. This is, of course, mathematically equivalent to the original condition which involved only colors. A tiling of the plane by a set of tiles is a covering of the plane with translated copies of the tiles such that adjacent edges of abutting tiles satisfy the above matching condition. A set of tiles is consistent if the plane can be tiled by the set. A set of tiles with a designated origin tile is origin-consistent if there is a tiling of the plane with the origin tile at the center.

A square block of tiles is a tiling if every pair of abutting tiles satisfies the above matching condition. If an origin tile has been designated, a block of tiles is an origin-constrained tiling if it is a tiling with the origin tile at the center. Two blocks have the “same” center row if the blocks are of the same size and have identical center rows or if the smaller block's center row is a centered segment of the larger block's center row.

In this paper we will present an application of generalized recursion theory to (noncombinatorial) set theory. More precisely we will combine a priority argument in α-recursion theory with a forcing construction to prove a theorem about the interdefinability of certain subsets of admissible ordinals.

Our investigation was prompted by G. Sacks and S. Simpson asking [6] if it is obvious that there are, for each Σn-admissible α, Σn (over L α ) subsets of α which are Δn -incomparable. If one understands “B is Δn in C” to mean that there are Σn /L α reduction procedures which put out B and when one feeds in C, then the answer is an unqualified “yes.” In this sense “Δn in” is a direct generalization of “α-recursive in” (replace Σ1 by Σn in the definition) and so amenable to the methods of [7, §§3, 5]. Indeed one simply chooses a complete Σn−1 set A and mimics the construction of [6] as modified in [7, §5] to produce two α-A-r.e. sets B and C neither of which is α-A-recursive in the other. By the remarks on translation [7, §3] this will immediately give the desired result for this definition of “Δn in.”

There is, however, the more obvious and natural notion of “Δn in” to be considered: B is Δn in C iff there are Σn and Πn formulas of ⟨L α , C⟩ which define B.

This paper constitutes a short report on the proof theory which developed in the course of an investigation of Essenin-Volpin's foundational studies (see his paper in Infinitistic methods.) The Infinitistic methods paper is primarily concerned with proving the consistency of ZF. His arguments employ some very unusual ideas, especially that of the possibility of different length natural number series. The modal setting which he uses for these ideas and which is really all important is not reflected in the present paper. Only a simple representation of this idea is considered, namely, the use of *N, the nonstandard natural numbers, together with N, the standard natural numbers, to play the roles of a “long” and a “short” number series.

It will be useful to make a few general remarks before beginning on the technical details. These remarks are especially directed towards those people who have read Essenin-Volpin's work, the above-mentioned paper in particular and the one appearing in the proceedings of the 1968 Conference on Intuitionism and Proof Theory at Buffalo, New York.

I want to draw a comparison between the ultra-intuitionistic position of Essenin-Volpin on the one hand with the intuitionistic and realistic positions on the foundations of mathematics on the other hand. Intuitionism makes a transition from the traditional mathematical position (realism) that the rules of mathematical reasoning must be constructed so as to preserve truth (as known by an omniscient being about “the real world” of abstract mathematical objects) to the position that the rules of mathematical reasoning must be in accord with the process of knowing (performed by the “ideal mathematician” or “creative subject”) about the world of mental constructions. Ultra-intuitionism deepens and extends this transition to the position that the fundamental rules of mathematical reasoning must be in accord with processes of knowing accessible to human beings.

It will be shown that propositional tense logic (with the Kripke relational semantics) may be regarded as a fragment of propositional modal logic (again with the Kripke semantics). This paper deals only with model theory. The interpretation of formal systems of tense logic as formal systems of modal logic will be discussed in [6].

The languages M and T, of modal and tense logic respectively, each have a countable infinity of propositional variables and the Boolean connectives; in addition, M has the unary operator ⋄ and T has the unary operators F and P. A structure is a pair <W, ≺<, where W is a nonempty set and ≺ is a binary relation on W. An assignment V assigns to each propositional variable p a subset V(p) of W. Then V(α)£ W is defined for all formulas α of M or T by induction:

We say that α is valid in <W, ≺>, or <W, ≺>, ⊨ α, if ⊩ (α) = W for every assignment V for <W, ≺>. If Γ is a set of formulas of M [T] and α is a formula of M [T], then α is a logical consequence of Γ, or Γ ⊩ α,if α is valid in every model of Γ i.e., in every structure in which all γ ∈ Γare valid.

The purpose of this paper is to investigate continuity properties arising in elementary (i.e., first-order) logic in the hope of illuminating the special status of this logic. The continuity properties turn out to be closely related to conditions which characterize elementary logic uniquely, and lead to various further questions.