In this paper we will investigate closure properties of the class of immune sets and of other, more restricted classes of sets of natural numbers under union and similar operations. Our main theorem states that there exists a hyperhyperimmune set A such that A join A is not hyperhyperimmune. We will prove this result in §3. The remaining questions about closure properties are all much easier and will be answered in §2.

We consider the closure properties which are given in the following

Definition. Let bea. class of subsets of N.

(i) is closed under join, if A join B ∈ whenever A ∈ and B ∈ .

(ii) is closed under self-join, if A join A ∈ whenever A ∈ .

(iii) is closed under union, if A ⋃ B ∈ whenever A ∈ and B ∈ .

(iv) is closed under cartesian product, if A × B ∈ whenever A ∈ and B ∈ .

(v) is closed under cartesian self-product, if A × A ∈ whenever A ∈ .

The almost-finiteness classes we consider are the following:

1 = {X∣X is immune};

2 = {X∣ simple};

3 = {X∣X is hyperimmune};

4 = {X∣ is hypersimple};

5 = {X∣X is strongly hyperimmune};

6 = {X∣ is strongly hypersimple};

7 = {X∣X is hyperhyperimmune};

8 = {X∣X is strongly hyperhyperimmune};

9 = {X∣ is hyperhypersimple};

10 = {X∣X is dense immune};

11 = {X∣ is dense simple}.

The definitions are all contained in Rogers [4, Chapter 12] and/or in Robinson [3]. In addition we could consider the class of -strongly hyperimmune sets and classes defined by lim-properties; see Rogers [4, pp. 243–244]. For other classes, however, such as the class of cohesive sets, the questions become trivial.

Our aim is to establish the table on the next page.

This paper deals with forcing in arithmetic (as first introduced by Feferman [2]) and its connections with recursive function theory. We define for each n ≥ 1 the class of weakly n-generic sets. We prove that these classes merge with the classes of n-generic sets to form the hierarchy suggested by the terminology. Our notation is the same as that of Jockusch [5].

A large number of formal systems based on combinatory logic or λ-calculus have been extended to include first order predicate calculus. Several of these however have been shown to be inconsistent, all, as far as the author knows, in the strong sense that all well formed formulas (which here include all strings of symbols) are provable. We will call the corresponding consistency notion—an arbitrary wff ⊥ is provable—weak consistency. We will say that a system is strongly consistent if no formula and its negation are provable.

Now for some systems, such as that of Kuzichev [11], the strong and weak consistency notions are equivalent, but in the systems of [5] and [6], which we will be considering, they are not. Each of these systems is strong enough to have all of ZF set theory, except Grounding and Choice, interpretable in it, and the system of [5] can also encompass first order arithmetic (see [7]). It therefore seems unlikely that a strong consistency result could be proved for these systems using elementary methods. In this paper however, we prove the weak consistency of both these systems by means that could be formulated, at least within the theory of [5]. The method also applies to the typed systems of Curry, Hindley and Seldin [10] and to Seldin's generalised types [12].

We begin with a simple observation and a simple question. If we fix Th(x), some reasonable formulation of “x is the Gödel number of a theorem of Peano Arithmetic”, then for any sentence σ, Peano Arithmetic proves σ → Th(⌈σ⌉). (Here ⌈σ⌉ is the canonical term denoting the Gödel number of σ.) This observation is crucial to the proof of the Second Incompleteness Theorem. Call ψ a self-prover (with respect to Th(x)) if ψ → Th(⌈ψ⌉) is a theorem of Peano Arithmetic (from now on, PA). Our simple question is this: Does the observation have a converse—must every self-prover be provably equivalent to a sentence? Whatever φ happens to be, the formula φ ∧ Th(⌈φ⌉) is a self-prover. This makes it seem clear that there must exist self-provers which are not provably : We need only use a suitably complicated φ.

Deciding what sort of complication is “suitable” and finding such a φ is surprisingly annoying. Here is a quick example: One might guess that any φ which is unprovable and would work. In that case we could take φ to be CON—that is, ¬Th(⌈0 = 1⌉); but CON ∧ Th(⌈CON⌉) is refutable in PA, so is provably equivalent to the quantifier-free formula 0 = 1.

In his thesis [2] Sy Friedman showed that for any inadmissible ordinal β there is an easily definable β-r.e. degree, 01/2, with β-degree strictly between 0 and 0′. In this paper we define, for some weakly admissible β, a β-r.e. degree 03/4 intermediate between 01/2 and 0′. This definition is given using the machinery developed by Maass [6], [7] to study the β-r.e. degrees.

A weak jump for β-recursion theory, the ½-jump, was first defined by Friedman [4] and has been studied by Sacks and Homer [5]. The degree 03/4 is of interest because of the way it interacts with the half-jump. In particular 03/4 forms the boundary between the half-jump of “hyperregular” and “nonhyperregular” β-r.e. degrees less than 01/2. One consequence of these results is that there are weakly inadmissible β for which either the jump theorem or the density theorem fails.

Much of this paper is based on earlier work in this area by Sy Friedman and Wolfgang Maass. I would like to thank Gerald Sacks for many helpful conversations and comments concerning this work.