We conclude here the treatment of forcing in recursion theory begun in Part I and continued in Part II of [31]. The numbering of sections is the continuation of the numbering of the first two parts. The bibliography is independent.

In Part I our language was a first-order language: the only set we considered was the (set constant for the) generic set. In Part II a second-order language was introduced, and we had to interpret the second-order variables in some way. What we did was to consider the ramified analytic hierarchy, defined by induction as:

A0 = {X ⊆ ω: X is arithmetic},

Aα+1 = {X ⊆ ω: X is definable (in 2nd order arithmetic) over Aα},

Aλ = ⋃α<λAα (λ limit),

RA = ⋃αAα.

We then used (a relativized version of) the fact that (Kleene [27]). The definition of RA is obviously modeled on the definition of the constructible hierarchy introduced by Gödel [14]. For this we no longer work in a language for second-order arithmetic, but in a language for (first-order) set theory with membership as the only nonlogical relation:

L0 = ⊘,

Lα+1 = {X: X is (first-order) definable over Lα},

Lλ = ⋃α<λLα (λ limit),

L = ⋃αLα.

In his excellent review of four notes of Skolem on recursive functions of natural numbers Bernays states: “The question whether every relation y = f(x1,…, xn) with a recursive function ƒ is primitive recursive remains undecided.” Actually, the question is easily answered in the negative by a form of the familiar diagonal argument.

We start with the ternary recursive relation R, referred to in the review, such that R(x, y, 0), R(x, y, 1), … is an enumeration of all binary primitive recursive relations.

We prove that the strong Martin conjecture is false. The counterexample is the first-order theory of infinite atomic Boolean algebras. We show that for this class of Boolean algebras, the classification of their (ω + ω)-elementary theories can be reduced to the classification of the elementary theories of their quotient algrbras modulo the Frechét ideals.

We say that a computably enumerable (c. e.) degree a is plus-cupping, if for every c.e. degree x with 0 < x ≤ a, there is a c. e. degree y ≠ 0′ such that x ∨ y = 0′. We say that a is n-plus-cupping, if for every c. e. degree x, if 0 < x ≤ a, then there is a lown c. e. degree I such that x ∨ I = 0′. Let PC and PCn be the set of all plus-cupping, and n-plus-cupping c. e. degrees respectively. Then PC1 ⊆ PC2 ⊆ PC3 = PC. In this paper we show that PC1 ⊂ PC2, so giving a nontrivial hierarchy for the plus cupping degrees. The theorem also extends the result of Li, Wu and Zhang [14] showing that LC1 ⊂ LC2, as well as extending the Harrington plus-cupping theorem [8].

We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree d if d is the degree of its elementary diagram. We show that if a CAD theory T has a prime model of c.e. degree c, then T has a prime model of strictly lower c.e. degree b, where, in addition, b is low (b′ = 0′), This extends Csima's result that every CAD theory has a low prime model. We also prove a density result for c.e. degrees of prime models. In particular, if c and d are c.e. degrees with d < c and c not low2 (c″ > 0″), then for any CAD theory T, there exists a c.e. degree b with d < b < c such that T has a prime model of degree b, where b can be chosen so that b′ is any degree c.e. in c with d′ ≤ b′. As a corollary, we show that for any degree c with 0 < c < 0′, every CAD theory has a prime model of low c.e. degree incomparable with c. We show also that every CAD theory has prime models of low c.e. degree that form a minimal pair, extending another result of Csima. We then discuss how these results apply to homogeneous models.

One of the early partition relation theorems which include ordinals was the observation of Erdös and Rado [7] that if κ = cf(κ) > ω then the Dushnik–Miller theorem can be sharpened to κ→(κ, ω + 1)2. The question on the possible further extension of this result was answered by Hajnal who in [8] proved that the continuum hypothesis implies ω1 ↛ (ω1, ω + 2)2. He actually proved the stronger result ω1 ↛ (ω: 2))2. The consistency of the relation κ↛(κ, (ω: 2))2 was later extensively studied. Baumgartner [1] proved it for every κ which is the successor of a regular cardinal. Laver [9] showed that if κ is Mahlo there is a forcing notion which adds a witness for κ↛ (κ, (ω: 2))2 and preserves Mahloness, ω-Mahloness of κ, etc. We notice in connection with these results that λ→(λ, (ω: 2))2 holds if λ is singular, in fact λ→(λ, (μ: n))2 for n < ω, μ < λ (Theorem 4).

In [11] Todorčević proved that if cf(λ) > ω then a ccc forcing can add a counter-example to λ→(λ, ω + 2)2. We give an alternative proof of this (Theorem 5) and extend it to larger cardinals: if GCH holds, cf (λ) > κ = cf (κ) then < κ-closed, κ+-c.c. forcing adds a counter-example to λ→(λ, κ + 2)2 (Theorem 6).

Erdös and Hajnal remarked in their problem paper [5] that Galvin had proved ω2→(ω1, ω + 2)2 and he had also asked if ω2→(ω1, ω + 3)2 is true. We show in Theorem 1 that the negative relation is consistent.

The object of this note is to close a slight gap, hitherto seemingly over-looked, in Nicod's derivation from his postulates of the primitives of Principia mathematica. The gap consists in this: Nicod's propositions corresponding to *1·1−*1·6 of the Principia, though they bear the same names and have the same symbol-forms as the Principia propositions, are not precisely *1·1−1·6. Indeed, if we denote Nicod's “p ⊃ q” and “p · q” by “p < q” and “pq” respectively, and if we write p′ for p∣p and p″ for (p′)′ then in terms of the “stroke,” we have

But p ⊃ q and p · q of the Principia are

Accordingly, the Nicod-Principia propositions are not *1·1−*1·6. They are *1·1−*1·6 in which < takes the place of ⊃, and Nicod has not shown us explicitly how to pass from < to ⊃.

It is true that Nicod also proves the following:

i.e.,

This yields: If ⊢· p < q then ⊢· p ⊃ q, and conversely. This would seem to allow passing from < to ⊃ throughout a proposition. But, it is clear, T1 permits this change only in the case of the principal <. The change in the case of a minor < still has to be justified.

Let T be a countable, complete, ω-stable, nonmultidimensional theory. By Lascar [7], in Teq there is in every dimension of T a type with Lascar rank ωα for some α. We give sufficient conditions for α to coincide with the level of that dimension in Pillay's [10] RK-hierarchy of dimensions computed in Teq. In particular, this is fulfilled for modules.

We prove the consistency result from the title. By forcing we construct a model of g = ℵ1, b = cf(Sym(ω)) = ℵ2.