Our unexplained notation is that of Rogers [4]. Let P ⊆ 2N × 2N. We call a sequence <An: n ∈ N> of subsets of N a P-sequence iff ∀n(An+1 = the unique B such that P(An, B)).

Theorem. Let P ⊆ 2N × 2N be arithmetical. Then there is no P-sequence <An: n ∈ N> such that ∀n(A′n+1 ≤T An).

This theorem improves a result of Friedman [2] who showed that for no arithmetical P is there a P-sequence <An: n ∈ N> such that An + 1 is a code for an ω-model of the relative arithmetic comprehension schema, and An + 1 is present in the model coded by An, for all n. Other related results are those of Harrison [3], who showed there is a sequence <An: n ∈ N> such that ∀n<A′n + 1 ≤T An>, and of Enderton and Putnam [1], who showed there is no sequence <An: n ∈ N> with ∀n(A′n + 1 ≤T An) and A0 hyperarithmetic.

Our theorem is closely connected to Gödel's second incompleteness theorem. Its proof is a recursion theoretic parallel to the proof of Gödel's theorem. In §2 we draw a version of Gödel's theorem as a corollary to ours.

In this paper we solve some of Pál Erdős's favorite problems on uncountably chromatic graphs. Generalizing a finite graph theory result of Tutte, Erdős and R. Rado showed that for every infinite cardinal κ there exists a triangle-free, κ-chromatic graph of size κ. For κ = ℵ0, Erdős established the existence of ℵ0-chromatic graphs excluding even C4, C5,…, Cn, i.e. circuits up to a given length. For κ < ℵ0 the situation is different. As shown by Erdős and A. Hajnal, a graph is necessarily countably chromatic if it omits any finite bipartite graph. We can, however, exclude any finite list of nonbipartite graphs (this obviously reduces to excluding finitely many odd circuits). They posed an even stronger conjecture, namely, that similar examples must occur in every uncountably chromatic graph. To be specific, they conjectured that for every infinite κ, every κ-chromatic graph contains a κ-chromatic triangle-free subgraph. Here we show that this may not be true for κ = ℵ1 i.e. we exhibit a model where it is false. We must emphasize that the conjecture is probably false already in ZFC, but we have been unable to show this.

We give some general criteria, when κ-complete forcing preserves largeness properties—like κ-presaturation of normal ideals on λ (even when they concentrate on small cofinalities). Then we quite accurately obtain the consistency strength “NSλ is αi-preserving”, for λ > α2.

Our purpose in this note is to study countable ℵ0-categorical structures whose theories are tree-decomposable in the sense of Baldwin and Shelah. The permutation group corresponding to such a structure can be decomposed in a canonical manner into simpler permutation groups in the same class. As an application of the analysis we show that these structures are finitely homogeneous.

This paper contains a result on the reconstruction of certain homogeneous transitive ω-categorical structures from their automorphism group. The structures treated are relational. In the proof it is shown that their automorphism group contains a generic pair (in a slightly non-standard sense, coming from Baire category).

Reconstruction results give conditions under which the abstract group structure of the automorphism group Aut() of an ω-categorical structure determines the topology on Aut(), and hence determines up to bi-interpretability, by [1]; they can also give conditions under which the abstract group Aut() determines the permutation group ⟨Aut (), ⟩. so determines up to bi-definability. One such condition has been identified by M. Rubin in [12], and it is related to the definability, in Aut(), of point stabilisers. If the condition holds, the structure is said to have a weak ∀∃ interpretation, and Aut() determines up to bi-interpretability or, in some cases, up to bi-definability.

A better-known approach to reconstruction is via the ‘small index property’: an ω-categorical stucture has the small index property if any subgroup of Aut() of index less than is open. This guarantees that the abstract group structure of Aut() determines the topology, so if is ω-categorical with Aut() ≅ Aut() then and are bi-interpretable.

The usual formulations of combinatory logic, as in Church [1] or Curry and Feys [2], have no straightforward semantics. This lack complicates the proofs of basic metasystematic results, prevents the perspicuous formalization of combinatory logic as a deductive theory, and makes the combinators unnecessarily difficult to apply to recursion theory or to the foundations of mathematics. In the present paper we shall give a new formulation of combinatory logic, thought of as an abstract theory of rules. At each stage in the development we shall give a precise semantic interpretation for our axioms. We begin with an abstract treatment of the syntax and semantics of a theory of rules. We then specialize to the theory of the combinators and prove a completeness theorem connecting our axioms with our semantics. On this basis we treat functional abstraction, truth-functions, and the representation of partial recursive functions. In the spirit of Church [1, pp. 62–71], we conclude by extending our methods to the treatment of intensional identity.

The theories developed here are part of a simplification of the theory of constructions described in [3]. Their semantics are motivated by the intended interpretation of the theory of constructions. The present paper is selfcontained and can be read without any familiarity with the theory of constructions, although the motivation of several of the notions considered here is given in [3]. In a future publication we will use the results of the present paper as the basis for a detailed study of a simplified form of the theory in [3].

Mr. Shen Yuting, in this Journal, vol. 18, no. 2 (June, 1953), stated a new paradox of intuitive set-theory. This paradox involves what Mr. Yuting calls the class of all grounded classes, that is, the family of all classes a for which there is no infinite sequence b such that … ϵ bn ϵ … ϵ b2ϵb1 ϵ a.

Now it is possible to state this paradox without employing any complex set-theoretical notions (like those of a natural number or an infinite sequence). For let a class x be called regular if and only if (k)(x ϵ k ⊃ (∃y)(y ϵ k · ~(∃z)(z ϵ k · z ϵ y))). Let Reg be the class of all regular classes. I shall show that Reg is neither regular nor non-regular.

Suppose, on the one hand, that Reg is regular. Then Reg ϵ Reg. Now Reg ϵ ẑ(z = Reg). Therefore, since Reg is regular, there is a y such that y ϵ ẑ(z = Reg) · ~(∃z)(z ϵ z(z = Reg) · z ϵ y). Hence ~(∃z)(z ϵ ẑ(z = Reg) · z ϵ Reg). But there is a z (namely Reg) such that z ϵ ẑ(z = Reg) · z ϵ Reg.

On the other hand, suppose that Reg is not regular. Then, for some k, Reg ϵ k · [1] (y)(y ϵ k ⊃ (∃z)(z ϵ k · z ϵ y)). It follows that, for some z, z ϵ k · z ϵ Reg. But this implies that (ϵy)(y ϵ k · ~(ϵw)(w ϵ k · w ϵ y)), which contradicts [1].

It can easily be shown, with the aid of the axiom of choice, that the regular classes are just Mr. Yuting's grounded classes.

Let the prepositional calculus (PC) be cast in the following form: (a) The primitive signs of PC are to be a denumerably infinite hst of propositional letters, the two connectives ‘∼’ and ‘&’, and the two parentheses ‘(‘and’)’; (b) The formulas of PC, referred to hereafter by ‘A’, ‘B’, ‘C’, and ‘D,’ are to be all finite sequences of primitive signs of PC; (c) The well-formed formulas (wffs) of PC are to be all propositional letters, all formulas of the form ∼A, where A is a wff of PC, and all formulas of the form (A&B), where A and B are wffs of PC; (d) (A⊃B) is to be short for ∼(A&∼B), (AνB) short for ∼(∼A&∼B), and (A ≡ B) short for (((A ⊃B)&(B⊃A)).

The purpose of the present paper is to construct a fragment of number theory not subject to Gödel incompletability. Originally the system was designed as a metalanguage for classical mathematics (see section 10); but it now appears to the author worthwhile to present it as a mathematical system in its own right, to serve however rather as an instrument of computation than of proof. Its resources in the latter respect seem very extensive, sufficient apparently for the systematic tabulation of every function used in any but the most recondite physics. The author intends to pursue this topic in a later paper; the present one will simply present the system, along with proofs of consistency and completeness and a few metatheorems which will be used as lemmas for future research.

Completeness is achieved by sacrificing the notions of negation and universal quantification customary in number-theoretic systems; the losses consequent upon this are made good in part by the use of the ancestral as a primitive idea. The general outlines of the system follow closely the pattern of Fitch's “basic logic”; however the latter system uses combinatory operators in place of the variables used in the present paper, and if variables are introduced into Fitch's system by definition their range of values will be found to be much more extensive than that of my variables. The present system K is thus a weaker form of Fitch's system.

It is apparently not known whether or not Fitch's system is complete.

The context for this paper is Feferman's theory of explicit mathematics, T0. We address a problem that was posed in [6]. Let MID be the principle stating that any monotone operation on classifications has a least fixed point. The main objective of this paper is to show that T0 + MID, when based on classical logic, also proves the existence of non-monotone inductive definitions that arise from arbitrary extensional operations on classifications. From the latter we deduce that MID, when adjoined to classical T0, leads to a much stronger theory than T0.

We shall show that certain natural and interesting intervals in the lattice of varieties of representable relation algebras embed the lattice of all subsets of the natural numbers, and therefore must have a very complicated lattice-theoretic structure.

A natural way of studying the computability of an algebraic structure or process is to apply some of the theory of the recursive functions to the algebra under consideration through the manufacture of appropriate coordinate systems from the natural numbers. An algebraic structure A = (A; σ1,…, σk) is computable if it possesses a recursive coordinate system in the following precise sense: associated to A there is a pair (α, Ω) consisting of a recursive set of natural numbers Ω and a surjection α: Ω → A so that (i) the relation defined on Ω by n ≡α m iff α(n) = α(m) in A is recursive, and (ii) each of the operations of A may be effectively followed in Ω, that is, for each (say) r-ary operation σ on A there is an r argument recursive function on Ω which commutes the diagram

wherein αr is r-fold α × … × α.

This concept of a computable algebraic system is the independent technical idea of M.O.Rabin [18] and A.I.Mal'cev [14]. From these first papers one may learn of the strength and elegance of the general method of coordinatising; note-worthy for us is the fact that computability is a finiteness condition of algebra—an isomorphism invariant possessed of all finite algebraic systems—and that it serves to set upon an algebraic foundation the combinatorial idea that a system can be combinatorially presented and have effectively decidable term or word problem.

In this paper, we study partition properties of the set of real numbers. The meaning of “set of real numbers” will vary, referring at times to the collection of sequences of natural numbers, ωω; the collection of infinite sets of natural numbers [ω]ω; the collection of infinite sequences of zeroes and ones, 2ω; or (ω), the power set of ω.

The archetype for the relations is the property: “all sets of reals are Ramsey,” in the notation of Erdős and Hajnal, ω → (ω)ω. This states that for every partition F : [ω]ω → 2, there is an infinite set H ∈ [ω]ω such that F is constant on [H]ω. Like virtually all of the properties we will discuss, it contradicts the Axiom of Choice but is compatible with the principle of dependent choices (DC). DC will be used throughout the paper wihtout further mention.

The properties discussed in this paper will vary in two respects. Some, like ω → (ω)ω, will be incompatible with the existence of an ultrafilter on ω (UF) and some will not. Some are known to be consistent relative to ZF alone, and for some, such as ω → (ω)ω, the question is still open. All properties, however, are true in Solovay's model and hence are consistent relative to Con(ZF + “there exists an inaccessible cardinal”).

We prove two results about the embeddability relation between Borel linear orders: For η a countable ordinal, let 2η (resp. 2< η) be the set of sequences of zeros and ones of length η (resp. < η), equipped with the lexicographic ordering. Given a Borel linear order X and a countable ordinal ξ, we prove the following two facts.

(a) Either X can be embedded (in a (X, ξ) way) in 2ωξ or 2ωξ + 1 continuously embeds in X.

(b) Either X can embedded (in a (X, ξ) way) in 2<ωξ or 2ωξ continuously embeds in X. These results extend previous work of Harrington, Shelah and Marker.

In [9] we have considered a wide class of “well-behaved” reducibilities for sets of reals. In this paper we continue with the study of Borel reducibilities by proving a dichotomy theorem for the degree-structures induced by good Borel reducibilities. This extends and improves the results of [9] allowing to deal with a larger class of notions of reduction (including, among others, the Baire class ξ functions).

An inaccessible cardinal κ is supercompact when (κ, λ)-ITP holds for all λ ≥ κ. We prove that if there is a model of ZFC with infinitely many supercompact cardinals, then there is a model of ZFC where for every n ≥ 2 and μ ≥ ℕn, we have (ℕn, μ)-ITP.

If T is an isol let D(T) be the least set of isols which contains T and is closed under predecessors and the application of almost recursive combinatorial functions. We find an infinite regressive isol T such that the universal theory (with respect to recursive relations and almost recursive combinatorial functions) of D(T) is the same as that of the nonnegative integers.

We investigate strictly positive finitely additive measures on Boolean algebras and strictly positive Radon measures on compact zerodimensional spaces. The motivation is to find a combinatorial characterisation of Boolean algebras which carry a strictly positive finitely additive finite measure with some additional properties, such as separability or nonatomicity. A possible consistent characterisation for an algebra to carry a separable strictly positive measure was suggested by Talagrand in 1980, which is that the Stone space K of the algebra satisfies that its space M(K) of measures is weakly separable, equivalently that C(K) embeds into l∞. We show that there is a ZFC example of a Boolean algebra (so of a compact space) which satisfies this condition and does not support a separable strictly positive measure. However, we use this property as a tool in a proof which shows that under MA + ¬ CH every atomless ccc Boolean algebra of size < c carries a nonatomic strictly positive measure. Examples are given to show that this result does not hold in ZFC. Finally, we obtain a characterisation of Boolean algebras that carry a strictly positive nonatomic measure in terms of a chain condition, and we draw the conclusion that under MA + ¬ CH every atomless ccc Boolean algebra satisfies this stronger chain condition.

The main result of this note is showing that if γ and μ are regular uncountable cardinals with γ ≤ μ then the non-stationary ideal (henceforth the NS ideal) on can be precipitous. This strengthens a result of [1] showing, under the same hypotheses, that a restriction of this ideal can be precipitous. See [1, Theorem 29, p. 36]. In fact, we show that even the strongly NS ideal on is precipitous in our model (since the former ideal is a restriction of the latter, the latter's being precipitous is a stronger assertion).

More precisely, by starting with a model of “ZFC + ‘κ is a supercompact cardinal’ + ‘μ < κ is a regular uncountable cardinal’ ”, we generate a model of ZFC where all cardinals below and including μ are not collapsed and where the NS and strongly NS ideals on Pγμ are precipitous, for all regular uncountable γ which are less than or equal to μ.

As far as consistency strength, we can obtain the same result even if κ is only Woodin in the ground model. However, the proof of this result is more complicated than in the case when κ is a supercompact cardinal. Furthermore, there are essentially no new ideas in adapting the proof relative to a supercompact cardinal to that relative to a Woodin cardinal beyond what appears in, e.g., [2]. We therefore give the complete proof relative to the existence of a supercompact cardinal and then briefly sketch the proof relative to the existence of a Woodin cardinal, using [2] as a reference.