Relative Set Genericity

V.Boutchkova

Abstract A set of natural numbers is generic relatively a set B if and only if it is the preimage of some set A using a B-generic B-regular enumeration such that both A and its complement are e-reducible to B.

Introduction

The genericity and set genericity, as defined by Copestake in [2], are widely explored, and have important role in studying the structure of the enumeration degrees.

In this paper we consider the genericity relative a set of natural numbers, which is in fact a set n-genericity. We refer to some well known facts in this area, most of which can be found in [2] and [1] and can be used to prove similar properties for the relative genericity.

Further we provide some results concerning regular enumerations of the set of the natural numbers that we use to prove a characterization theorem. Concerning the regular enumerations, the used notions and results are taken mostly from Soskov’s course on Recursion Theory and the author’s Master’s Thesis.

Basic notions and definitions

By ω we denote the set of all natural numbers, 2ω denotes the set of all even and 2ω + 1 - the set of all odd natural numbers; by [0..n − 1], where n ∈ ω, we denote the set {x ∈ ω|x < n}. We use N to denote an arbitrary denumerable set.

We use bijective recursive coding of pairs of natural numbers ⟨·, ·⟩, the notation ⟨x_{1}, x_{2}, ..., x_{k}⟩ means ⟨x_{1}, ⟨x_{2}, ..., x_{k}⟩⟩, and of finite sets - D_{v} denotes the finite set with code v. By φ, ψ... we denote partial functions from ω into ω and let Gr(φ) = {⟨x, y⟩ | φ(x) = y} be the graph of the function φ. The notation φ(x)↓ means x ∈ Dom(φ), and φ(x) ↑ means x ∉ Dom(φ). The notation ⊆ is used to denote inclusion between sets, extension between functions, ω-strings or 0-1-strings, considered as finite functions.

By C_{A} we denote the semicharacteristic function of a set A ⊆ ω, and its characteristic function - by χ_{A}, where

χ_{A}(x) = \begin{cases}0 & , if x ∈ A \\ 1 & , if x ∉ A \end{cases}

If each of P and Q denotes some property of natural numbers we use the following abbreviation:

μy_{∈ω}[Q(y)][P (y)] ≃ \begin{cases}μy_{∈ω}[Q(y)&P (y)] & , if ∃y(P (y)&Q(y)) \\ μy_{∈ω}[Q(y)] & , if ∃y(Q(y)) and ¬(P (y)&Q(y)) \\ ↑ & , if ∀y(¬Q(y)) \end{cases} ,

where μy_{∈ω}[Q(y)] is the least y having the property Q.

Let A, B and C... be sets of natural numbers. We use the following standard definitions and notations:

A ≤_{e} B if and only if A = Ψ_{a}(B) for some e-operator Ψ_{a}, defined as follows: Ψ_{a}(B) = {x | ∃v(⟨x, v⟩ ∈ W_{a} & D_{v} ⊆ B)}, where W_{a} is the recursively enumerable set with Gödel code a. A ≡_{e} B if and only if A ≤_{e} B and B ≤_{e} A. The enumeration degree (e-degree) of the set A is the equivalence class Deg_{e}(A) = {B ⊆ ω|A ≡_{e} B}. We denote the e-degrees by a, b, c...

We use the standard join operation of two sets A⊕B = {2x|x ∈ A}∪{2x+1|x ∈ B} having the property that Deg_{e}(A⊕B) is the least upper bound of Deg_{e}(A) and Deg_{e}(B).

A set of natural numbers C is said to be total if its complement is e-reducible to C, i.e. \overline{C} ≤_{e} C, (which is equivalent to C ≡_{e} C^{+}, where we define C^{+} = C ⊕ \overline{C}, and thus for every set C^{+} ≡_{e} Gr(χ_{C})).

1 B-Generic sets

Definition 1.1 ω-string is a finite function from ω into ω, with domain an initial segment of ω. ∅_{ω} denotes the nowhere defined function, considered as empty ωstring; note that length of σ_{ω} is lh(σ_{ω}) = μx[¬∃y(σ_{ω}(x) = y)];

0-1-string, (or 2-valued string) is an ω-string α_{ω}, such that Rng(α_{ω}) ⊆ {0, 1}. For every 0-1-string α_{ω} we define the set α_{ω}^{+} = {x | α_{ω}(x) ≃ 0}.

Definition 1.2 The set A is B-generic, for B ⊆ ω, if and only if for every set S, such that S is a set of 0-1-strings and S ≤_{e} B

∃α_{ω} ⊆ χ_{A}(α_{ω} ∈ S ∨ ∀β_{ω} ⊇ α_{ω}(β_{ω} ∉ S)).

The set A is quasi-minimal over B, if and only if

(1) B ≤_{e} A, but A ≰_{e} B; and (2) If C is a total set such that C ≤_{e} A, then C ≤_{e} B. The set A is minimal-like over B, if and only if

(1) B ≤_{e} A, but A ≰_{e} B; and (2) For every partial function φ, such that φ ≤_{e} A, there exists partial function ψ, such that φ ⊆ ψ and ψ ≤_{e} B.

In analogue to the definitions in [1], an e-degree containing such set is said to be strongly minimal-like over B.

Here we mention some of the properties of the B-generic sets, that we will need later: A is B-generic if and only if \overline{A} is B-generic; if A is B-generic, there is no infinite e-reducible to B, subset of A; every B-generic set A is infinite and not e-reducible to B.

Concerning the existence of a B-generic set, a minimal like set over any set B and the existence of a quasi-minimal set over any set B, see [1], [2], it is proven that for an arbitrary B-generic set A, the set A ⊕ B is minimal like and quasi-minimal over B.

Theorem 1.3 Let B_{0}, B_{1}, …, B_{n}, … be a sequence of sets of natural numbers. There exists a set of natural numbers A, which is minimal-like over this sequence, i.e. such that the next two conditions hold:

1) ∀n(B_{n} ≤_{e} A);

2) For every partial function φ, such that φ ≤_{e} A, there exist a partial function ψ and natural number n, such that φ ⊆ ψ and ψ ≤_{e} B_{0} ⊕ … ⊕ B_{n}.

Proof:

In the following proof the notation ∀^{∞} x P (x) is equivalent to ∃y∀x(x ≥ y ⇒ P (x)). We define a set A, satisfying two requirements:

(a) ∀n ∀^{∞}x(⟨x, n⟩ ∈ A ⇔ x ∈ B_{n}), and

(b) ∀e(Ψ_{e}(A) is a function ⇒ ∃ψ(Ψ_{e}(A) ⊆ ψ & ψ ≤_{e} B_{0} ⊕ … ⊕ B_{2e+1})), building finite sets A_{0} ⊆ … ⊆ A_{s} ⊆ . . . ..., having the next property: ∀s(⟨x, m⟩ ∈ A_{s+1} \ A_{s} & m ≤ s ⇒ x ∈ B), for all x and m. Stage 0 : Let A_{0} = ∅. Stage 2e+1 : A_{s} is built, where s = 2e. We have two cases:

Case 1: There exists ⟨x, n⟩, such that x ∈ B_{n} and ⟨x, n⟩ ∉ A_{s}. Then we can define A_{s+1} = A_{s} ∪ {⟨x, n⟩}, for the first such ⟨x, n⟩ = μ⟨x, n⟩.

Case 2: Otherwise, define A_{s+1} = A_{s}. Stage 2e+2 : A_{s} is built, where s = 2e + 1. Again we have two cases:

Case 1: There exists a finite set D_{v}, such that A_{s} ⊆ D_{v} and Ψ_{e}(D_{v}) is not a function (i.e. ∃x∃y∃z such that y ≠ z & ⟨x, y⟩ ∈ Ψ_{e}(D_{v}) & ⟨x, z⟩ ∈ Ψ_{e}(D_{v})) and such that ∀t∀m(⟨t, m⟩ ∈ D_{v} \ A_{s} & m ≤ s ⇒ t ∈ B_{m})?

Define A_{s+1} to be the least D_{v} (i.e. having the least code v), with this property. Case 2: Otherwise, define A_{s+1} = A_{s}.

End.

Finally define A = ⋃_{s=0}^{∞} A_{s}.

For this set we can prove the properties (a) and (b), from which our theorem follows.

The interesting direction of the proof of (a) is (⇒). We can prove that ∀n ∀^{∞} x (⟨x, n⟩ ∈ A ⇒ x ∈ B_{n}). Assume it is not true, i.e. there exist n and infinitely many x_{0} < … < x_{i} < …, such that ⟨x_{i}, n⟩ ∈ A and x_{i} ∉ B_{n}. Therefore ∀x_{i}∃s_{i}(⟨x_{i}, n⟩ ∈ A_{s_{i}+1} \ A_{s_{i}}). But at every stage s the set A_{s+1} \ A_{s} is finite, then there exist infinitely many x_{s_{0}}, …, x_{s_{i}}, … from this sequence, such that at stages s_{0} < … < s_{i} < … we have ⟨x_{s_{i}}, n⟩ ∈ A_{s_{i}+1}\A_{s_{i}}. But x_{s_{i}} ∉ B_{n} and then the stages s_{i} + 1 must be even (i.e. s_{i} + 1 = 2e_{i} + 2), and we have Case 1, i.e. A_{s_{i}+1} = D_{v}, where D_{v} ⊇ A_{s_{i}} and ∀t∀m(⟨t, m⟩ ∈ D_{v} \ A_{s_{i}} & m ≤ s_{i} ⇒ t ∈ B_{m}). Therefore for every s_{i} ≥ n if ⟨x_{s_{i}}, n⟩ ∈ A_{s_{i}+1} \ A_{s_{i}}, then x_{s_{i}} ∈ B_{n}, which is a contradiction.

The proof of (b) consists in the following: supposing Ψ_{e}(A) to be a graph of some function, at Stage 2e+2, for s=2e + 1 we have Case2. Define the set G_{ψ} = {⟨x, y⟩ | ∃D_{v}(D_{v} ⊇ A_{s} & ⟨x, y⟩ ∈ Ψ_{e}(D_{v}) & ∀⟨t, m⟩(⟨t, m⟩ ∈ D_{v} \A_{s} & m ≤ s ⇒ t ∈ B_{m}))}. Therefore the following conditions hold:

• G_{ψ} ≤_{e} B_{0} ⊕ … ⊕ B_{s};

• G_{ψ} = Gr(ψ), i.e. G_{ψ} is a graph of some function ψ, since assuming it not true, there exist x and y_{1} ≠ y_{2}, such that ⟨x, y_{1}⟩ ∈ G_{ψ} and ⟨x, y_{1}⟩ ∈ G_{ψ}. Therefore there exist finite sets D_{v_{1}} and D_{v_{2}}, both extending A, s.t. ⟨x, y_{1}⟩ ∈ Ψ_{e}(D_{v_{i}}) and ∀⟨t, m⟩(⟨t, m⟩ ∈ D_{v_{i}} \ A_{s} & m ≤ s ⇒ t ∈ B_{m}). Then for D_{v} = D_{v_{1}} ∪ D_{v_{2}}, Ψ_{e}(D_{v}) is not a function and ∀⟨t, m⟩(⟨t, m⟩ ∈ D_{v} \ A_{s} & m ≤ s ⇒ t ∈ B_{m}), which is a contradiction with Case 2.

• Ψ_{e}(A) ⊆ G_{ψ}, since assuming there is ⟨x, y⟩ ∈ Ψ_{e}(A)\G_{ψ}, there exists A_{s+p} ⊇ A_{s}, such that ⟨x, y⟩ ∈ Ψ_{e}(A_{s+p}) and ∃⟨t, m⟩ (⟨t, m⟩ ∈ A_{s+p} \A_{s} & m ≤ s & t ∉ B_{m}). It follows that there is i, such that 0 ≤ i < p and ⟨t, m⟩ ∈ A_{s+i+1} \ A_{s+i}, and therefore m ≤ s+i. Since A_{s+i+1} \A_{s+i} ≠ ∅, we have Case 1 at Stage s+i = 2e_{i} +1 or Case 1 at Stage s + i = 2e_{i}. But in both cases it follows that t ∈ B_{m}, which is a contradiction.

This proves our proposition. □

As a corollary of the above theorem we obtain the existence of strongly minimallike e-degree over an infinite ascending sequence of e-degrees.

2 B-Generic regular enumerations

In this paragraph we illustrate briefly some results obtained using the relative generic regular enumerations and many of the proofs will be only sketched.

Definition 2.1 Let B ⊆ ω be a non-empty set of natural numbers.

1) The total and surjective function f : ω →ω, is called B-regular ω-enumeration, if f(2ω) = B, where f(2ω) = {f(2x) | x ∈ ω}.

2) An ω-string τ_{ω} is B-regular, if τ_{ω}(2ω) ⊆ B, where τ_{ω}(2ω) = {y | ∃x (τ_{ω}(2x) = y)}.

3) The B-regular ω-enumeration f is called B-generic if for every e-reducible to B set of ω-strings F, the following holds:

∃σ_{ω} ⊆ f(σ_{ω} ∈ F ∨ ∀τ_{ω} ⊇ σ_{ω}(τ_{ω} ∉ F)).

For every non-empty set B one can iteratively build a B-generic B-regular enumeration f at stages, using ω-strings to satisfy the requirements in the definition of f.

It is true that f ≰_{e} B, for every B-generic B-regular enumeration f. This can be proved assuming f ≤_{e} B, and defining the e-reducible to B set of ω-strings S = {τ_{ω} | τ_{ω}(2ω) ⊆ B & τ_{ω} ⊈ f}, that will lead to the contradiction.

Proposition 2.2 For every B-generic B-regular enumeration f, for every set R, such that R ≤_{e} B, \overline{R} ≤_{e} B, R ∩ B ≠ ∅ and \overline{R} ∩ B ≠ ∅, the set f^{−1}(R) is B-generic.

Proof:

Since f^{−1}(R) = {x | f(x) ∈ R}, we have that χ_{f^{−1}(R)} = χ_{R} ∘ f. Assume f^{−1}(R) is not B-generic, i.e. there is e-reducible to B set of ω-strings, such that

(1) ∀α_{ω}(α_{ω} ⊆ χ_{f^{−1}(R)} ⇒ α_{ω} ∉ F & ∃β_{ω}(β_{ω} ⊇ α_{ω} & β_{ω} ∈ F)).

Define S = {σ_{ω} | ∃α_{ω}(α_{ω} ∈ F & χ_{R} ∘σ_{ω} = α_{ω})}, where χ_{R} ∘σ_{ω} = α_{ω} if and only if (lh(α_{ω}) = lh(σ_{ω}) & ∀x < lh(α_{ω})(α_{ω}(x) = 0 ⇔ σ_{ω}(x) ∈ R)), therefore S is a set of B-regular ω-strings and S ≤_{e} B. But f is B-generic B-regular enumeration, so there is σ_{ω} ⊆ f, such that either σ_{ω} ∈ S, either ∀τ_{ω} ⊇ σ_{ω}(τ_{ω} ∉ S).

Assuming σ_{ω} ∈ S, there is α_{ω} ∈ F, such that χ_{R} ∘ σ_{ω} = α_{ω}, but σ_{ω} ⊆ f and then χ_{R} ∘ f ⊇ α_{ω}, i.e. α_{ω} ⊆ χ_{f^{−1}(R)}, which is a contradiction with (1). Therefore for that σ_{ω} the following holds:

(2) ∀τ_{ω} ⊇ σ_{ω}(τ_{ω} ∉ S).

Define α_{ω} = χ_{R} ∘ σ_{ω}. Since σ_{ω} ⊆ f, then α_{ω} ⊆ χ_{R} ∘ f = χ_{f^{−1}(R)}, and from (1) it follows that there exists β_{ω}, such that β_{ω} ⊇ α_{ω} and β_{ω} ∈ F. Therefore β_{ω} ⊇ χ_{R} ∘ σ_{ω} = α_{ω} and lh(β_{ω}) ≥ lh(α_{ω}). If we fix two elements of B - a ∈ R ∩ B and b ∈ \overline{R} ∩ B, we can define an ω-string τ_{ω}, such that τ_{ω} ⊇ σ_{ω}, lh(τ_{ω}) = lh(β_{ω}) and ∀x(lh(σ_{ω}) ≤ x ≤ lh(τ_{ω}) ⇒ (β_{ω}(x) = 0 ⇔ τ_{ω}(x) ∈ R)), i.e. β_{ω} = χ_{R} ∘ τ_{ω} ⊇ χ_{R} ∘σ_{ω} = α_{ω}. Since β_{ω} ∈ F and χ_{R} ∘τ_{ω} = β_{ω}, then τ_{ω} ∈ S, which is a contradiction with (b). Therefore f^{−1}(R) is not B-generic set.

□

The following corollary follows directly from Proposition 2.2 and from the properties of relative generic sets in §1.

Corollary 2.3 For every B-generic B-regular enumeration f, for every set R, such that R ≤_{e} B, \overline{R} ≤_{e} B, R ∩ B ≠ ∅ and \overline{R} ∩ B ≠ ∅, the set f^{−1}(R) ⊕ B is quasi-minimal over B.

Lemma 2.4 Let A be B-generic. Let R ⊆ ω, such that R ≤_{e} B, \overline{R} ≤_{e} B, R ∩ B ≠ ∅ and \overline{R} ∩ B ≠ ∅. Let δ_{ω} be an ω-string, having the properties (1) and (2):

(1) δ_{ω} is B-regular;

(2) ∀x < lh(δ_{ω}) (x ∈ A ⇔ δ_{ω}(x) ∈ R).

For every S, such that S is e-reducible to B set of ω-strings, there exists ω-string σ_{ω}, having the properties (a), (b), (c) and (d) :

(a) σ_{ω} ⊇ δ_{ω};

(b) σ_{ω} is B-regular;

(c) ∀x < lh(σ_{ω}) (x ∈ A ⇔ σ_{ω}(x) ∈ R);

(d) σ_{ω} ∈ S ∨ ∀τ_{ω}(τ_{ω} ⊇ σ_{ω} ⇒ τ_{ω} ∉ S).

Proof:

Let us denote by α_{ω} ∼_{R} σ_{ω} the property ∀x ∈ Dom(σ_{ω})(α_{ω}(x) = 0 ⇔ σ_{ω}(x) ∈ R), where α_{ω} is a 0-1-string, σ_{ω} is a ω-string and R ⊆ ω.

Define the set P = {α_{ω} | ∃σ_{ω}(σ_{ω} ∈ S & σ_{ω} ⊇ δ_{ω} & σ_{ω}(2ω) ⊆ B & lh(α_{ω}) = lh(σ_{ω}) & α_{ω} ∼_{R} σ_{ω})}, that is e-reducible to B. Since A is B-generic, we have two possibilities:

Case 1. ∃α_{ω} ⊆ χ_{A} (α_{ω} ∈ P).

In this case there exists σ_{ω} - a B-regular extension of δ_{ω} in S with the same length as α_{ω}, such that α_{ω} ∼_{R} σ_{ω}. But α_{ω} ⊆ χ_{A}, then ∀x < lh(σ_{ω}) (x ∈ A ⇔ σ_{ω}(x) ∈ R), i.e. σ_{ω} has the properties (a), (b), (c) and (d).

Case 2. ∃α_{ω} ⊆ χ_{a}∀β_{ω} ⊇ α_{ω}(β_{ω} ∉ P).

In this case ∃α_{ω} ⊆ χ_{A}(lh(δ_{ω}) ≤ lh(α_{ω}) & ∀β_{ω} ⊇ α_{ω}(β_{ω} ∉ S)). Fix two elements a in R ∩ B ≠ ∅ and b in \overline{R} ∩ B ≠ ∅. Now we can define an ω-string σ_{ω}, such that σ_{ω} ⊇ δ_{ω} and lh(σ_{ω}) = lh(α_{ω}), such that for the arguments x, s.t. lh(δ_{ω}) ≤ x < lh(α_{ω}), σ_{ω}(x) ≃ a if α_{ω}(x) = 0; and σ_{ω}(x) ≃ b if α_{ω}(x) = 1. Since δ_{ω} is Bregular, σ_{ω} is B-regular too. And from (2) and α_{ω} ⊆ χ_{A} follows that ∀x < lh(σ_{ω}) (x ∈ A ⇔ σ_{ω}(x) ∈ R). So, σ_{ω} has the properties (a), (b) and (c). It remains to verify (d).

First, notice that α_{ω} ∼_{R} σ_{ω}. Assume that there exists τ_{ω}, such that τ_{ω} ⊇ σ_{ω} ⊇ δ_{ω} and τ_{ω} ∈ S, (then τ_{ω} is B-regular). Therefore there exists 0-1-string β_{ω}, such that β_{ω} ⊇ α_{ω} and lh(β_{ω}) = lh(τ_{ω}), such that for the arguments lh(α_{ω}) ≤ x < lh(τ_{ω}), β_{ω}(x) ≃ 0 if τ_{ω}(x) ∈ R; and β_{ω}(x) ≃ 1 if τ_{ω}(x) ∉ R. Since α_{ω} ∼_{R} σ_{ω} for this β follows that ∀x < lh(β_{ω}) (β_{ω}(x) = 0 ⇔ τ_{ω}(x) ∈ R), i.e. β_{ω} ∼_{R} τ_{ω} and therefore β_{ω} ∈ P, which is a contradiction with Case 2, then the property (d) holds.

In both cases we found an ω-string satisfying (a), (b), (c) and (d).

□

Proposition 2.5 Let A be B-generic and R be such that R ∩ B ≠ ∅, \overline{R} ∩ B ≠ ∅, R ≤_{e} B and \overline{R} ≤_{e} B. There exists B-generic B-regular enumeration f, such that A = f^{−1}(R).

Proof:

Since f^{−1}(R) = {x | f(x) ∈ R}, A = f^{−1}(R) is equivalent to ∀x(x ∈ A ⇔ f(x) ∈ R).

We build a sequence of ω-strings σ_{ω}^{0} ⊆ σ_{ω}^{1} ⊆ … σ_{ω}^{q} ⊆ …, such that each σ_{ω}^{q} has the properties (1) and (2):

(1) σ_{ω}^{q} is B-regular, i.e. σ_{ω}^{q}(2ω) ⊆ B;

(2) ∀x < lh(σ_{ω}^{q}) (x ∈ A ⇔ σ_{ω}^{q}(x) ∈ R).

If (1) holds for all σ_{ω}^{q}, then f(2ω)⊆B. If (2) for each σ_{ω}^{q} and from (3) it follows that A = f^{−1}(R).

At Stage (2e + 1) we insure f to be total, surjective and f(2ω) ⊆ B, i.e.

(3) ∀q = 2e + 1 (lh(σ_{ω}^{q+1}) > lh(σ_{ω}^{q}));

(4) ∀x ∈ ω ∃q = 2e + 1 (x ∈ Rng(σ_{ω}^{q}));

(5) ∀x ∈ B ∃q = 2e + 1 (x ∈ σ_{ω}^{q}(2ω)).

At Stage (2e + 2) we insure f to be B-generic, i.e.

(6) ∀q = 2e + 2 ( If Ψ_{e}(B) is a set of B-regular ω-strings, then

(σ_{ω}^{q} ∈ Ψ_{e}(B) ∨ ∀τ_{ω} ⊇ σ_{ω}^{q}(τ_{ω} ∉ Ψ_{e}(B) )) ).

Stage 0: Define σ_{ω}^{0} = ∅_{ω}. Stage 2e+1: At this stage σ_{ω}^{q} is built, with q = 2e.

Let x_{0}, x_{1}, x_{2} and x_{3} be the first numbers, greater or equal to lh(σ_{ω}^{q}), that belong to 2ω ∩ A, (2ω + 1) ∩ A, 2ω ∩ \overline{A} and (2ω + 1) ∩ \overline{A} respectively. Such x_{i} exist, because assuming for example ∀x (x ≥ lh(σ_{ω}^{q}) & x ∈ 2ω ⇒ x ∉ A), the set C_{0} = \{x | x ≥ lh(σ_{ω}^{q}) & x ∈ 2ω\} is infinite and recursively enumerable and C_{0} ⊆ \overline{A}, which is a contradiction with the properties of the B-generic sets.

Let m = max{x_{0}, x_{1}, x_{2}, x_{3}} Define σ_{ω}^{q+1}, such that σ_{ω}^{q+1} ⊇ σ_{ω}^{q} and lh(σ_{ω}^{q+1}) = m + 1 > lh(σ_{ω}^{q}), and for the arguments lh(σ_{ω}^{q})≤ x≤ m, define as follows:

σ_{ω}^{q+1}(x) ≃\begin{cases}μy[y ∈R ∩ B][y ∉Rng(σ_{ω}^{q})] & , x∈2ω & x∈A \\ μy[y ∈\overline{R} ∩ B][y ∉Rng(σ_{ω}^{q})] & , x∈2ω & x∉A \\ μy[y ∈R][y ∉Rng(σ_{ω}^{q})] & , x∉2ω & x∈A \\ μy[y ∈\overline{R}][y ∉Rng(σ_{ω}^{q})] & , x∉2ω & x∉A \end{cases}

Stage 2e+2: At this stage σ_{ω}^{q} is built, with q = 2e + 2.

Define G = {σ_{ω} | σ_{ω}(2ω) ⊆ B & ∀x < lh(σ_{ω}) (x ∈ A ⇔ σ_{ω}(x) ∈ R)}, i.e. G = {σ_{ω} | for σ_{ω} (1) and (2) hold true }. We have two possibilities:

Case 1. ∃σ_{ω} ⊇ σ_{ω}^{q} (σ_{ω} ∈ G & (σ_{ω} ∈ Ψ_{e}(B) ∨ ∀τ_{ω} ⊇ σ_{ω}(τ_{ω} ∉ Ψ_{e}(B) ))). Define

σ_{ω}^{q+1} to be the least such σ_{ω}.

Case 2. ∀σ_{ω} ⊇ σ_{ω}^{q} (σ_{ω} ∈ G ⇒ (σ_{ω} ∉ Ψ_{e}(B) & ∃τ_{ω} ⊇ σ_{ω} (τ_{ω} ∈ Ψ_{e}(B) ))). Define

σ_{ω}^{q+1} = σ_{ω}^{q}.

End.

Define f = ⋃_{q=0}^{∞} σ_{ω}^{q}.

Using induction on q one can prove that for each σ_{ω}^{q} the conditions (1) and (2) holds. At Stage 2e+1 we satisfy the requirements (3), (4) and (5). It follows that f is B-regular enumeration and A = f^{−1}(R).

From (1) and (2) for σ_{ω} it follows, that for every e ∈ ω, if Ψ_{e}(B) is a set of B-regular ω-strings, then there exists σ_{ω}, having the properties (a), (b), (c) and (d) of Lemma 2.4, i.e. σ_{ω} ⊇ σ_{ω}^{q}, σ_{ω} is B-regular, ∀x < lh(σ_{ω}) (x ∈ A ⇔ σ_{ω}(x) ∈ R) and (σ_{ω} ∈ Ψ_{e}(B) ∨ ∀τ_{ω} (τ_{ω} ⊇ σ_{ω} ⇒ τ_{ω} ∉ Ψ_{e}(B) )). This means that if Ψ_{e}(B) is a set of B-regular ω-strings, at Stage 2e+1, we never have Case 2, i.e the requirement (6) is satisfied.

Therefore our f is B-generic B-regular enumeration, such that A = f^{−1}(R).

□

Theorem 2.6 Let B be a non-empty set of natural numbers. Any set A ⊆ ω is B-generic if and only if there exist a set R and B-generic B-regular enumeration f, such that R ≤_{e} B and \overline{R} ≤_{e} B, and A = f^{−1}(R).

Proof: (⇐) The Proposition 2.2. (⇒) If A is B-generic and there exists at least two different elements in B (otherwise B is recursively enumerable and therefore e-equivalent to a set containing at least two different elements) a ≠ b. Then for R = {a} the conditions in Proposition 2.5 hold and therefore there exists B-generic B-regular enumeration f, such that A = f^{−1}(R), and for the existence of B-generic B-regular enumeration we need only B ≠ ∅.

□

References

[1] B.Cooper, Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion Theory Week, Oberwolfach 1989, Springer-Verlag, Berlin, Heidelberg, New York, 1990, pp. 57-110.

[2] K.Copestake, 1-Genericity in the enumeration degrees, The Journal of Symbolic Logic, vol.53 (1988), pp.878-887.