Friedman has posed (see [F, p. 117]) the following problem: “35. Define the set E of expressions by (i) Con is an expression; (ii) if A, B are expressions so are (~ A), (A&B), and Con(A). Each expression ϕ in E determines a sentence ϕ in PA [classical first-order arithmetic] by taking Con* to be “PA is consistent,” ( ~ A) * to be ~ (A*), (A&B)* to be A*&B*, and Con(A)* to be “PA + ‘A*’ is consistent.” The set of expressions ϕ ∈ E such that ϕ* is true is recursive.

The formalized second incompleteness theorem reads

In order to simplify notation, we will reformulate Friedman's problem slightly. Let Con be the usual sentence of PA expressing the consistency of PA, ~ A the negation of A, (A&B) the conjunction of A and B, etc., and Bew(A) the result of substituting the numeral for the Gödel number of A for the free variable in the usual provability predicate for PA. Let Con(A) = ~ Bew(~ A). (Con(A) is equivalent in PA to the usual sentence expressing the consistency of PA + A.) And let the class of F-sentences be the smallest class which contains Con and which also contains ~ A, (A&B) and Con(A) whenever it contains A and B. Since ⊦PA Bew(A) ↔ Bew(B) if ⊦PAA ↔ B, Friedman's problem is then the question whether the class of true F-sentences is recursive.

The answer is that it is recursive. To see why, we need a definition and a theorem.

Definition. An atom is a sentence Conn for some n ≥ 1, where Cont = Con and Conn + 1 = Con(Conn).

Priority arguments have been used to produce r.e. sets whose complements have various properties (e.g., maximal sets, hyperhypersimple sets, etc.). In this paper we use the priority method in the context of certain recursively presented models (e.g., dense unbordered linear orderings, countable atomless Boolean algebras, infinite dimensional vector spaces over a finite field) to produce hypersimple subsets of these models whose complements are closed under algebraic operations and/or whose complements are elementarily isomorphic to certain algebraic substructures. For example, it follows from the results of §3 that there are hypersimple subsets of a countable atomless Boolean algebra (of an infinite dimensional vector space over a finite field) in every nonzero r.e. degree whose complement is a subalgebra (subspace). Also, it follows from the same result that, given any subset P of the rationals Q, there is a hypersimple subset of Q whose complement is order isomorphic to P.

A model M of a theory T in a countable language L is said to be recursively presented if the universe ∣M∣ of M is an initial segment of the natural numbers and the satisfaction relation “a satisfies Φ in M” is recursive (where a is a finite sequence of elements of ∣M∣ and Φ is a formula in L).

A new reduction class is presented for the satisfiability problem for well-formed formulas of the first-order predicate calculus. The members of this class are closed prenex formulas of the form ∀x∀yC. The matrix C is in conjunctive normal form and has no disjuncts with more than three literals, in fact all but one conjunct is unary. Furthermore C contains but one predicate symbol, that being unary, and one function symbol which symbol is binary.

This note describes a simple interpretation * of modal first-order languages K with but finitely many predicates in derived classical second-order languages L(K) such that if Γ is a set of K-formulae, Γ is satisfiable (according to Kripke's 55 semantics) iff Γ* is satisfiable (according to standard (or nonstandard) second-order semantics).

The motivation for the interpretation is roughly as follows. Consider the “true” modal semantics, in which the relative possibility relation is universal. Here the necessity operator can be considered a universal quantifier over possible worlds. A possible world itself can be identified with an assignment of extensions to the predicates and of a range to the quantifiers; if the quantifiers are first relativized to an existence predicate, a possible world becomes simply an assignment of extensions to the predicates. Thus the necessity operator can be taken to be a universal quantifier over a class of assignments of extensions to the predicates. So if these predicates are regarded as naming functions from extensions to extensions, the necessity operator can be taken as a string of universal quantifiers over extensions.

The alphabet of a “finite” modal first-order language K shall consist of a non-empty countable set Var of individual variables, a nonempty finite set Pred of predicates, the logical symbols ‘¬’ ‘∧’, and ‘∧’, and the operator ‘◊’. The formation rules of K generate the usual Polish notations as K-formulae. ‘ν’, ‘ν1’, … range over Var, ‘P’ over Pred, ‘A’ over K-formulae, and ‘Γ’ over sets of K-formulae.

Let Kr be the class of all those quantificational formulas whose matrices are conjunctions of binary disjunctions of signed atomic formulas. Decision problems for subclasses of Kr do not invariably coincide with those for the corresponding classes of quantificational formulas with unrestricted matrices; for example, the ∀∃∀ prefix subclass of Kr is solvable, but the full ∀∃∀ class is not ([AaLe],- [KMW]). Moreover, the straightforward encodings of automata which have been used to show the unsolvability of various subclasses of Kr ([Aa], [Bö], [AaLe]) yield but little information about signature subclasses, i.e. subclasses determined by the number and degrees of the predicate letters occurring in a formula. By a new and highly complex construction Theorem 1 establishes the best possible result on classification by signature.

Theorem 1. Let C be the class of all formulas in Kr with a single predicate letter, which is dyadic; then C is a reduction class for satisfiability.

Thus a signature subclass of Kr is solvable just in case the corresponding class of unrestricted quantificational formulas is solvable, to wit, just in case no predicate letter of degree exceeding one may occur. To obtain a richer classification by signature we consider further restrictions on the matrix. Let Or be the class of formulas in Kr having disjunctive normal forms with only two disjuncts. Theorem 2 sharpens Orevkov's proof of the unsolvability of Or ([Or]; see also [LeGo]).

Theorem 2. Let D be the class of formulas in Or with just two predicate letters, both pentadic; then D is a reduction class for satisfiability.

Let be a finite set of (nonlogical) predicate symbols. By an -structure, we mean a relational structure appropriate for . Let be the set of all -structures with universe {1, …, n}. For each first-order -sentence σ (with equality), let μ n (σ) be the fraction of members of for which σ is true. We show that μ n (σ) always converges to 0 or 1 as n → ∞, and that the rate of convergence is geometrically fast. In fact, if T is a certain complete, consistent set of first-order -sentences introduced by H. Gaifman [6], then we show that, for each first-order -sentence σ, μ n (σ) → n 1 iff T ⊩ ω. A surprising corollary is that each finite subset of T has a finite model. Following H. Scholz [8], we define the spectrum of a sentence σ to be the set of cardinalities of finite models of σ. Another corollary is that for each first-order -sentence a, either σ or ˜σ has a cofinite spectrum (in fact, either σ or ˜σ is “nearly always“ true).

Let be a subset of which contains for each in exactly one structure isomorphic to . For each first-order -sentence σ, let ν n (σ) be the fraction of members of which a is true. By making use of an asymptotic estimate [3] of the cardinality of and by our previously mentioned results, we show that v n(σ) converges as n → ∞, and that lim n ν n (σ) = lim n μ n (σ).If contains at least one predicate symbol which is not unary, then the rate of convergence is geometrically fast.

We are concerned in this paper with infinite binary sequences which are noncomplex in the sense that their minimal-program complexity (i.e., the lengths of shortest programs for computing their finite initial segments), as a function of the lengths of their initial segments, grows arbitrarily (in an effective sense) slowly. Indeed, the existence of such sequences which are also nonrecursive raises some interesting questions concerning the notion of computability itself. Our first task is to give a characterization of these sequences which does not directly involve the notions of complexity theory. Although these characterizations do involve the primitives of recursive function theory, they do not involve the types of properties which one usually encounters there. While a closer connection is still hoped for, the lack of one is not entirely unexpected. For example, except for the trivial case of degree 0, there is no general correlation between program complexity and degrees of unsolvability. The reason, roughly, is this: even though the inequality deg (f) ≤ deg (g) expresses the relative information between f and g (in the sense that if one knows g then one can compute f), it is a qualitative sort of information. The minimal-program complexity is used as a measure of algorithmic information content and as such is quantitative.

The second task of this paper is to present an example of one of these sequences which to its credit possesses a fairly long list of interesting properties, not the least attractive of which is that, though nonrecursive, it is very simple to describe. In fact this sequence has occurred previously in the literature. It is the characteristic sequence of the set of busy beaver numbers first studied by T. Rado [13]. Of particular interest to the discussion in the last section of this paper concerning the notion of computability is the fact that all the initial segments of this sequence are computable by arbitrarily short programs each of which is defined on all inputs and runs very quickly.

This paper answers some questions which naturally arise from the Spector-Gandy proof of their theorem that the π1 1 sets of natural numbers are precisely those which are defined by a Σ1 1 formula over the hyperarithmetic sets. Their proof used hierarchies on recursive linear orderings (H-sets) which are not well orderings. (In this respect they anticipated the study of nonstandard models of set theory.) The proof hinged on the following fact. Let e be a recursive linear ordering. Then e is a well ordering if and only if there is an H-set on e which is hyperarithmetic. It was implicit in their proof that there are recursive linear orderings which are not well orderings, on which there are H-sets. Further information on such nonstandard H-sets (often called pseudohierarchies) can be found in Harrison [4]. It is natural to ask: on which recursive linear orderings are there H-sets?

In Friedman [1] it is shown that there exists a recursive linear ordering e that has no hyperarithmetic descending sequences such that no H-set can be placed on e. In [1] it is also shown that if e is a recursive linear ordering, every point of which has an immediate successor and either has finitely many predecessors or is finitely above a limit point (heretofore called adequate) such that an H-set can be placed on e, then e has no hyperarithmetic descending sequences. In a related paper, Friedman [2] shows that there is no infinite sequence xn of codes for ω-models of the arithmetic comprehension axiom scheme such that each x n+ 1 is a set in the ω-model coded by xn , and each x n+1 is the unique solution of P(xn , x n+1) for some fixed arithmetic P.

One of the earliest goals of modern logic was to characterize familiar mathematical structures up to isomorphism by means of properties expressed in a first order language. This hope was dashed by Skolem's discovery (cf. [6]) of a nonstandard model of first order arithmetic. A theory T such that any two of its models are isomorphic is called categorical. It is well known that if T has any infinite models then T is not categorical. We shall regain categoricity by

(i) enlarging our language so as to allow expressions of infinite length, and

(ii) enlarging our class of isomorphisms so as to allow isomorphisms existing in some Boolean valued extension of the universe of sets.

We suggest the name “approximation theorems” for a new kind of theorems which are strong versions of preservation theorems. A typical preservation theorem has the form:

A sentence φ is preserved by the relation R (i.e. and imply ) iff there exists φ* ϵ Φ such that ⊧φ↔ φ*

where R is a relation between structures and Φ is a class of sentences (depending, of course, on R). Usually, Φ is described in syntactical terms and it is easy to see that every element of it is, indeed, preserved by R. A typical approximation theorem has the form:

For every sentence Φ there is a sentence Φ* ϵ Φ (the “approximation” of Φ) such that, for all sentences δ which are preserved under R,

(a) if ⊧δ → φ then ⊧δ → φ* and

(b) if ⊧φ → δ then ⊧φ* → δ.

An approximation theorem obviously implies the corresponding preservation theorem.

The first approximation theorem was proved by Vaught in [14] (see Corollary 2.3 below). That paper inspired the present one. Vaught's result is stated in topological terms. It says that for each Borel set B there is an invariant Borel set B* explicitly defined by an L ω1ω sentence, such that B − ⊆ B* ⊆ B + where B − (B +) is the largest (smallest) invariant set included in (containing) B.

In March 1973, W. Veldman [1] discovered that, by a slight modification of a Kripke-model, it was possible to give an intuitionistic proof of the completeness-theorem for the intuitionistic predicate calculus (IPC) with respect to modified Kripke models. The modification was the following: Let f represent absurdity, then we allow the possibility that and we agree that, for all sentences ϕ, , if . Just one modified Kripke model is constructed such that validity in implies derivability in IPC. While usually one thinks of as some subset of ⋃ n Nat n and of as the discrete natural ordering in ⋃ n Nat n, in Veldman's model , is a spread and , where Γα and Γβ are sets of sentences associated with α, resp. β, is a nondiscrete ordering.

In the completeness-proofs, both for Beth and for Kripke models that we present here, we consider only models over ⋃n Nat n, with the natural discrete ordering and we need validity in all models, not just in one, to get derivability in IPC. Also we have to modify the definition of a model in a somewhat different way than Veldman did. We agree that if ∨s[M⊨s f], then M⊨sϕ for each s ∈ ⋃n Nat n and for each sentence ϕ.

One can view a single model of the type constructed in [1] as the result of throwing together all the models of (the type constructed in) this paper into one big model, which has the somewhat strange properties mentioned above.

As has been shown by the investigations of some mathematicians, there are numerous analogies between forcing and omitting types. Evidence of that can also be found in the application of forcing to model theory. Both methods use the Rasiowa-Sikorski lemma on the existence in a Boolean algebra of an ultrafilter intersecting every dense set from a given denumerable family.

In this paper we will not use the terms Cohen forcing and omitting types in their original sense. We shall deal mainly with the Scott-Boolean kind of forcing as a transformation of Cohen's idea and with methods used in logic that consist in finding a suitable ultrafilter in the Lindenbaum-Tarski algebra for a given theory and defining canonical models—under the name of omitting types.

The two methods will be confronted to show that Cohen's forcing stems from logical methods. Attention will also be drawn to some differences between forcing in set theory and the general methods of logic.

In logic we construct a model by defining relations in a set of constants. In particular when defining a model for set theory we define a certain relation E in a set of constants. It is usually immaterial what E is, in particular whether it is the true relation of membership up to isomorphism.

Craig showed in [3] that Beth's theorem fails for 2nd order logic. This is so since the syntax for 2nd order logic can be represented in the structure of natural numbers and itself can be characterized in 2nd order logic. Thus the satisfaction relation S is implicitly definable yet not explicitly definable (by a Tarski diagonal argument) and Beth fails. Kreisel pointed out in a review of Craig's paper that a similar argument shows that Beth's theorem fails for ω-logic or for any logic whose syntax can be represented in and in which can be characterized. In this paper we use the abstract model-theoretic notions of truth adequacy, truth-maximality and truth-completeness developed by Feferman in [4] to prove the following generalization of Craig's result: If L is a truth-complete logic, then no structure in which the syntax is represented is L-characterizable. This is applied via a corollary to give new examples of failures of Beth's theorem. Another way to construe this result is that truth-complete logics L have the desirable model-theoretic property (see [5]) that the structure in which the syntax is represented is not generalized finite (interpreting generalized finite as L-characterizability).

Since the basic notions of [4] are defined in terms of many-sorted logics, we will consider all our logics to be many-sorted.

The notions of sets of reals being κ-Souslin (κ a cardinal) and admitting a λ-scale (λ an ordinal) are due respectively to D. A. Martin and Y.N. Moschovakis. A set is ω-Souslin if and only if it is Σ1 1 (analytic). We show that a set is ω-Souslin if and only if it admits an (ω + l)-scale. Jointly with Martin and Solovay we show that if κ is uncountable and has cofinality ω, then being κ-Souslin is equivalent to admitting a κ-scale. Our results together with those of Kechris give a new simultaneous characterization of Σ1 1 and Δ1 1 (Borel) sets (a set is Σ1 1 if it admits an (ω + 1)-scale and Δ1 1 if it admits an ω-scale) and determine completely the relation between the κ-Souslin sets and the sets admitting λ-scales.

The existence of an ω2-Souslin tree will be proved (Theorem 2.2 or §3) from the Generalized Continuum Hypothesis (GCH) plus Jensen's combinatorial principle □ω1. Thus, it follows from Jensen's 1.4(2) that the consistency of the formal theory T given by ZFC + GCH + “ω2-Souslin Hypothesis” implies the consistency of ZFC + “there exists a Mahlo cardinal.” So one does not hope to prove the consistency of this T relative to the consistency of ZFC + “there is an inaccessible cardinal, hence there are transitive models of ZFC.”

Silver [5, Theorem 5.8] has shown that the consistency of ZFC + “there is a weakly compact cardinal” implies the consistency of ZFC + not GCH + “there is no ω2-Aronszajn tree, hence no ω2-Souslin tree”; this is one reason why we deal with GCH here. Jensen has shown that the consistency of ZFC implies the consistency of ZFC +GCH + “ω1-Souslin Hypothesis.”

In the preliminary §1, we state some definitions and known results about trees and some of Jensen's combinatorial principles, including □ and ◇*(E).

Our main Lemma 2.1 states (a fortiori) that GCH implies ◇* at ω-cofinal elements of ω2 (i.e., in our notation, ◇*(E(ω) ∩ ω2)). From Lemma 2.1 and the known facts of §1, it is proved (2.5) that if □ k , the cofinality cf(k)> ω, and GCH, then there is a k +-Souslin tree. For k = ω1, this implies the result mentioned above for ω2-Souslin trees.

Validity in recursive structures was investigated by several authors. Kreisel [10] has shown that there exists a consistent sentence of classical predicate calculus (CPC) that does not possess a recursive model. The sentence is a conjunction of the axioms of a variant of Bernays set theory, including the axiom of infinity. The language contains additional constants besides ϵ. Later Kreisel [2] and Mostowski [3] presented a sentence (not possessing recursive models) which was a conjunction of axioms of a variant of Bernays set theory without the axiom of infinity but still with additional constants besides ϵ. Later Mostowski [4] improved the result by giving a sentence which can be demonstrated in Heyting arithmetic to be consistent and to have no recursive models. Rabin [6] obtained a simple proof that some sentence of set theory with the single nonlogical constant ϵ does not have any recursively enumerable models.

More generally, Mostowski [5] has shown that the set of all sentences valid in all RE models is not arithmetical and Vaught [1] improved this result by showing that it holds for a language of one binary relation. In fact, Vaught gives· a way of translating n-place relations to 2-place ones that preserves the RE characteristic of the model. For further results pertaining to recursive models see Vaught [1].