Genericity in abstract structure degrees

V.Boutchkova

March 1, 2002

Abstract

The generalized notion of genericity in the theory of abstract structure degrees is used to obtain a characterization of abstractly generic predicate of natural numbers as the preimage of some predicate of the denumerable set N and generic regular enumeration.

Introduction

In this paper we deal with search-computability, defined by Moschovakis in [2], though for the proofs of most of the propositions we have used the Skordev’s definition of search-computability, in [3] Skordev proved both are equivalent.

The idea of considering two sort structures was presented by I.N.Soskov during the cycle of lectures of the seminar on Computability Theory at Sofia University, 1998. The abstract structure degrees are defined also by him during the same seminar as well as their regular enumerations.

The first sort of the mentioned two-sort abstract structures is an arbitrary denumerable set and the other is the set of natural numbers. The presence of the equality among the basic predicates of the structure is required.

In these terms we present an analogue of some notions from the theory of the enumeration degrees, namely the set genericity and the related results, applying the techniques used by Copestake in [1]. We generalize the characterization obtained in [6], stating that 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.

Here we introduce the notion of genericity for abstract predicates. Using the enumerations of two-sort abstract structures (in the way they are used in [4]) we obtain a characterization of this type of abstract genericity, which claims that a predicate A of natural numbers is generic relatively the two-sort abstract structure 𝔅 with one predicate if and only if there exists a predicate Σ on the first sort, which is search computable in 𝔅 and a 𝔅-generic regular enumeration f, such that A = f_{N}^{−1}(Σ).

This paper is part of the author’s Master’s Thesis, supervised by I.Soskov.

1 Preliminaries

We use some standard definitions and notations: ≤_{e} denotes the enumeration reducibility between sets and Ψ_{e} denotes the e-th enumeration operator, i.e. Ψ_{e}(B) = {x | ∃v(⟨x, v⟩ ∈ W_{e} & D_{v} ⊆ B)}, where W_{e} is the recursively enumerable set with Gödel code e, B is a set of natural numbers and D_{v} is the finite set with code v. Recall the join operation for sets of naturals: A⊕B is the set {2x|x ∈ A}∪{2x+1|x ∈ B}, used to induce the least upper bound of the e-degrees of A and B.

Given a countable set N and 0^{∗} ∉ N, N^{∗} denotes the Moschovakis’ extension of N, i.e. the smallest extension of N ∪ {0^{∗}} closed under the operation ordered pair ⟨·, ·⟩ (we will use the same notation for effective coding of pairs of natural numbers); ω denotes the set of the natural numbers and ω^{∗} ⊆ N^{∗} is the set of elements 0^{∗}, …, (n + 1)^{∗} …, such that (n + 1)^{∗} = ⟨0^{∗}, n^{∗}⟩ ∈ ω^{∗}. By F we denote the set of one-argument partial functions φ : N^{∗} ⊸→ N^{∗}. We write φ ∈ SC(φ_{1}, …, φ_{n}) to say that φ is search computable in the set of functions {φ_{1} … φ_{n}} ⊆ F, (see [3]).

From now on, we consider the abstract partial two-sort structures:

𝔄 = ⟨N, ω; =_{N}, ≠_{N}; Σ_{1}, …, Σ_{k}⟩,

with two fixed basic predicates in N^{2}: =_{N} (equality) and ≠_{N} (inequality), and partial predicates Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, s.t. a_{i}, b_{i} ≥ 0 but not both zero. This kind of structures will be denoted by 𝔄(Σ_{1} … Σ_{k}).

The notation Σ_{0} ≤_{SC} 𝔄 says that Σ_{0} is search computable in the set of 𝔄’s predicates, including the equality and inequality, i.e. Σ̂_{0} ∈ SC(Σ̂_{1}^{𝔄}, …, Σ̂_{k}^{𝔄}, ˆ=_{N}, ˆ≠_{N}), (we also write Σ̂_{0} ∈ SC(𝔄)), where Σ̂ : N^{∗} ⊸→ N^{∗} is the semi-characteristic function of the predicate.

Soskov defined 𝔄 ⊕ 𝔅 to be the two-sort structure with predicates =_{N}, ≠_{N}, Σ_{1}^{𝔄} … Σ_{k_{𝔄}}^{𝔄}, Σ_{1}^{𝔅} … Σ_{k_{𝔅}}^{𝔅}; 𝔄 ≤_{SC} 𝔅 if and only if ∀i_{(1≤i≤k_{𝔄})}: Σ_{i}^{𝔄} ≤_{SC} 𝔅 and 𝔄 ≡_{SC} 𝔅 if and only if 𝔄 ≤_{SC} 𝔅 and 𝔅 ≤_{SC} 𝔄.

Definition 1.1 (Soskov) The abstract structure degrees are the equivalence classes, induced by the relation ≡_{SC} between structures, and we denote them by 𝔞, 𝔟, 𝔠... and for every 𝔞 and 𝔟 in 𝔇, 𝔞 ∪ 𝔟 = 𝔇_{s}(𝔄 ⊕ 𝔅) for some 𝔄 ∈ 𝔞 and 𝔅 ∈ 𝔟.

We write 𝔇 for the set of all abstract structure degrees with the partial ordering induced by ≤_{SC} . Thus the structure ⟨𝔇, ≤_{SC}, ∪, 𝔒⟩ is an upper semi-lattice with least element the empty structure 𝔒 = ⟨N; ω; =_{N}, ≠_{N}⟩.

On the seminar on Computability Theory in 1998, I.Soskov introduced the following definition of search computability and proved its equivalence with the standard ones (see [2] and [3]):

𝔄 ≤_{SC} 𝔅 iff ∀α(𝔅 ≤ α ⇒ 𝔄 ≤ α),

where α = (f, R) is enumeration and 𝔄 ≤ α if and only if f^{−1}(𝔄) ≤_{e} R. Here we shall use it for a single predicate Σ ⊆ N^{a_{i}} × ω^{b_{i}} in this particular form:

Σ ≤_{SC} 𝔄 iff (f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄), for every N-enumeration f_{N})  (1)

where f_{N} : ω → N is total and surjective function, that we shall call N-enumeration, f_{N}^{−1}(Σ) = {⟨x_{1} … x_{a}, y_{1} … y_{b}⟩ ∈ ω | (f_{N}(x_{1}) … f_{N}(x_{a}), y_{1} … y_{b}) ∈ Σ} and for the structure 𝔄 = ⟨N, ω; =_{N}, ≠_{N}; Σ_{1}, …, Σ_{k}⟩, the preimage f_{N}^{−1}(𝔄) is defined in such a way that is e-equivalent to f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ f_{N}^{−1}(=_{N}) ⊕ f_{N}^{−1}(≠_{N}).

2 Enumerations

Many of the definitions and the proofs from [4] concerning the enumeration approach and the normal form theorem are applicable in our case. We recall them in order to use them later in §3 and for the characterization in §4.

Definition 2.1 1) N-string τ_{N} is a finite function τ_{N} : [0 … n − 1] → N, with domain an initial segment of ω with length lh(τ_{N}) = n.

We shall call the strings used in [6] ω-strings, i.e. an ω-string is a finite sequence of naturals meant to be an initial segment of ω.

2) τ_{N} ⊆ σ_{N} iff ∀x(x < lh(τ_{N}) ⇒ τ_{N}(x) = σ_{N}(x)).

3) Code of the N-string τ_{N} is defined to be ⌜τ_{N}⌝ = ⟨n^{∗}, τ_{N}(0), …, τ_{N}(n − 1)⟩.

Definition 2.2 ([4]) For a structure 𝔄(Σ_{1} … Σ_{k}) with Σ_{i} ⊆ N^{a_{i}} ×ω^{b_{i}}, an N-string τ_{N} and a formula F_{e}(z) with e, z ∈ ω, define the forcing relation τ_{n} ⊩_{𝔄} F_{e}(z) as follows:

(1) τ_{N} ⊩_{𝔄} F_{e}(z) iff ∃v(⟨v, z⟩ ∈ W_{e} & τ_{n} ⊩_{𝔄} D_{v})

(2) τ_{N} ⊩_{𝔄} D_{v} iff ∀u ∈ D_{v}(u = ⟨i, ⟨x_{1} … x_{a_{i}}, y_{1} … y_{b_{i}}⟩⟩ & 1 ≤ i ≤ k & x_{1} … x_{a_{i}} ∈ Dom(τ_{N}) &(τ_{N}(x_{1}) … τ_{N}(x_{a_{i}}), y_{1} … y_{b_{i}}) ∈ Σ_{i}∨ u = ⟨0, 2⟨x, y⟩⟩ & x, y ∈ Dom(τ_{N}) & τ_{N}(x) = τ_{N}(y) & u = ⟨0, 2⟨x, y⟩ + 1⟩ & x, y ∈ Dom(τ_{N}) & τ_{N}(x) ≠_{N} τ_{N}(y)).

Definition 2.3 ([4]) For an N-enumeration f_{N} : ω → N and a structure 𝔄(Σ_{1} … Σ_{k}) with predicates Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, define

f_{N} ⊧_{𝔄} F_{e}(z) if and only if z ∈ Ψ_{e}(f_{N}^{−1}(𝔄)).

Definition 2.4 ([4]) We say that the predicate Σ ⊆ N^{a} × ω^{b} has normal form in the structure 𝔄(Σ_{1} … Σ_{k}), if there exist e ∈ ω, an N-string δ_{N} and x_{1} … x_{a} ∉ Dom(δ_{N}), such that for all s_{1} … s_{a} ∈ N, and for all y_{1} … y_{b} ∈ ω, (s_{1} … s_{a}, y_{1} … y_{b}) ∈ Σ iff ∃τ_{N} ⊇ δ_{N} s.t. ∀_{1≤i≤a} (τ_{N}(x_{i}) = s_{i}) & τ_{N} ⊩_{𝔄} F_{e}(⟨x_{1} … x_{a}, y_{1} … y_{b}⟩).

The following is a corrollary from the Normal Form Theorem from [4] for the case of two-sort structures.

Theorem 2.5 (Normal Form Theorem) Let 𝔄(Σ_{1} … Σ_{k}) be a structure, with predicates Σ_{i} ≤ N^{a_{i}} × ω^{b_{i}}. Then every predicate Σ ⊆ N^{a} × ω^{b} that Σ is search computable in 𝔄, has a normal form in 𝔄.

3 Generic predicates

Definition 3.1 1) Let Σ ⊆ N^{a} × ω^{b} be a predicate. We define the characteristic function of Σ to be the function χ_{Σ} : N^{∗} ⊸→ N^{∗}, defined as follows:

χ_{Σ}(s) = \begin{cases}0^{∗} & if s = ⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩ & (s_{1} … s_{a}, x_{1} … x_{b}) ∈ Σ \\ 1^{∗} & if s = ⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩ & (s_{1} … s_{a}, x_{1} … x_{b}) ∉ Σ \\ ↑ & otherwise \end{cases} .

2) Let F_{a,b}, where a + b ≥ 1, be the set of all partial functions φ ∈ F, such that Dom(φ) ⊆ {⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩ | (s_{1} … s_{a}, x_{1} … x_{b}) ∈ N^{a} × ω^{b}} and Range(φ) ⊆ ω^{∗}.

3) Define (a, b)-string to be a finite function α ∈ F_{a,b} with Range(α) ⊆ {0^{∗}, 1^{∗}} . We may define the code of the (a, b)-string α (denote ⌜α⌝), to be ⟨k^{∗}, ⟨s_{1}, α(s_{1})⟩ , …, ⟨s_{k}, α(s_{k})⟩⟩ ∈ N^{∗}, if Dom(α) = {s_{1}, …, s_{k}}; and ⌜∅⌝ = 0^{∗}, for the empty function.

Remark: Since an (a, b)-string may have more than one (but only finitely many) different codes, by α ∈ S^{∗} ⊆ N, we mean that there exists a code of α, which belongs to the set S^{∗}; respectively α ∉ S^{∗} means there is no code of α that belongs to the set. We say that S^{∗} is a set of codes of (a, b)-strings when each element is a code of some (a, b)-string, it is not necessary that S^{∗} contains all the codes of an (a, b)-string.

4) Semi-characteristic function of the set S^{∗} ⊆ N we call the function C_{S^{∗}} : N^{∗} ⊸→ N^{∗}, defined as follows:

C_{S^{∗}}(s) ≅ \begin{cases}0^{∗} & if s ∈ S^{∗} \\ ↑ & otherwise \end{cases}

For a given set S^{∗} ⊆ N^{∗} and structure 𝔅(Σ_{1} … Σ_{k}), we write S^{∗} ∈ SC(𝔅), when C_{S^{∗}} ∈ SC( ˆ=_{N}, ˆ≠_{N}, Σ̂_{1}, …, Σ̂_{k}).

5) For every a and b, which are not both zero, and every function φ ∈ F_{a,b}, we define the graph-predicate of φ, to be the predicate Σ_{φ} ⊆ N^{a} × ω^{b+1}, such that for all s_{1}, …, s_{a} ∈ N and x_{1}, …, x_{b}, y ∈ ω, (s_{1} … s_{a}, x_{1} … x_{b}, y) ∈ Σ_{φ} iff φ(⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩) = y^{∗}.

Definition 3.2 Given a structure 𝔅(Σ_{1} … Σ_{k}), we say that the predicate Σ ⊆ N^{a} × ω^{b} is 𝔅generic if for every set S^{∗} ⊆ N^{∗} of codes of (a, b)-strings such that S^{∗} ∈ SC(𝔅), the following holds:

∃α ⊆ χ_{Σ}(α ∈ S^{∗} ∨ ∀β ⊇ α(β ∉ S^{∗})).

Note: If we consider a structure 𝔅(B) with one predicate of naturals and a predicate Σ ⊆ ω, then Σ is 𝔅-generic in the sense of Definition 3.2 if and only if the set Σ is B-generic set of natural numbers in the classical sense. The proof uses the definition of SC via enumerations (1).

Proposition 3.3 For every structure 𝔅 = 𝔅(Σ_{1} … Σ_{k}) and a, b ∈ ω, such that a + b ≥ 1, there exists a 𝔅-generic predicate Σ ⊆ N^{a} × ω^{b}.

Proof:

In this proof and from now on \overline{x} will denote a finite sequence of elements for brevity (an appropriate number of them).

We can find such Σ by building its characteristic function as a union of (a, b)- strings, that we build at stages, such that at even stages we satisfy the requirements Dom(χ_{Σ}) to be a domain of a predicate’s characteristic function and at odd stages - the genericity.

Let us have some enumeration S_{0}^{∗} … S_{n}^{∗} … of the domains the partial functions from SC(𝔅), i.e. S_{n}^{∗} = Dom(φ), for φ ∈ SC(𝔅).

Stage 0 Define α_{0} = ∅.

Stage 2n+1 We have defined α_{q} for q = 2n. Let ⟨\overline{s}, \overline{x}^{∗}⟩ ∈ N^{∗} be such that (\overline{s}, \overline{x}) is the least according to some order in N^{a} × ω^{b} element for which ⟨\overline{s}, \overline{x}^{∗}⟩ ∉ Dom(α). Define α_{q+1} to extend α_{q} with one new argument, i.e. such that α_{q+1}(⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩) = 0^{∗}.

Stage 2n+2 We have defined α_{q} for q = 2n + 1. Case 1. If there exists in S_{n}^{∗} an (a, b)-string β, extending α_{q}, define α_{q+1} to be the first such β. Case 2. Otherwise define α_{q+1} = α_{q}.

Finally we can define χ_{Σ} = ⋃_{q=0}^{∞} α_{q}, that is the characteristic function of some

𝔅-generic predicate. □

Proposition 3.4 Let 𝔅 be an abstract structure and Σ ⊆ N^{a} × ω^{b} a 𝔅-generic predicate. Then the following hold:

P1) The predicate \overline{Σ} ⊆ N^{a} × ω^{b} is 𝔅-generic.

P2) There is no infinite predicate C ⊆ N^{a} ×ω^{b}, such that C ≤_{SC} 𝔅 and C ⊆ Σ. P3) Σ is infinite. P4) Σ ≰_{SC} 𝔅.

Proof:

Each of (P3) and (P4) follows directly from the previous properties. To prove (P1) we may assume it’s false. Therefore there is a set of codes of (a, b)-strings, namely P^{∗} ∈ SC(𝔅), such that:

(a) ∀α ⊆ χ\overline{Σ} (α ∉ P^{∗} & ∃β ⊇ α(β ∈ P^{∗})).

There is a recursive function translating (codes of) (a, b)-strings into their reverse, e.g. the reverse of α being the (a, b)-string \overline{α}, such that ∀s ∈ Dom(α), α(x) = 0^{∗} iff \overline{α}(x) = 1^{∗}. Thus the set S^{∗} = \{α | \overline{α} ∈ P^{∗}\} ∈ SC(𝔅) and therefore there exists α ⊆ χ_{Σ} (and therefore \overline{α} ⊆ χ\overline{Σ}) such that the next (1) or (2) holds:

(1) α ∈ S^{∗}. Then \overline{α} ∈ P^{∗} and \overline{α} ⊆ χ\overline{Σ}, which is a contradiction with (a).

(2) ∀β ⊇ α (β ∉ S^{∗}). But from (a) for \overline{α} follows there exists an (a, b)-string β ∈ P^{∗} extending \overline{α}. Since \overline{\overline{β}} = β, we have that β ∈ S^{∗} and β ⊇ α, which is a contradiction.

In both cases we found a contradiction, therefore Σ is 𝔅-generic.

To prove (P2) we may assume there exists such C ⊆ N^{a} ×ω^{b} and define a set S^{∗} = {α | ∃s_{1} … s_{a} ∈ N, ∃y_{1} … y_{b} ∈ ω ((s_{1} … s_{a}, y_{1} … y_{b}) ∈ C & α(⟨s_{1} … s_{a}, y_{1}^{∗} … y_{b}^{∗}⟩) = 1^{∗})}, that will lead to contradiction.

□

Definition 3.5 Let us define the structure 𝔄(Σ_{1}^{𝔄} … Σ_{n}^{𝔄}) to be total iff \overline{Σ_{i}^{𝔄}} ≤_{SC} 𝔄 for 1 ≤ i ≤ n. The generalization the quasi-minimal and the minimal-like (see [1]) will have the following form:

1. 𝔄 is quasi-minimal over 𝔅 if the following two conditions hold:

• 𝔅 ≤_{SC} 𝔄 and 𝔄 ≰_{SC} 𝔅;

• For every total structure ℭ, if ℭ ≤_{SC} 𝔄 then ℭ ≤_{SC} 𝔅.

2. 𝔄 is minimal-like over 𝔅, if the following two conditions hold:

• 𝔅 ≤_{SC} 𝔄 and 𝔄 ≰_{SC} 𝔅;

• For every function φ ∈ F_{a,b}, if φ ∈ SC(𝔄), there exists a function ψ ∈ F_{a,b} such that φ ⊆ ψ and ψ ∈ SC(𝔅).

For the (a, b)-string α we define a predicate α^{+} to be the set {(s_{1} … s_{a}, x_{1} … x_{b})| α(⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩) = 0^{∗}}.

If Σ_{0} is a predicate and 𝔅(Σ_{1} … Σ_{k}) a structure, we denote by Σ_{0} ⊕ 𝔅 the two-sort structure with predicates Σ_{0}, Σ_{1} … Σ_{k}.

Proposition 3.6 For given 𝔅(Σ_{1} … Σ_{k}) and 𝔅-generic predicate Σ_{0}, the structure Σ_{0} ⊕ 𝔅 is minimal-like over 𝔅.

Proof:

Since Σ_{0} is 𝔅-generic, Σ_{0} ≰_{SC} 𝔅 and therefore 𝔅 ≨_{SC} Σ_{0} ⊕ 𝔅. Let (a_{i}, b_{i}) be the arity of the predicate Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}.

For φ ∈ F_{a,b}, such that φ ∈ SC(Σ_{0} ⊕ 𝔅), we define its graph-predicate Σ_{φ} for which Σ̂_{φ} ∈ SC(Σ_{0} ⊕ 𝔅), i.e. Σ_{φ} ≤_{SC} Σ_{0} ⊕ 𝔅 and from the Normal form theorem(2.5) it follows that Σ_{φ} has normal form in Σ_{0} ⊕ 𝔅. i.e. there are e ∈ ω, N-string δ_{N} and z_{1} … z_{a} ∉ Dom(δ_{N}), such that for all s_{1}, …, s_{a} ∈ N and x_{1} … x_{b}, y ∈ ω, (s_{1} … s_{a}, x_{1} … x_{b}, y) ∈ Σ_{φ} iff ∃τ_{N} ⊇ δ_{N} s.t. (τ_{N}(z_{i}) = s_{i} & τ_{N} ⊩_{Σ_{0}⊕𝔅} F_{e}(⟨z_{1}, …, z_{a}, x_{1} … x_{b}, y⟩). If by P_{a,b} we denote the set of codes of all (a, b)-strings and by P_{N} the set of all codes of N-strings, we may define the set S^{∗} to be the set of all β_{0} ∈ P_{a_{0},b_{0}}, for which there exist β_{i} ∈ P_{a_{i},b_{i}} for ∀_{1≤i≤k}, s.t. β_{i}^{+} ⊆ Σ_{i}, and there exist τ_{N}^{1}, τ_{N}^{2} ∈ P_{N}, both extending δ_{N} and such that z_{1} … z_{a} ∈ Dom(τ_{N}^{1}) ∩ Dom(τ_{N}^{2}), and there exist natural numbers x_{1} … x_{b} ∈ ω, y_{1} ≠ y_{2} ∈ ω, such that τ_{N}^{ε} ⊩_{𝔄(β_{0}^{+},β_{1}^{+},... ,β_{k}^{+})} F_{e}(⟨z_{1} … z_{a}, x_{1} … x_{b}, y_{ε}⟩) for each ε ∈ {1, 2}, where 𝔄(β_{0}^{+}, β_{1}^{+}, …, β_{k}^{+}) denotes the structure with finite predicates β_{i}^{+} ⊆ N^{a_{i}} × ω^{b_{i}}. Therefore S^{∗} ∈ 𝔅 and there is an (a_{0}, b_{0})-string α ⊆ χ_{Σ_{0}}, such that α ∈ S^{∗} or ∀β ⊇ α (β ∉ S^{∗}).

In the first case, since α ⊆ χ_{Σ_{0}}, then α^{+} ⊆ Σ_{0}, and from τ_{N}^{ε} ⊩_{𝔄(α^{+},β_{1}^{+},... ,β_{k}^{+})} F_{e}(⟨z_{1} … z_{a}, x_{1} … x_{b}, y_{ε}⟩) follows that τ_{N}^{ε} ⊩_{Σ_{0}⊕𝔅} F_{e}(⟨z_{1} … z_{a}, x_{1} … x_{b}, y_{ε}⟩), and using the normal form of Σ_{φ} we obtain a contradiction. So it remains the second case ∀β ⊇ α(β ∉ S^{∗}) and now we can define a predicate Σ_{ψ} as follows: Σ_{ψ} = {(s_{1} … s_{a}, x_{1} … x_{b}, y) | (∃β_{0} ∈ P_{a_{0},b_{0}} … ∃β_{k} ∈ P_{a_{k},b_{k}}, ∃τ_{N} ∈ P_{N}) s.t. (β_{0} ⊇ α & ∀_{1≤i≤k} β_{i}^{+} ⊆ Σ_{i} & τ_{N} ⊇ δ_{N} & ∀_{1≤j≤a} τ_{N}(z_{j}) = s_{j} & τ_{N} ⊩_{𝔄(β_{0}^{+},β_{1}^{+},... ,β_{k}^{+})} F_{e}(⟨z_{1} … z_{a}, x_{1} … x_{b}, y⟩), which is the graph-predicate of some function ψ and is search computable in 𝔅, therefore ψ ∈ SC(𝔅).

Using the above definition and the normal form of Σ_{φ} it is not difficult to verify that Σ_{φ} ⊆ Σ_{ψ}, from which follows that φ ⊆ ψ, and this proves our proposition.

□

Given a structure ℭ(Σ_{1} … Σ_{k}) and a predicate Σ ⊆ N^{a} × ω^{b}, if Σ ≤_{SC} ℭ and \overline{Σ} ≤_{SC} ℭ, then its characteristic function χ_{Σ} ∈ SC(ℭ). This fact can be used to prove the following:

Proposition 3.7 Given a structure 𝔅(Σ_{1} … Σ_{k}) and a 𝔅-generic predicate Σ, the structure Σ⊕𝔅 with predicates Σ, Σ_{1}, …, Σ_{k} is quasi-minimal over 𝔅.

The above is true for a single predicate, but not in the general case with multiple 𝔅-generic predicates. For example, for any total structure 𝔄(Σ, \overline{Σ}) with 𝔅-generic predicates Σ and \overline{Σ} ⊆ N^{a} × ω^{b}, the structure 𝔄 ⊕ 𝔅 is not quasi-minimal over 𝔅.

4 Generic regular enumerations

The regular enumerations are introduced by I.Soskov in [5] and here we shall use their modification for two-sort structures. An enumeration for two-sort structures is the pair f = (f_{N}, f_{ω}), where f_{N} : ω → N and f_{ω} : ω → ω are total surjective functions.

Gr(f_{N}) = {(s, x) | f_{N}(x) = s} ⊆ N × ω is the graph of f_{N}.

Gr(f_{ω}) = {⟨x, y⟩ | f_{ω}(x) = y} ⊆ ω is the graph of f_{ω}.

The enumerations f = (f_{N}, f_{ω}), define a unique structure 𝔄(Gr(f_{N}), Gr(f_{ω})), denoted by 𝔄_{f}.

Since every two-sort structure (with finite number of predicates) is equivalent, in terms of search computability, to a structure with one predicate, in this section we consider only structures with one predicate.

Definition 4.1 Given a structure 𝔅(Σ^{𝔅}) with one predicate ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b}, we say that the enumeration f = (f_{N}, f_{ω}) is 𝔅-regular, if the function f_{ω} is f_{N}^{−1}(Σ^{𝔅})-regular enumeration of ω in the sense of [5] and [6], i.e. f_{ω} is total surjective mapping of ω onto ω, such that f_{ω}(2ω) = f_{N}^{−1}(Σ^{𝔅}).

Definition 4.2 1) A pair of strings τ = (τ_{N}, τ_{ω}) is the pair of an N-string τ_{N} : ω ⊸→ N and an ω-string τ_{ω} : ω ⊸→ ω (see Definition 2.1). The pair ∅ = (∅_{N}, ∅_{ω}) is referred as the empty pair of strings.

2) Given a structure 𝔅(Σ^{𝔅}) with predicate ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b}, we say that the pair of strings τ = (τ_{N}, τ_{ω}) is 𝔅-regular if τ_{ω}(2ω) ⊆ τ_{N}^{−1}(Σ^{𝔅}), where τ_{N}^{−1}(Σ^{𝔅}) = {⟨x_{1} … x_{a}, y_{1} … y_{b}⟩ ∈ Dom(τ_{N})^{a} × ω^{b} | & (τ_{N}(x_{1}) … τ_{N}(x_{a}), y_{1} … y_{b}) ∈ Σ^{𝔅}} and τ_{ω}(2ω)={y | ∃x (τ_{ω}(2x)=y)}.

3) The N^{∗}-code of τ = (τ_{N}, τ_{ω}) is denoted by ⌜τ⌝^{∗} and defined to be the pair of codes ⌜τ⌝^{∗} = ⟨⌜τ_{N}⌝^{∗}, ⌜τ_{ω}⌝^{∗}⟩ , where ⌜τ_{N}⌝^{∗} = ⟨n^{∗}, ⟨1^{∗}, τ_{N}(1)⟩ , …, ⟨n^{∗}, τ_{N}(n)⟩⟩ and ⌜τ_{ω}⌝^{∗} = ⟨m^{∗}, ⟨1^{∗}, (τ_{ω}(1))^{∗}⟩ , …, ⟨m^{∗}, (τ_{ω}(m))^{∗}⟩⟩, n = lh(τ_{N}) and m = lh(τ_{ω}); define ⌜∅_{N}⌝^{∗} = 0^{∗} and ⌜∅_{ω}⌝^{∗} = 0^{∗}.

4) We say that τ extends σ, write σ ⊆ τ, if both σ_{N} ⊆ τ_{N} and σ_{ω} ⊆ τ_{ω}. For an enumeration f = (f_{N}, f_{ω}) and a pair of strings τ = (τ_{N}, τ_{ω}), we say that τ ⊆ f when both τ_{N} ⊆ f_{N} and τ_{ω} ⊆ f_{ω}.

Remark: Given a structure 𝔅(Σ^{𝔅}) let Reg_{𝔅} denote the set of codes of all 𝔅regular pairs of strings. Thus τ ∈ Reg_{𝔅} ⇔ τ_{ω}(2ω) ⊆ τ_{N}^{−1}(Σ^{𝔅}), and therefore Reg_{𝔅} ∈ SC(𝔅).

Definition 4.3 Given a structure 𝔅(Σ^{𝔅}) with predicate ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b}, we say that f = (f_{N}, f_{ω}) is 𝔅-generic regular enumeration, if it is 𝔅-regular enumeration and for every set S^{∗} ⊆ N^{∗} of codes of 𝔅(Σ^{𝔅})-regular pairs of strings, for which S^{∗} ∈ SC(𝔅), there exists a pair of strings τ ⊆ f, such that τ ∈ S^{∗} or ∀σ ⊇ τ (σ ∉ S^{∗}).

Proposition 4.4 For every structure 𝔅(Σ^{𝔅}) with one predicate ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b}, there exists a 𝔅-generic regular enumeration f = (f_{N}, f_{ω}).

Proof:

Let S_{0}^{∗}, …, S_{n}^{∗}, … be a sequence of all the sets S^{∗} ∈ SC(𝔅) and s_{0}, …, s_{n}, … be all the elements of N. We can build a 𝔅-generic regular enumeration in the standard way starting from the empty pair of strings and building an increasing sequence of 𝔅-regular pair of strings, such that, at even stages we will monitor the n-th set S_{n}^{∗} and take care to satisfy the requirements for genericity. At odd stages we will satisfy τ_{ω}^{q}(2ω) ⊆ (τ_{ω}^{q})^{−1}(Σ^{𝔅}) and in the same time f_{N}^{−1} ⊆ f_{ω}(2ω), as follows:

Suppose at Stage 2n+1 we have defined τ_{q} = (τ_{N}^{q}, τ_{ω}^{q}), for q = 2n. We may define τ_{N}^{q+1} to extend τ_{N}^{q}, so that for x = lh(τ_{N}^{q}), τ_{N}^{q+1}(x) = s_{n}. For the set (τ_{N}^{q+1})^{−1}(Σ^{𝔅}) we have two possibilities: if it is empty, define τ_{ω}^{q+1} = τ_{ω}^{q}. Otherwise (τ_{N}^{q+1})^{−1}(Σ^{𝔅}) ≠ Ø. In this case we consider the set A_{q} = (τ_{N}^{q+1})^{−1}(Σ^{𝔅}) \ τ_{ω}^{q}(2ω) and define τ_{ω}^{q+1} to extend τ_{ω}^{q} such that in the first odd number x_{1} ∉ Dom(τ_{ω}^{q}), define τ_{ω}^{q+1}(x_{1}) = n, and in the first even number x_{0} ∉ Dom(τ_{ω}^{q}), define τ_{ω}^{q+1}(x_{0}) to be the first y ∈ A_{q}, if A_{q} ≠ Ø, or the first y ∈ (τ_{N}^{q+1})^{−1}(Σ^{𝔅}), if A_{q} = Ø.

In this way we obtain the desired enumeration.

□

To prove the following proposition and the lemma, it may be convenient to define two notations for a (0, 1)-string α and N-string τ_{N} :

cmp(α, τ_{N}) if and only if ∀x ∈ ω (x^{∗} ∈ Dom(α) ⇔ x ∈ Dom(τ_{N})),

α ∼_{Σ} τ_{N} if and only if ∀x^{∗} ∈ Dom(α) (α(x^{∗}) = 0^{∗} ⇔ τ_{N}(x) ∈ Σ).

Proposition 4.5 For a structure 𝔅(Σ^{𝔅}) with one predicate ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b} and a 𝔅-generic regular enumeration f = (f_{N}, f_{ω}) the following properties hold:

1) 𝔅 ≤_{SC} 𝔄_{f}

2) 𝔄_{f} ≰_{SC} 𝔅

3) For every predicate Σ ⊆ N^{a}×ω^{b}, if Σ ≤_{SC} 𝔅 and \overline{Σ} ≤_{SC} 𝔄_{f}, then \overline{Σ} ≤_{SC} 𝔅.

4) For every predicate Σ ⊆ N, if ∅ ≠ Σ ≤_{SC} 𝔅 and ∅ ≠ \overline{Σ} ≤_{SC} 𝔅, then f_{N}^{−1}(Σ) is 𝔅-generic predicate.

5) For every predicate Σ ⊆ N, if ∅ ≠ Σ ≤_{SC} 𝔅 and ∅ ≠ \overline{Σ} ≤_{SC} 𝔅, the structure 𝔄(f_{N}^{−1}(Σ), Σ^{𝔅}) is quasi-minimal over 𝔅.

Proof:

These properties follow easily from the definitions and the properties of the enumerations. For example, for the proof of (4) we may assume that f_{N}^{−1}(Σ) is not 𝔅-generic predicate. Then there exists a set of (0, 1)-strings S, that fails the genericity, and consider the set of 𝔅-regular pairs of strings:

P^{∗} = {τ ∈ Reg_{𝔅} | ∃α ∈ S(cmp(α, τ_{N}) & α ∼_{Σ} τ_{N})}.

Since for each τ there is a unique α, such that cmp(α, τ_{N}) and α ∼_{Σ} τ_{N}, and for each α there is such τ_{N}, we can obtain a contradiction with the genericity of f.

□

Lemma 4.6 Given a structure 𝔅(Σ^{𝔅}) with ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b}, given a pair of strings δ, a 𝔅-generic predicate A ⊆ ω and a predicate Σ ⊆ N, such that ∅ ≠ Σ ≤_{SC} 𝔅 and ∅ ≠ \overline{Σ} ≤_{SC} 𝔅, for which the following two conditions hold:

(1) δ is 𝔅-regular;

(2) ∀x < lh(δ_{N}) (x ∈ A ⇔ δ_{N}(x) ∈ Σ), If S^{∗} ⊆ N^{∗} is a set of codes of 𝔅-regular pairs of strings and S ≤_{SC} 𝔅, then there exists a pair of strings σ with the following properties:

(a) σ ⊇ δ;

(b) σ is 𝔅-regular; (c) ∀x < lh(σ_{N}) (x ∈ A ⇔ σ_{N}(x) ∈ Σ), (this is the property (2) for σ);

(d) σ ∈ S ∨ ∀τ(τ ⊇ σ ⇒ τ ∉ S).

Proof:

The proof is very similar to the one of the corresponding lemma in the classical case (Lemma 2.4. in [6]).

□

Proposition 4.7 Given a structure 𝔅(Σ^{𝔅}) with ∅ ≠ Σ^{𝔅}, a 𝔅-generic predicate A ⊆ ω, and a predicate Σ ⊆ N, such that ∅ ≠ Σ ≤_{SC} 𝔅 and ∅ ≠ \overline{Σ} ≤_{SC} 𝔅, there exists a 𝔅-generic regular enumeration f, such that A = f_{N}^{−1}(Σ).

Proof:

We can build f by the standard construction of increasing sequence of pairs of strings σ_{q}, (starting from the empty pair of strings), with the properties (1) and (2) from the above lemma. Moreover, we want them to satisfy four additional properties:

(3) ∃n∀e ≥ n (lh(σ_{N}^{2e+1}) ≥ lh(σ_{N}^{2e}) and lh(σ_{ω}^{2e+1}) ≥ lh(σ_{ω}^{2e})).

(4) ∀s ∈ N ∃e (s ∈ Range(σ_{N}^{2e+1})) and ∀y ∈ ω ∃e (y ∈ Range(σ_{ω}^{2e+1})).

(5) ∀p ∀x ∈ (σ_{N}^{p})^{−1}(Σ^{𝔅}) ∃e (x ∈ σ_{ω}^{2e+1}(2ω)).

(6) ∀e ( if S_{e} ⊆ Reg_{𝔅} then (σ_{2e+2} ∈ S_{e} ∨ ∀τ ⊇ σ_{2e+2} (τ ∉ S_{e}))), where S_{e} is the e-th search computable in 𝔅 set in some given enumeration of all the sets from SC(𝔅), and Reg_{𝔅} is the set of the 𝔅-regular pair of strings.

These requirements guarantee that f = ⋃_{q=0}^{∞} σ_{q} will be a 𝔅-generic regular enu-

meration and A = f_{N}^{−1}(Σ).

Stage 2e+1 Suppose σ_{q} is defined, for q = 2e. Define σ_{N}^{q+1} to extend σ_{N}^{q} with new elements and to have the property (2) defined in the previous lemma. If (σ_{N}^{q})^{−1}(Σ^{𝔅}) is empty, we define σ_{ω}^{q+1} = σ_{ω}^{q}, otherwise define σ_{ω}^{q+1} to extend σ_{ω}^{q} with the first two elements x_{0} ∈ 2ω \ Dom(σ_{ω}^{q}) and x_{1} ∈ (2ω + 1) \ Dom(σ_{ω}^{q}), for which:

• σ_{ω}^{q+1}(x_{1}) = the first y s.t. y ∉ Range(σ_{ω}^{q});

• σ_{ω}^{q+1}(x_{0}) = the first y s.t. y ∈ (σ_{ω}^{q})^{−1}(Σ^{𝔅}) \ σ_{ω}^{q}(2ω) if not empty, or the first y ∈ (σ_{ω}^{q})^{−1}(Σ^{𝔅}) otherwise.

Stage 2e+2 Suppose σ_{q} is defined, for q = 2e + 1. Let G be the set of all pairs of strings having the properties (1) and (2) from the previous lemma. We have two possibilities:

Case 1. ∃σ ⊇ σ_{q} (σ ∈ G & (σ ∈ S_{e} ∨ ∀τ ⊇ σ (τ ∉ S_{e}))). Define σ_{q+1} to be the first such σ.

Case 2. Otherwise define σ_{q+1} = σ_{q}.

Now it can be verified that this construction meets the requirements (3) to (6), defined earlier in the current proof. For example to verify (6) we can use the previous lemma to show that Case 2 never happens if S_{e} is a set of 𝔅-regular pair of strings.

□

Theorem 4.8 Let a structure 𝔅(Σ^{𝔅}) with one predicate ∅ ≠ Σ^{𝔅} ⊆ N^{a} × ω^{b}, be given.

Then for any predicate A ⊆ ω, A is 𝔅-generic if and only if there exist a predicate Σ ⊆ N, such that ∅ ≠ Σ ≤_{SC} 𝔅 and ∅ ≠ \overline{Σ} ≤_{SC} 𝔅, and there exists a 𝔅-generic regular enumeration f, such that A = f_{N}^{−1}(Σ).

Proof:

(⇐) The Proposition 4.5-4.

(⇒) Consider the predicate Σ = {s} for which it is clear that ∅ ≠ Σ ≤_{SC} 𝔅 and ∅ ≠ \overline{Σ} ≤_{SC} 𝔅. From previous proposition it follows that there exists a 𝔅-generic regular enumeration f, such that A = f_{N}^{−1}(Σ).

□

Acknowledgements. The author is deeply indebted to Tinko Tinchev for all the advice and encouragement for the realization of this paper.

References

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

[2] Moschovakis, Y.N., Abstract first order computability, Transaction of the American Mathematical Society, vol.138 (1969), pp.427-464.

[3] Skordev, D.G., Computability in Combinatory Spaces, vol.55, Kluwer Academic Publishers, (1992).

[4] Soskov, I.N., Intrinsically Π_{1}^{1} Relations, Mathematical Logic Quarterly, vol.42 (1996), pp.109-126.

[5] Soskov, I.N., A jump inversion theorem for the enumeration jump,Arch. Math. Logic, vol.39 (2000), pp.417-437.

[6] Boutchkova, V., Relative Set Genericity, Annuaire de l’Université de Sofia ”St.Kliment Ohridski”, vol.94 (2001).