On the Abstract Computability in Two-sort Structures

V.Boutchkova

Sofia University ”St.Kl.Ohridski”, Part of the Master’s Thesis

November, 1998

1 Computability in N^{∗}

Basic notions and definitions

Let N be an arbitrary countable set. Take 0^{∗} which is not an element of N and an operation ordered pair, denoted by ⟨·, ·⟩ such that no element of N ∪ {0^{∗}} is an ordered pair. By induction we define the sets N_{0} = N ∪ {0^{∗}} and N_{n+1} = N_{n} ∪ N_{n}^{2}, where N_{n}^{2} = {⟨a, b⟩ | a ∈ N_{n} & b ∈ N_{n}}. Finally, define

the Moskovakis’ extension of N, N^{∗} = ⋃_{n=0}^{∞} N_{n}.

For s_{1} … s_{n+1} ∈ N^{∗} we use ⟨s_{1}, …, s_{n+1}⟩ to denote ⟨s_{1}, ⟨s_{2}, …, s_{n+1}⟩⟩. Recall that ω is the set of all natural numbers. By induction we define

the set ω^{∗} ⊆ N^{∗} as follows:

| \begin{matrix}0^{∗} ∈ ω^{∗} \\ (n + 1)^{∗} = ⟨0^{∗}, n^{∗}⟩ ∈ ω^{∗} \end{matrix}

Define the left and right functions L and R : N^{∗} ⊸→ N∗ as follows:

| \begin{matrix}L(0^{∗}) = R(0^{∗}) = 0^{∗} \\ L(n) = R(n) = 1^{∗} & for n ∈ N \\ L(⟨s, t⟩) = s, R(⟨s, t⟩) = t \end{matrix}

By F we denote the set of one argument partial functions φ : N^{∗} ⊸→N^{∗}. Define the following operations on functions in F :

1. composition (φ ∘ ψ) ∈ F (∀s ∈ N^{∗}) (∀t ∈ N^{∗}) (φ ∘ ψ)(s) = t ⇔ (∃p ∈ N^{∗})(ψ(s) = p & φ(p) = t)

2. pairing Π(φ, ψ) ∈ F (∀s ∈ N^{∗}) (∀t ∈ N^{∗})

Π(φ, ψ)(s) = t ⇔ (∃p, q ∈ N^{∗}) (⟨p, q⟩ = t & φ(s) = p & ψ(s) = q)

3. iteration [φ, ψ] ∈ F (∀s ∈ N^{∗}) (∀t ∈ N^{∗}) [φ, ψ](s) = t ⇔ ∃w_{0}, …, w_{n} ∈ N^{∗} (w_{0} = s & w_{n} = t & ψ(t) ∈ N_{0} & ∀i_{(0≤i<n)}(φ(w_{i}) = w_{i+1} & ψ(w_{i}) ∉ N_{0}))

We define the constant functions as follows: if c ∈ N^{∗}, by č we denote the function č: N^{∗} ⊸→ N^{∗}, such that č(s) = c for all s ∈ N^{∗}.

Definition 1.1 The function φ ∈ F is said to be prime computable using constants, relatively the set {ψ_{1}, …, ψ_{k}}, where ψ_{i} ∈ F (write φ ∈ PC(ψ_{1} … ψ_{k})), if it can be expressed with functions from {L, R, ψ_{1}, …, ψ_{k}} ∪ {č_{1}, …, č_{n}, … }, where č_{1}, …, č_{n}, … is an enumeration of the elements of N, using composition, pairing and iteration. The function φ is said to be prime computable with constants (write φ ∈ PC), if it is prime computable relatively the empty set of functions, i.e. φ ∈ PC(∅).

The function φ ∈ F is said to be prime computable relatively the set {ψ_{1}, …, ψ_{k}} (write φ ∈ P C(ψ_{1} … ψ_{k})), if it can be expressed with functions from {L, R, ψ_{1}, …, ψ_{k}} using composition, pairing and iteration. The definition of φ ∈ P C is analogous.

Definition 1.2 The function φ ∈ F is said to be search computable using constants, relatively ψ_{1}, …, ψ_{k} ∈ F, write φ ∈ SC(ψ_{1} … ψ_{k}), if there exists a function ψ ∈ PC(ψ_{1}, …, ψ_{k}), such that

(∀s ∈ N^{∗}) (∀t ∈ N^{∗}) (φ(s) = t ⟺ ∃r ∈ N^{∗}(ψ(⟨r, s⟩) = t)).

In the same way we define φ ∈ SC, φ ∈ SC(ψ_{1} … ψ_{k}) and φ ∈ SC.

Examples The following functions are P C :

\begin{matrix}1. 0(s) = 0^{∗} for s ∈ N^{∗} & \overline{0} = L^{3} ∘ [L, L] \\ \overline{n}(s) = n^{∗} & \overline{(n + 1)} = Π(\overline{0}, \overline{n}) \end{matrix}

2. I(s) = s for s ∈ N^{∗} I = [L, \overline{0}]
3. The nowhere defined function ∅^{∗} : ∅^{∗} = [I, I] ∘ Π(I, I)
4. χ_{N_{0}}(s) = \begin{cases}0^{∗} & , s ∈ N_{0} \\ 1^{∗} & , s ∈ N^{∗} \ N_{0} \end{cases} χ_{N_{0}} = L ∘ [Π(\overline{1}, \overline{0}), R] ∘ Π(\overline{0}, I)

5. Sg(s) = \begin{cases}0^{∗} & , s = 0^{∗} \\ 1^{∗} & , s ∈ N^{∗} \ \{0^{∗}\} \end{cases} Sg = L ∘ [Π(\overline{1}, \overline{0}), R] ∘ Π(L, I)
6. \overline{Sg}(s) = \begin{cases}0^{∗} & , Sg(s) = 1^{∗} \\ 1^{∗} & , Sg(s) = 0^{∗} \end{cases}  \overline{Sg} = L ∘ [Π(\overline{0}, \overline{0}), R] ∘ Π(\overline{1}, Sg)

7. χ_{ω^{∗}}(s) = \begin{cases}0^{∗} & , s ∈ ω^{∗} \\ 1^{∗} & , s ∈ N^{∗} \ ω^{∗} \end{cases}  χ_{ω^{∗}} = L ∘ [φ, R] ∘ Π(L, I), where

φ(⟨s, ⟨s, t⟩⟩) = \begin{cases}⟨1^{∗}, 0^{∗}⟩ & , s ≠ 0^{∗} \\ ⟨L(t), t⟩ & , s = 0^{∗} \end{cases}  \begin{matrix}φ = L ∘ [ψ, \overline{Sg} ∘ L ∘ R] ∘ Π(Π(\overline{1}, \overline{0}), I) \\ and ψ = Π(Π(L ∘ R^{3}, R^{3}), L) \end{matrix}

8. And(s) = \begin{cases}0^{∗} & L(s) = R(s) = 0^{∗} \\ 1^{∗} & otherwise \end{cases} And = Sg ∘ L ∘ [Π(\overline{1}, \overline{0}), Sg ∘ R]

Or(s) = \begin{cases}0^{∗} & L(s) = 0^{∗} or R(s) = 0^{∗} \\ 1^{∗} & otherwise \end{cases} Or = \overline{Sg} ∘ And ∘ Π(\overline{Sg} ∘ L, \overline{Sg} ∘ R)

\begin{aligned}9. & N^{k} = \{⟨s_{1} … s_{k}⟩ | s_{1}, …, s_{k} ∈ N\} \\ & N^{1} = N \end{aligned}

χ_{n^{k}}(s) = \begin{cases}0^{∗} & , s ∈ N \\ 1^{∗} & , s ∉ N \end{cases}  \begin{matrix}χ_{N} = \overline{Sg} ∘ [\overline{0}, I] \\ χ_{N^{k+1}} = And ∘ Π(χ_{N} ∘ L, χ_{N^{k}} ∘ R) \end{matrix}

10. If φ ∈ P C(ψ_{1}, …, ψ_{n}), ψ ∈ P C(ψ_{1}, …, ψ_{n}) and ξ ∈ P C(ψ_{1}, …, ψ_{n}), then the function If(ξ, φ, ψ) is P C(ψ_{1}, …, ψ_{n}), where

If(ξ, φ, ψ)(s) = \begin{cases}φ(s) & , if ξ(s) ∈ N_{0} \\ ψ(s) & , if ξ(s) ∈ N^{∗} \ N_{0} \end{cases}

If(ξ, φ, ψ) = L ∘ [Π(φ ∘ L, Π(\overline{1}, \overline{0})), \overline{Sg} ∘ L ∘ R] ∘ [Π(ψ ∘ L, Π(\overline{1}, \overline{0})), R^{2}]∘ Π(I, Π(I, I) ∘ χ_{N_{0}} ∘ ξ)

11. If φ ∈ P C(ψ_{1}, …, ψ_{n}) and ψ ∈ P C(ψ_{1}, …, ψ_{n}), then there exists a function χ ∈ P C(ψ_{1}, …, ψ_{n}), such that:

| \begin{matrix}χ(⟨0^{∗}, s⟩) & ≃ & φ(s) \\ χ(⟨(x + 1)^{∗}, s⟩) & ≃ & ψ(⟨x^{∗}, s, χ(⟨x^{∗}, s⟩)⟩) \end{matrix} ,

for all s ∈ N^{∗} and x ∈ ω^{∗}; in the other cases χ is not defined. χ = If(ζ, ξ, ∅^{∗}), where ζ = And(\overline{(}Sg) ∘ χ_{N_{0}}, χ_{ω^{∗}}) and ξ = R^{3} ∘ ξ_{2} ∘ ξ_{1}, where ξ_{1} = Π(L, Π(\overline{0}, Π(I, φ) ∘ R)), ξ_{2} = [Π(R ∘ L, Π(Π(\overline{0}, L), Π(L ∘ R, ψ)) ∘ R), L].

12. If ψ ∈ P C(ψ_{1}, …, ψ_{n}), then there exists a function φ ∈ P C(ψ_{1}, …, ψ_{n}), such that:

φ(s) ≃ μ^{∗}x_{x^{∗}∈ω^{∗}}^{∗}[ψ(⟨x^{∗}, s⟩) ∈ N_{0}],

i.e. Rng(φ) ⊆ ω^{∗} and φ(s) = x^{∗} ⇔ ψ(⟨x^{∗}, s⟩) ∈ N_{0} & ∀y < x (ψ(⟨y^{∗}, s⟩) ↓ & (ψ(⟨y^{∗}, s⟩) ∉ N_{0}), for all s ∈ N^{∗}. Indeed φ = L ∘ [Π(Π(\overline{0}, L), I), ψ] ∘ Π(\overline{0}, I).

The proof of 10, 11 and 12 for PC is similar.

Definition 1.3 Having the partial function ρ : ω^{n} ⊸→ ω, we can define its corresponding function ρ^{∗} ∈ F as follows:

for n ≥ 2 : ρ^{∗}(s) = t ⇔  ∃x_{1} … x_{n}, y ∈ ω (s = ⟨x_{1}^{∗} … x_{n}^{∗}⟩ &
y^{∗} = t & ρ(x_{1}, …, x_{n}) = y);
for n = 1 : ρ^{∗}(s) = t ⇔ ∃x, y ∈ ω (s = x^{∗} & y^{∗} = t & ρ(x) = y),
for all s and t in N^{∗}.

Proposition 1.4 If the function ρ : ω^{n} ⊸→ ω is partial recursive relatively ψ_{1}, …, ψ_{k}, where each ψ_{i} : ω^{n_{i}} ⊸→ ω, then ρ^{∗} ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}).

Proof:

Since ρ is partial recursive relatively ψ_{1}, …, ψ_{k}, it can be expressed with functions from {O, S, I_{1}^{m}, … I_{m}^{m}} ∪ {ψ_{1}, …, ψ_{k}}, using superposition, prime recursion and minimization. We will prove that ρ^{∗} ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}) using induction of the structure of ρ :

Let ρ = O. Define ρ^{∗′} = \overline{0}. Then ρ^{∗} = If(χ_{ω^{∗}}, ρ^{∗′}, ∅^{∗}) ∈ P C;

Let ρ = S and define ρ^{∗′} = Π(\overline{0}, I). Then ρ^{∗} = If(χ_{ω^{∗}}, ρ^{∗′}, ∅^{∗}) ∈ P C; Let ρ = I_{i}^{m} and define ρ^{∗} = L ∘ R^{i−1} ∈ P C for m > 1, and for m = 1

define ρ^{∗} = I ∈ P C.

Superposition: Let ρ(x_{1} … x_{n}) ≃ f(g_{1}(x_{1} … x_{n}) … g_{s}(x_{1} … x_{n})) and f, g_{1}, …, g_{s} are partial recursive relatively ψ_{1}, …, ψ_{k}. By the induction hypothesis it follows that f^{∗}, g_{1}^{∗}, …, g_{s}^{∗} ∈ P C(ψ_{1}^{∗}, …, ψ_{m}^{∗}). But ρ^{∗} = f^{∗} ∘ Π_{s}(g_{1}^{∗} … g_{s}^{∗}), where Π_{1}(g^{∗}) = g^{∗}, and Π_{s+1}(g_{1}^{∗} … g_{s+1}^{∗}) = Π(g_{1}^{∗}, Π_{s}(g_{2}^{∗} … g_{s+1}^{∗})) are P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}) and therefore so is ρ^{∗}.

Prime recursion: Let

| \begin{matrix}ρ(0, \overline{y}) & ≃ & φ(\overline{y}) \\ ρ(x + 1, \overline{y}) & ≃ & ψ(x, \overline{y}, ρ(x, \overline{y})) \end{matrix}

where φ and ψ are partial recursive relatively ψ_{1}, …, ψ_{k} and then φ^{∗}, ψ^{∗} ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}). But (see ex.11) there exists χ ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}), such that χ = P r(φ^{∗}, ψ^{∗}), i.e.

| \begin{matrix}χ(⟨0^{∗}, s⟩) & ≃ & φ^{∗}(s) \\ χ(⟨x + 1, s⟩) & ≃ & ψ^{∗}(⟨x^{∗}, s, χ(⟨x^{∗}, s⟩)⟩) \end{matrix}

But ρ^{∗} = χ = P r(φ^{∗}, ψ^{∗}) and therefore ρ^{∗} ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}).

Minimization: Let ρ(x_{1} … x_{n}) ≃ μy[ψ(y, x_{1} … x_{n}) = 0] and ψ is partial recursive relatively ψ_{1}, …, ψ_{k}. Then ψ^{∗} ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}), but (see ex.12) there exists φ ∈ P C(ψ_{1}^{∗}, …, ψ_{k}^{∗}) and s.t. φ(s) ≃ μ^{∗}x_{x_{∗}∈ω^{∗}}^{∗}[ψ^{∗}(⟨x^{∗}, s⟩) ∈ N_{0}], i.e. φ(s) = x^{∗} ⇔ ψ^{∗}(⟨x^{∗}, s⟩) ∈ N_{0} & ∀y < x (ψ^{∗}(⟨y^{∗}, s⟩) ↓∉ N_{0}), for all s ∈ N^{∗}. Then φ(s) = t ⇔ ∃z, x_{1} … x_{n} ∈ ω (s = ⟨x_{1} … x_{n}⟩ & t = z^{∗} & ψ^{∗}(⟨z^{∗}, s⟩) = 0^{∗} & ∀y < z (ψ^{∗}(⟨y^{∗}, s⟩) ↓≠ 0^{∗})), i.e. φ(s) = t if and only if ∃z, x_{1} … x_{n} ∈ ω (s = ⟨x_{1} … x_{n}⟩ & t = z^{∗} & ψ(z, x_{1} … x_{n}) = 0 & ∀y < z ψ(y, x_{1} … x_{n}) ⇓≠ 0), i.e. ρ^{∗} = φ = μ^{∗}x^{∗}[ψ^{∗}(⟨x^{∗}, ·⟩) ∈ N_{0}] ∈ P C(ψ_{1}^{∗} … ψ_{k}^{∗}).

□

We have the following: P C ⊆ SC, PC⊆ SC, P C ⊆ PC and SC ⊆ SC. In the general case the constant functions are prime computable using

constants: č ∈ PC, for all c ∈ N^{∗}. And č ∈ P C, for all c ∈ ω^{∗}.

2 Abstract structures

Definition 2.1 Let ω be the set of all the natural numbers and N be a countable set. A structure we will call an abstract partial two-sort structure

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

with two fixed (basic) predicates in N^{2} - equality in N (=_{N}) and inequality in N (≠_{N}). Σ_{1}, … Σ_{k} are partial predicates, Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, a_{i}, b_{i} ≥ 0 and are not both zero, for all i, 1 ≤ i ≤ k. This kind of structure will be denoted as 𝔄(Σ_{1} … Σ_{k}).

Definition 2.2 For any predicate Σ ⊆ N^{a} × ω^{b} we define its semicharacteristic function Σ̂ : N^{∗} ⊸→ N^{∗}, Σ̂ ∈ F, as follows: Rng(Σ̂) ⊆ {0^{∗}} and for all s ∈ N^{∗}

Σ̂(s) = 0^{∗} if and only if

∃s_{1} … s_{a} ∈ N ∃x_{1}, … x_{b} ∈ ω (s = ⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}⟩ & (s_{1} … s_{a}, x_{1} … x_{b}) ∈ Σ).

Examples: =_{N}= {(n, n) | n ∈ N}, ˆ=_{N}(s) = 0^{∗} ↔ ∃n ∈ N (s = ⟨n, n⟩) ≠_{N}= \overline{=_{N}} = \{(n, m) | n, m ∈ N & n ≠ m\}

ˆ≠_{N}(s) = 0^{∗} ↔ ∃n ∈ N∃m ∈ N (s = ⟨n, m⟩) & n ≠ m).

Definition 2.3 Let 𝔄 = ⟨Σ_{1}^{𝔄}, …, Σ_{m}^{𝔄}⟩ and 𝔅 = ⟨Σ_{1}^{𝔅}, …, Σ_{n}^{𝔅}⟩ be structures and Σ_{0}, Σ_{1}, …, Σ_{k} be predicates.

1. Σ_{0} ≤_{SC} {Σ_{1}, …, Σ_{k}} if and only if Σ̂_{0} ∈ SC(Σ̂_{1}, …, Σ̂_{k});

2. Σ_{0} ≤_{SC} 𝔄 if and only if Σ_{0} ≤_{SC} {=_{N}, ≠_{N}, Σ_{1}^{𝔄}, …, Σ_{m}^{𝔄}};

3. 𝔄 ≤_{SC} 𝔅 if and only if ∀i_{1≤i≤m} Σ_{i}^{𝔄} ≤_{SC} 𝔅;

4. 𝔄⊕𝔅 = ⟨N; ω; =_{N}, ≠_{N}; Σ_{1}^{𝔄} … Σ_{m}^{𝔄}, Σ_{1}^{𝔅} … Σ_{n}^{𝔅}⟩ = ℭ(Σ_{1}^{𝔄} … Σ_{m}^{𝔄}, Σ_{1}^{𝔅} … Σ_{n}^{𝔅}).

5. 𝔄 ≡_{SC} 𝔅 if and only if 𝔄 ≤_{SC} 𝔅 and 𝔅 ≤_{SC} 𝔄.

In the same way we define the relation ≤_{SC} (without constants) but henceforth we consider the relation ≤_{SC} only.

The relation ≤_{SC} is a preorder (reflexive and transitive relation), and ≡_{SC} is an equivalence relation.

S-degrees or structure degrees we call the equivalence classes, induced by the relation ≡_{SC} between structures: given a structure 𝔄, an S-degree of 𝔄 we denote its structure degree by 𝔇_{S}(𝔄) and mean the set {𝔅 | 𝔅 ≡_{SC} 𝔄}.

The set {𝔇_{S}(𝔄) | 𝔄 is an abstract structure} we denote by 𝔇. For 𝔄 and 𝔟 in 𝔇, 𝔞 ≤_{sc} 𝔟 if and only if there exist structures 𝔄 in 𝔞 and 𝔅 in 𝔟, such that 𝔄 ≤_{SC} 𝔅. For 𝔞 and 𝔟 in 𝔇 and for 𝔄 ∈ 𝔞 and 𝔅 ∈ 𝔟 we define 𝔞 ∪ 𝔟 = 𝔇_{s}(𝔄 ⊕ 𝔅). So the structure S = ⟨𝔇, ≤_{SC}, ∪, 𝔒⟩ is an upper semilattice with least element the empty structure 𝔒 = ⟨N; ω; =_{N}, ≠_{N}⟩.

Lemma 2.4 The following functions are prime computable (PC ):

1. The functions φ_{n,m}, defined as follows:

φ_{0,1}(s) = \begin{cases}0^{∗} & , if s ∈ ω^{∗} \\ 1^{∗} & , otherwise \end{cases} and φ_{1,0}(s) = \begin{cases}0^{∗} & , if s ∈ N \\ 1^{∗} & , otherwise \end{cases} and

for n + m ≥ 2, φ_{n,m}(s) = \begin{cases}0^{∗} & , for s = ⟨s_{1} … s_{n}, t_{1} … t_{m}⟩ where \\ & s_{1}, …, s_{n} ∈ N and t_{1}, …, t_{m} ∈ ω^{∗} \\ 1^{∗} & , otherwise \end{cases} .

Indeed φ_{0,1} = χ_{ω^{∗}}, φ_{0,m+1} = And ∘ Π(\overline{Sg} ∘ χ_{N_{0}}, And ∘ Π(χ_{ω^{∗}} ∘ L, φ_{0,m} ∘ R)) for m ≥ 1, φ_{1,0} = χ_{N} , φ_{n+1,m} = And ∘ Π(χ_{N} ∘ L, φ_{n,m} ∘ R), for m ≥ 0 and n ≥ 0 and n + m ≥ 1.

2. The functions ψ_{n,m}, where for all u and s_{j} in N^{∗}, ψ_{n,m}(⟨u, ⟨s_{1} … s_{n}, … ⟩) =

⟨s_{1} … s_{n}, \underbrace{u … u}_{m times}, … ⟩, n ≥ 0, m ≥ 0.

Indeed ψ_{0,m+1} = ψ_{0,m} ∘ Π(L, I), for m ≥ 0; and ψ_{n+1,m} = Π(L ∘ R, ψ_{n,m} ∘ Π(L, R^{2})), for n, m ≥ 0. Therefore ψ_{n,m} ∈ P C.

3. The functions γ_{p}^{i}, such that for all s_{1}, …, s_{p} ∈ N^{∗} and p ≥ 1, i ∈ ω, γ_{p}^{i}(⟨s_{1} … s_{p}⟩) = ⟨s_{1} … s_{p}, i^{∗}⟩ = ⟨s_{1}, ⟨s_{2} … ⟨s_{p}, i^{∗}⟩ … ⟩⟩.

Indeed γ_{1}^{i} = Π(I, \overline{i^{∗}}), γ_{p+1}^{i} = Π(L, γ_{p}^{i} ∘ R), i.e. γ_{p}^{i} = ψ_{p,i} ∘ Π(\overline{i^{∗}}, I). Therefore γ_{p}^{i} ∈ P C.

4. The functions Lt_{n}, n ≥ 1, such that for u, s_{j} in N^{∗}, Lt_{n}(⟨s_{1} … s_{n}⟩) = s_{n}.

Indeed Lt_{1} = I and Lt_{n+1} = Lt_{n} ∘ R, for n ≥ 1.

5. The functions F st_{n}, n ≥ 1, such that for u, s_{j} in N^{∗}, F st_{n}(⟨s_{1} … s_{n} … ⟩) = ⟨s_{1} … s_{n}⟩.

Indeed F st_{1} = L and F st_{n+1} = Π(L, F st_{n} ∘ R), for n ≥ 1.

□

Corollary 2.5

For every structure 𝔅^{k}(Σ_{1} … Σ_{k}) with predicates Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, 1 ≤ i ≤ k, there exists a structure 𝔅 with one predicate 𝔅(Σ), Σ ⊆ N^{a} × ω^{b+1}, where a = max{a_{i} | 1 ≤ i ≤ k} and b = max{b_{i} | 1 ≤ i ≤ k}, such that 𝔅^{k} ≡_{SC} 𝔅.

Proof:

Let a = max{a_{i} | 1 ≤ i ≤ k} and b = max{b_{i} | 1 ≤ i ≤ k} and define a predicate Σ ⊆ N^{a} × ω^{b+1}, as follows:

Σ = {(s_{1} … s_{a}, x_{1} … x_{b}, i) | 1 ≤ i ≤ k & s_{1} … s_{a} ∈ N & x_{1} … x_{b} ∈ ω &

(s_{1} … s_{a}, x_{1} … x_{b}) ∈ Σ_{i}}.

Here we prove that fact, but we do not give such explicit proof in the rest of this paper.

1) 𝔅^{k} ≤_{SC} 𝔅, proof: For every predicate Σ_{i}, 1 ≤ i ≤ k, for all s ∈ N^{∗}, Σ̂_{i}(s) = 0^{∗} iff s = ⟨s_{1} … s_{a_{i}}, x_{1}^{∗} … x_{b_{i}}^{∗}⟩ & (s_{1} … s_{a_{i}}, x_{1} … x_{b_{i}}) ∈ Σ_{i}, i.e. iff s = ⟨s_{1} … s_{a_{i}}, x_{1}^{∗} … x_{b_{i}}^{∗}⟩ & (∃r ∈ N^{∗}) (r = ⟨r_{1} … r_{a}, p_{1} … p_{b}, c⟩ & r_{1} =_{N} s_{1} & … & r_{a_{i}} =_{N} s_{a_{i}} & p_{1} =_{N} t_{1} & … &p_{b_{i}} =_{N} t_{b_{i}} & c =_{N} i^{∗} & Σ̂(r) = 0^{∗}), that is Σ̂_{i} = If(φ_{a_{i},b_{i}}, Σ̂ ∘ ψ_{i} ∘ γ_{a_{i}+b_{i}}^{i}, ∅^{∗}), where φ_{a_{i},b_{i}} and γ_{a_{i}+b_{i}}^{i} defined in Lemma2.4 are prime computable, and the function ψ_{i} is such that for all s_{1} …, s_{a_{i}}, t_{1} … t_{b_{i}}, p ∈ N^{∗},

ψ_{i}(⟨s_{1} … s_{a_{i}}, t_{1} … t_{b_{i}}, p⟩) = ⟨s_{1} … s_{a_{i}}, \underbrace{c … c}_{a−a_{i} times}, t_{1} … t_{b_{i}}, \underbrace{d … d}_{b−b_{i} times}, p⟩, where

c ∈ N and d ∈ ω^{∗} are constants, ψ_{i} ∈ PC is prime computable with constants c, since ψ_{i} = ψ_{a_{i},a−a_{i}} ∘Π(ĉ, I)∘ψ_{a_{i}+b_{i},b−b_{i}} ∘Π(d̂, I), where the functions ψ_{a_{i},a−a_{i}} and ψ_{a_{i}+b_{i},b−b_{i}} defined in Lemma2.4(2) are prime computable (PC ). Then Σ̂_{i} ∈ SC( ˆ=_{N}, ˆ≠_{N}, Σ̂), i.e. Σ_{i} ≤_{SC} (𝔅), i.e. 𝔅^{k} = (Σ_{1} … Σ_{k}) ≤_{SC} 𝔅.

2) 𝔅 ≤_{SC} 𝔅^{k}, proof: Σ̂(r) = 0^{∗} iff s = ⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}, i^{∗}⟩ & (s_{1} … s_{a}, x_{1} … x_{b}, i) ∈ Σ iff s = ⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}, i^{∗}⟩ & 1 ≤ i ≤ k & s_{1} … s_{a} ∈ N & x_{1} … x_{b} ∈ ω & (s_{1} … s_{a_{i}}, x_{1} … x_{b_{i}}) ∈ Σ. Σ̂ = If(And(φ_{a_{i},b+1}, φ_{k} ∘ Lt_{a+b+1}), ψ_{k}, ∅^{∗}), where φ_{a,b+1} and Lt_{a+b+1} are defined in Lemma2.4 and φ_{k} is such that for Dom(φ_{k}) = ω^{∗} and φ_{k}(x^{∗}) = 0^{∗} iff 1 ≤ x & x ≤ k, i.e. φ_{k} = If(χ_{ω^{∗}}, And(δ^{∗}, ρ_{k}^{∗}), ∅^{∗}), where δ and ρ_{k} are functions from ω into ω, δ(x) = 0 ⇔ 1 ≤ x, and ρ_{k}(x) = 0 iff x ≤ k, and δ^{∗} and ρ^{∗} are prime computable, see Proposition 1.4. The functions ψ_{k} is such that ψ_{k}(⟨s_{1} … s_{a}, x_{1}^{∗} … x_{b}^{∗}, i^{∗}⟩) = Σ̂_{i}(⟨s_{1} … s_{a_{i}}, x_{1}^{∗} … x_{b_{i}}^{∗}⟩), for 1 ≤ i ≤ k. Indeed ψ_{1} = If(ρ_{1}^{∗}, Σ̂_{1}∘F st_{a_{1}+b_{1}}, ∅^{∗}), that is ψ_{1} ∈ P C(Σ̂_{1}); and ψ_{k} = If(ρ_{k}^{∗}, Σ̂_{k}∘F st_{a_{k}+b_{k}}, ψ_{k−1}) ∈ P C(Σ̂_{1}, …, Σ̂_{k}). Therefore Σ̂ ∈ P C(Σ̂_{1} … Σ̂_{k}) and 𝔅 ≤_{SC} 𝔅^{k}.

□

3 N-enumerations

Definition 3.1 An N-enumeration is a total and surjective function f_{N} : ω → N. Define the following sets:

1. f_{N}^{−1}(Σ) := {⟨x_{1} … x_{a}, y_{1} … y_{b}⟩ ∈ ω| (f_{N}(x_{1}) … f_{n}(x_{a}), y_{1} … y_{b}) ∈ Σ}.

2. E_{f} := {⟨x, y⟩ ∈ ω | f_{N}(x) =_{N} f_{N}(y)} = f_{N}^{−1}(=_{N}); \overline{E_{f}} := \{⟨x, y⟩ ∈ ω | f_{N}(x) ≠_{N} f_{N}(y)\} = f_{N}^{−1}(≠_{N}); and E_{f}^{+} := E_{f} ⊕ \overline{E_{f}}.

Definition 3.2 Let f^{∗} : ω → N^{∗}. For the functions φ ∈ F and the predicate Σ ⊆ N^{a}×ω^{b}, define:

1. E^{∗} := {⟨x, y⟩ ∈ ω | f^{∗}(x) = f^{∗}(y)}.

2. f^{∗}^{−1}(φ) := {⟨x, y⟩ ∈ ω | φ(f^{∗}(x))} = f^{∗}^{−1}(Gr_{φ}).

3. f^{∗}^{−1}(Σ) := {x ∈ ω | Σ̂(f^{∗}(x)) = 0^{∗}} =

{x | f^{∗}(x) = ⟨s_{1} … s_{a}, y_{1}^{∗} … y_{b}^{∗}⟩ & (s_{1} … s_{a}, y_{1} … y_{b}) ∈ Σ}.

Lemma 3.3 The function f^{∗} : ω → N^{∗} is total and surjective; there exist a recursive function J : ω^{2} → ω, such that for all x, y ∈ ω, f^{∗}(J(x, y)) = ⟨f^{∗}(x), f^{∗}(y)⟩, and there exists a recursively enumerable set X, such that f^{∗}[X] = N. Then for all ψ, φ_{1} … φ_{k} ∈ F, if ψ ∈ SC(φ_{1} … φ_{k}), then f^{∗}^{−1}(ψ) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

Proof:

Since ψ ∈ SC(φ_{1} … φ_{k}), there exists φ ∈ PC(φ_{1} … φ_{n}), such that ψ(s) = t ⇔ (∃u ∈ N^{∗}) (φ⟨u, s⟩) = t). Therefore ⟨x, y⟩ ∈ f^{∗}^{−1}(ψ) ⇔ ψ(f^{∗}(x)) = f^{∗}(y) ⇔ (∃u ∈ N^{∗}) (φ(⟨u, f^{∗}(x)⟩) = f^{∗}(y)) /since f is surjective/ ⇔ (∃t ∈ ω) φ(⟨f^{∗}(t), f^{∗}(x)⟩) = f^{∗}(y)) ⇔ (∃t ∈ ω) (φ(f^{∗}(J(t, x))) = f^{∗}(y)) ⇔ (∃t, z ∈ ω) (J(t, x) = z & φ(f^{∗}(z)) = f^{∗}(y)), therefore f^{∗}^{−1} ≤_{e} f^{∗}^{−1}(φ).

By induction on the definition of PC, we are going to prove that for φ ∈ PC(φ_{1} … φ_{k}), f^{∗}(φ) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}, from which follows that f^{∗}(ψ) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

Let c_{0} and c_{1} ∈ ω be such that

f^{∗}(c_{0}) = 0^{∗} and f^{∗}(c_{1}) = 1^{∗}. Such c_{0} and c_{1} exist, since f^{∗} is a surjective function.

• If φ = L ⟨z, y⟩f^{∗}^{−1}(L) iff L(f^{∗}(z)) = f^{∗}(y) iff f^{∗}(z) = f^{∗}(y) = 0^{∗} ∨ f^{∗}(z) ∈ N & f^{∗}(y) = 1^{∗} ∨ f^{∗}(z) ∈ N^{∗}\N − 0 & ∃x ∈ ω ⟨f^{∗}(y), f^{∗}(x)⟩f^{∗}(z)) iff ⟨z, c_{0}⟩, ⟨y, c_{0}⟩ ∈ E^{∗} ∨ ∃x ∈ X(⟨z, x⟩, ⟨y, c_{1}⟩ ∈ E^{∗}) ∨ ∃x ∈ ω(f^{∗}(J(y, x)) = f^{∗}(z)) iff ⟨z, c_{0}⟩, ⟨y, c_{0}⟩ ∈ E^{∗} ∨ ∃x ∈ X(⟨z, x⟩, ⟨y, c_{1}⟩ ∈ E^{∗}) ∨ ∃x, t ∈ ω(J(y, x) = t & (f^{∗}(t) = f^{∗}(z)) iff ⟨z, c_{0}⟩, ⟨y, c_{0}⟩ ∈ E^{∗} ∨ ∃x ∈ X⟨z, x⟩, ⟨y, c_{1}⟩ ∈ E^{∗}) ∨ ∃x, t ∈ ω(J(y, x) = t & ⟨t, z⟩ ∈ E^{∗}), i.e. f^{∗}^{−1}(L) ≤_{e} E^{∗}, and it follows that f^{∗}^{−1}(L) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

• For φ = L the proof is similar.

• For φ = φ_{i}, 1 ≤ i ≤ k.

f^{∗}^{−1}(φ) = f^{∗}^{−1}(φ_{i}) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

• For φ = ĉ the constant function, for c ∈ N. Therefore f^{∗}^{−1}(φ) = f^{∗}^{−1}(ĉ) = f^{∗}^{−1}(Grĉ) = {⟨x, y⟩ ∈ ω | ĉf^{∗}(x) = f^{∗}(y)} = {⟨x, y⟩ ∈ ω | c = f^{∗}(y)}. Since f^{∗} is surjective, there exists d ∈ ω, such that f^{∗}(d) = c. Then ⟨x, y⟩ ∈ f^{∗}^{−1}(ĉ) iff ⟨x, y⟩ ∈ E^{∗}.

The induction hypothesis for ψ_{1} and ψ_{2} ∈ PC(φ_{1} … φ_{k}), f^{∗}^{−1}(ψ_{j}) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

• Composition φ = ψ_{1} ∘ ψ_{2}. We have the following equivalences ⟨z, y⟩ ∈ f^{∗}^{−1}(φ) ⇔ φ(f^{∗}(z)) = f^{∗}(y) ⇔ ∃s ∈ N^{∗} (ψ_{2}(f^{∗}(z)) = s & ψ_{1}(s) = f^{∗}(y)) and since f^{∗} is surjective, this is equivalent to ∃x ∈ ω ψ(f^{∗}(z)) = f^{∗}(x) & ψ_{1}(f^{∗}(x)) = f^{∗}(y)), i.e. ∃x (⟨z, x⟩ ∈ f^{∗}^{−1}(ψ_{2}) & ⟨x, y⟩ ∈ f^{∗}^{−1}(ψ_{1})), therefore f^{∗}^{−1}(φ) ≤_{e} f^{∗}^{−1}(ψ_{1}) ⊕ f^{∗}^{−1}(ψ_{2}), i.e. f^{∗}^{−1}(φ) ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

• Pairing φ = Π(ψ_{1}, ψ_{2}). Using that f^{∗} is surjective, we obtain the following equivalences ⟨z, y⟩ ∈ f^{∗}^{−1}(φ) ⇔ φ(f^{∗}(z)) = f^{∗}(y) ⇔ ∃s_{1}, s_{2} ∈ N^{∗} (⟨s_{1}, s_{2}⟩ = f^{∗}(y) & ψ(f^{∗}(z)) = s − 1 & ψ_{2}(f^{∗}(z)) = s_{2}) ⇔ ∃x_{1}, x_{2} ∈ ω (⟨f^{∗}(x_{1}), f^{∗}(x_{2})⟩ = f^{∗}(y) & ψ_{1}(f^{∗}(z)) = f^{∗}(x_{1}) & ψ_{2}(f^{∗}(z)) = f^{∗}(x_{2})) ⇔ ∃x_{1}, x_{2} ∈ ω (f^{∗}(J(x_{1}, x_{2})) = f^{∗}(y) & ψ_{2}(f^{∗}(z)) = f^{∗}^{−1}(x_{1}) & ψ_{2}(f^{∗}(z)) = f^{∗}(x_{2})) ⇔ ∃x_{1}, x_{2}, t (J(x_{1}, x_{2}) = t & ⟨t, y⟩ ∈ E^{∗} & ⟨z, x_{1}⟩ ∈ f^{∗}^{−1}(ψ_{1}) & ⟨z, x_{2}⟩ ∈ f^{∗}^{−1}(ψ_{2})), i.e. f^{∗}^{−1}(φ) ≤_{e} f^{∗}^{−1}(ψ_{1}) ⊕ f^{∗}^{−1}(ψ_{2}) ⊕ E^{∗}, therefore f^{∗}^{−1}(φ ≤_{e} f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

• Iteration φ = [ψ_{1}, ψ_{2}]. We have that ⟨z, y⟩ ∈ f^{∗}^{−1}(φ) ⇔ φ(f^{∗}(z)) = f^{∗}(y) ⇔ [ψ_{1}, ψ_{2}](f^{∗}(z)) = f^{∗}(y) ⇔ ψ_{2}(f^{∗}(y)) ↓∈ N_{0} & ∃w_{0}, …, w_{n} ∈ N^{∗} (w_{0} = f^{∗}(z) & w_{n} = f^{∗}(y) & ∀i (0 ≤ i < n) (ψ_{1}(w_{i}) = w_{i+1} & ψ_{2}(w_{i}) ∉ N_{0})), and since f^{∗} is surjective we obtain that the last part is equivalent to ∃x_{0}, … x_{n} ∈ ω (f^{∗}(x_{0}) = f^{∗}(z) & f^{∗}(x_{n}) = f^{∗}(y) & ∀i (0 ≤ i < n) (ψ_{1}(f^{∗}(x_{i})) = f^{∗}(x_{i+1}) & ψ_{2}(f^{∗}(x_{i})) ∉ N_{0})). Therefore ⟨z, y⟩ ∈ f^{∗}^{−1}(φ) ⇔ (ψ_{2}(f^{∗}(y)) = f^{∗}(c_{0}) = 0^{∗} ∨ ψ_{2}(f^{∗}(y)) ∈ N) & ∃x_{0} … x_{n} ∈ ω (⟨x_{0}, z⟩, ⟨x_{n}, y⟩ ∈ E^{∗} & ∀i_{(0≤i<n)} (⟨x_{i}, x_{i+1}⟩ ∈ f^{∗}^{−1}(ψ_{1}) & ψ_{2}(f^{∗}(x_{i})) ↓∈ N^{∗}\N_{0})) ⇔ (⟨y, c_{0}⟩ ∈ f^{∗}^{−1}(ψ_{2}) ∨ ∃t ∈ X(ψ_{2}(f^{∗}(y)) = f^{∗}(t))) & ∃x_{0} … x_{n} ∈ ω (⟨x_{0}, z⟩, ⟨x_{n}, y⟩ ∈ E^{∗} & ∀i_{(0≤i<n)} (⟨x_{i}, x_{i+1}⟩ ∈ f^{∗}^{−1}(ψ_{1}) & ∃t_{i_{1}}, t_{i_{2}}, t_{i} ∈ ω (J(t_{i_{1}}, t_{i_{2}}) = t_{i} & ψ_{2}(f^{∗}(x_{i})) = f^{∗}t_{i}))) ⇔ ∃t ∈ X ∪ {c_{0}} (⟨y, t⟩ ∈ f^{∗}^{−1}(ψ_{2})) & ∃x_{0}, …, x_{n} ∈ ω (⟨x_{0}, z⟨∈ E^{∗} & ⟨x_{n}, y⟨∈ E^{∗} & ∀i_{(0≤i<n)} (⟨x_{i}, x_{i+1}⟩ ∈ f^{∗}^{−1}(ψ_{1}) & ∃t_{i} ∈ Range(J) (⟨x_{i}, t_{i}⟩ ∈ f^{∗}^{−1}(ψ_{2}))), i.e.

f^{∗}^{−1}(φ) ≤_{e} f^{∗}^{−1}(ψ_{1}) ⊕ f^{∗}^{−1}(ψ_{2}) ⊕ E^{∗}, therefore
f^{∗}^{−1}(φ) = leq_{e}f^{∗}^{−1}(φ_{1}) ⊕ … ⊕ f^{∗}^{−1}(φ_{k}) ⊕ E^{∗}.

□

Corollary 3.4 Let f^{∗} : ω → N^{∗} be a total surjective function and J : ω^{2} → ω, such that for all x, y ∈ ω, f^{∗}(J(x, y)) = ⟨f^{∗}(x), f^{∗}(y)⟩ and there is a recursively enumerable set X, such that f^{∗}(X) = N, Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, 0 ≤ i ≤ k, are predicates, such that Σ_{0} ≤ (Σ_{1} … Σ_{k}). Therefore

f^{∗}^{−1}(Σ) ≤_{e} f^{∗}^{−1}(Σ_{1}) ⊕ … ⊕ f^{∗}^{−1}(Σ_{k}) ⊕ E^{∗}.

Proposition 3.5 Let f_{N} : ω → N be an N-enumeration and Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, 0 ≤ i ≤ k, such that Σ_{0} ≤_{SC} (Σ_{1} … Σ_{k}).

Therefore f^{∗}^{−1}(Σ_{0}) ≤_{e} f^{∗}^{−1}(Σ_{1}) ⊕ … ⊕ f^{∗}^{−1}(Σ_{k}) ⊕ E_{f}.

Proof:

Let J(x, y) := 2⟨x, y⟩ + 2, where the pairing is recursive injective functions, for example ⟨x, y⟩ := 2^{x}.(2y + 1) − 1. Then for all t and z, t < J(t, z) and z < J(t, z).

Having f_{N} : ω → N, define a total surjective function f^{∗} : ω → N^{∗}, as follows:

| \begin{matrix}f^{∗}(J(x, y)) & = & ⟨f^{∗}(x), f^{∗}(y)⟩ \\ f^{∗}(2z + 1) & = & f_{N}(z) \\ f^{∗}(0) & = & 0^{∗} \end{matrix}

The set X = {2z + 1 | z ∈ ω} is recursive and f^{∗}(X) = N. Therefore, using Lemma3.3, f^{∗}^{−1}(Σ_{0}) ≤_{e} f^{∗}^{−1}(Σ_{1}) ⊕ … ⊕ f^{∗}^{−1}(Σ_{k}) ⊕ E^{∗}.

There exists a recursive function g, such that y^{∗} = f^{∗}(g(y)), that we define as follow:

| \begin{matrix}g(0) & = & 0 \\ g(y + 1) & = & J(0, g(y)) \end{matrix}

Therefore there exists a recursive function h_{a,b}, such that ⟨f_{N}(z_{1}) … f_{N}(z_{a}), y_{1}^{∗} … y_{b}^{∗}⟩ = ⟨f^{∗}(2z_{a} + 1), f^{∗}(g ∗ y_{1})) … f^{∗}(g(y_{b}))⟩ = f^{∗}(J(2z_{1} + 1, J(…, J(g(y_{b})) …))) = f^{∗}(h_{a,b}(⟨z_{1} … z_{a}, y_{1} … y_{b}⟩)).

1) We can prove that for every predicate Σ ⊆ N^{a} × ω^{b}, f^{∗}^{−1}(Σ) ≤ E^{∗} ⊕ f_{N}^{−1}(Σ), from which follows that f^{∗}^{−1}(Σ_{0}) ≤_{e} f_{N}^{−1}(Σ_{1})⊕…⊕f_{N}^{−1}(Σ_{k})⊕ E^{∗}. Indeed x ∈ f^{∗}^{−1}(Σ) ⟺ Σ̂(f^{∗}(x)) = 0^{∗} ⟺ ∃s_{1} … s_{a} ∈ N ∃y_{1} … y_{b} ∈ ω (f^{∗}(x) = ⟨s_{1} … s_{a}, y_{1}^{∗} … y_{b}^{∗}⟩ & (s_{1} … s_{a}, y_{1} … y_{b}) ∈ Σ) ⟺ ∃z_{1}z._{a}, y_{1} … y_{b} ∈ ω (f^{∗}(x) = ⟨f_{N}(z_{1})⟨f_{N}(z_{a}), y_{1}^{∗} … y_{b}^{∗}⟩ & (f_{N}(z_{1}) … f_{N}(z_{a}), y_{1} … y_{b}) ∈ Σ) ⇔ ∃z_{1} … z_{a}, y_{1} … y_{b} (f^{∗}(x) = f^{∗}(h_{a,b}(⟨z_{1} … z_{a}, y_{1} … y_{b}⟩)) & ⟨z_{1} … z_{a}, y_{1} … y_{b}⟩ ∈ f_{N}^{−1}(Σ)) ⇔ ∃z_{1} … z_{a}, y_{1} … y_{b} (⟨x, ⟨z_{1} … z_{a}, y_{1}⟨y_{b}⟩⟩ ∈ E^{∗} & ⟨z_{1} … z_{a}, y_{1} … y_{b}⟩ ∈ f_{N}^{−1}(Σ)).

Therefore f^{∗}^{−1}(Σ_{0}) ≤_{e} f^{∗}^{−1}(Σ_{1}) ⊕ … ⊕ f^{∗}^{−1}(Σ_{k}) ⊕ E^{∗} ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ E^{∗}.

2) We can prove that for every predicate Σ ⊆ N^{a} ×ω^{b}, f_{N}^{−1}(Σ) ≤_{e} f^{∗}^{−1}(Σ)⊕ E^{∗}. Indeed ⟨x_{1} … x_{a}, y_{1} … y_{b}⟩ ∈ f_{N}^{−1}(Σ) ⇔ (f_{N}(x_{1}) … f_{N}(x_{a}), y_{1} … y_{b}) ∈ Σ ⇔ ∃s ∈ N^{∗} (Σ̂(s) = 0^{∗} & 4s = ⟨f_{N}(x_{1}) … f_{N}(x_{a}), y_{1}^{∗} … y_{b}^{∗}⟩) ⇔ ∃x ∈ ω (Σ̂(f^{∗}(x)) = 0^{∗} & f^{∗}(x) = ⟨f_{N}(x_{1}) … f_{N}(x_{a}), y_{1}^{∗} … y_{b}^{∗}⟩) ⇔ ∃x (x ∈ f^{∗}^{−1}(Σ) & f^{∗}(x) = f^{∗}(x) = f^{∗}(h_{a,b}(⟨x_{1} … x_{a}, y_{1} … y_{b}⟩))) ⇔ ∃x, z (x ∈ f^{∗}^{−1}(Σ) & 4h(⟨x_{1} … x_{a}, y_{1}⟨y_{b}⟩) = z & ⟨x, z⟩ ∈ E^{∗}).

Therefore f_{N}^{−1}(Σ_{0}) ≤_{e} f^{∗}^{−1}(Σ_{0}) ⊕ E^{∗}, and since f^{∗}^{−1}(Σ_{0}) ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ …⊕f_{N}^{−1}(Σ_{k})⊕E^{∗}, we obtain that f_{n}^{−1}(Σ_{0}) ≤_{e} f_{N}^{−1}(Σ_{1})⊕…⊕f_{N}^{−1}(Σ_{k})⊕E^{∗}.

3) We have E^{∗} ≤_{e} E_{f}, from which follows that f_{N}^{−1}(Σ_{0}) ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ E_{f}. For the proof of that statement is necessary to know that ⟨x, y⟩ ∈ E^{∗} ⇔ f^{∗}(x) = f^{∗}(y) ⇔ x = y = 0 ∨ ∃z, t (x = 2z+1 & y = 2t+1 & f_{N}(z) = f_{N}(t)) ∨ ∃x_{1}, x_{2}, y_{1}, y_{2} such that (x_{1} < x & y_{1} < y & x_{2} < x & y_{2} < y) and (x = J(x_{1}, x_{2}) & y = J(y_{1}, y_{2}) & f^{∗}(x_{1}) = f^{∗}(y_{1}) & f^{∗}(x_{2}) = f^{∗}(y_{2})).

□

Definition 3.6 For an N-enumeration f_{N} : ω → N and a structure 𝔄(Σ_{1} … Σ_{k}), define:

f_{N}^{−1}(𝔄) := {⟨i, z⟩ | z ∈ f_{N}^{−1}(Σ_{i})} ∪ {⟨0, z⟩ | z ∈ E_{f}^{+}}.

Remark: f_{N}^{−1}(𝔄) ≡_{e} f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ E_{f} ⊕ \overline{E_{f}}.

Definition 3.7 1) N-string τ_{N} is a function τ_{N} : [0 … n−1] → N, with length lh(τ_{N}) = n.

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

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

Remark: The functions h_{0}, h_{1}, h_{2}, such that ∀s ∈ N^{∗}(h_{0}(s) ↓⇔ ∃τ_{N}(s = ⌜τ_{N}⌝)), h_{1}(⟨⌜τ_{N}⌝, ⌜σ_{N}⌝⟨) = 0^{∗} ⇔ τ_{N} ⊆ σ_{N}, h_{2}(⟨⌜τ_{N}⌝, x^{∗}, y⟩) = 0^{∗} ⇔ τ_{N}(x) = y)

are prime computable.

Definition 3.8 For a structure 𝔄 = 𝔄(Σ_{1} … Σ_{k}) with predicates Σ_{i} ⊆ N^{a_{i}} × ω^{b_{i}}, a Nstring τ_{N} and a formula F_{e}(z) with e, z ∈ ω, define τ_{n} ⊩_{𝔄} F_{e}(z) as follows:

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

and

τ_{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)).

Properties:

1) If τ_{n} ⊆ σ_{N} and τ_{N} ⊩_{𝔄} F_{e}(z), then σ_{N} ⊩_{𝔄} F_{e}(z).

2) The function h_{3}, such that h_{3}(⟨⌜τ_{N}⌝, e^{∗}, z^{∗}⟩) = 0∗ ⇔ τ_{N} ⊩_{𝔄} F_{e}(z) is SC(Σ̂_{1} … Σ̂_{k}, ˆ=_{N}, ˆ≠_{N}).

Definition 3.9 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}(𝔄)).

Proposition 3.10 f_{N} ⊧_{𝔄} F_{e}(z) iff ∃τ_{N} ⊆ f_{N}(τ_{N} ⊩_{𝔄} F_{e}(z)).

Definition 3.11 The predicate Σ ⊆ N^{a} × ω^{b} has normal form in the structure 𝔄 = 𝔄(Σ_{1} … Σ_{k}), when there exist e ∈ ω, an N-string δ_{N} and x_{1} … x_{a} ∉ Dom(δ_{N}), such that (∀s_{1} … s_{a} ∈ N, ∀y_{1} … y_{b} ∈ ω) ((s_{1} … s_{a}, y_{1} … y_{b}) ∈ Σ iff ∃τ_{N} ⊇ δ_{N} such that (τ_{N}(x_{1}) = s_{1} & … & τ_{N}(x_{a}) = s_{a} & τ_{N} ⊩_{𝔄} F_{e}(⟨x_{1} … x_{a}, y_{1} … y_{b}⟩))).

Theorem 3.12 (The Normal form theorem) Let 𝔄(Σ_{1} … Σ_{k}) be a structure, with predicates Σ_{i} ≤ N^{a_{i}} × ω^{b_{i}}. Then for every predicate Σ ⊆ N^{a} × ω^{b} the followings are equivalent:

1) Σ has in normal form in 𝔄.

2) Σ ≤_{SC} 𝔄.

3) f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄) where f_{N} is an arbitrary N-enumeration.

Proof:

1) (3) follows from (2).

Let Σ ≤_{SC} 𝔄, i.e. Σ ≤_{SC} (Σ_{1} … Σ_{k}, =_{N}, ≠_{N}). Therefore, using Corollary 7.6, for every N-enumeration f_{N}, we have that f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ …⊕f_{N}^{−1}(Σ_{k})⊕f_{N}^{−1}(=_{N})⊕f_{N}^{−1}( ˆ≠_{N})⊕E_{f}, but f_{N}^{−1}(=_{N}) = E_{f} and f_{N}^{−1}( ˆ≠_{N}) = \overline{E}_{f}, therefore f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ E_{f}^{+} ≡_{e} f_{N}^{−1}(𝔄).

2) (1) follows from(3).

Let for every total surjective function f_{N} : ω → N, f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄), i.e. there exists e, such that f_{N}^{−1}(Σ) = Ψ_{e}(f_{N}^{−1}(𝔄)). Assume that Σ has no normal form in 𝔄, i.e. for all e ∈ ω, for all N-string δ_{N} and x_{1} … x_{a} ∈ ω\Dom(δ_{N}), there exist s_{1} … s_{a} ∈ N and y_{1} … y_{b} ∈ ω, such that the following holds true:

(∗) (\overline{s}, \overline{y}) ∉ Σ iff ∃τ_{N} ⊇ δ_{N}(τ_{N}(x_{1}) = s_{1} & … & τ_{N}(x_{a}) = s_{a} & τ_{N} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩))

We can define an N-enumeration f_{N} : ω → N, such that f_{N}^{−1} ≰_{e} f_{N}^{−1}(𝔄), i.e. such that for every e, f_{N}^{−1}(Σ) ≠ Ψ_{e}(f_{N}^{−1}(𝔄)). First we define by induction N-strings σ_{N}^{q}, such that σ_{N}^{0} ⊆ … ⊆ σ_{N}^{q} ⊆ …, so that at stage 2e + 1 we insure f_{N} to be total and surjective,and at stage 2e + 2 we insure f_{N}^{−1}(Σ) ≠ Ψ_{e}(f_{N}^{−1}(𝔄)), for f_{n} := ⋃_{q} σ_{N}^{q}, as follows:

Stage 0 σ_{N}^{0} = ∅

Stage 2e+1

Suppose we have already defined σ_{N}^{q}, for q = 2e. Let x = lh(σ_{N}^{q}), for the least n ∉ N, such that n ∉ Range(σ_{N}^{q}).

Define σ_{N}^{q+1} ⊇ σ_{N}^{q}, lh(σ_{N}^{q+1}) = lh(σ_{N}^{q}) + 1 and σ_{N}^{q+1}(x) = n.

Stage 2e+2 Suppose we have already defined σ_{N}^{q}, where q = 2e + 1. Let x_{1} … x_{a} ∈ ω are such that x_{j} = lh(σ_{N}^{q}) + j − 1, 1 ≤ j ≤ a. Therefore

x_{1} … x_{a} ∉ dom(σ_{N}^{q}) are the first a elements, where σ_{N}^{q} is not defined.

Case 1. There exist s_{1} … s_{a} ∈ N and y_{1} … y_{b} ∈ ω, such that (*) holds true, i.e. (\overline{s}, \overline{y}) ∉ Σ iff ∃τ_{N} ⊇ σ_{N}^{q} (τ_{N}(x_{1}) = s_{1} & … & τ_{N}(x_{a}) = s_{a} & τ_{N} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩)), i.e. for δ_{N} ⊇ σ_{N}^{q}, such that δ_{N}(x_{1}) = s_{1} & … & δ_{N}(x_{a}) = s_{a} & lh(δ_{N}(x_{a}) = lh(σ_{N}^{q}) + a, the following holds: (\overline{s}, \overline{y}) ∉ Σ iff ∃τ_{N} ⊇ δ_{N} (τ_{N} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩)).

Subcase 1.1. ∃τ_{N} ⊇ δ_{N} (τ_{N} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩)). Define σ_{N}^{q+1} := τ_{N}.

Subcase 1.2. ∀τ_{N} ⊇ δ_{N} (τ_{N} ⊮_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩)). Define σ_{N}^{q+1} := δ_{N}.

Case 2. Otherwise, define σ_{N}^{q+1} := σ_{N}^{q}.

Define f := ⋃_{q} σ_{N}^{q}, which is total and surjective, i.e. an N-enumeration.

Using the assumption that Σ has no normal form in 𝔄 it follows that at stage 2e + 2 the Case 2 never happens, so we have the following two subcases only:

In Subcase 1.1, σ_{N}^{q+1} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩) and (\overline{s}, \overline{y}) ∉ Σ, and σ_{N}^{q+1}(x_{j}) = s_{j} for 1 ≤ j ≤ a (from the last one it follows that f_{N}(d_{j}) = s_{j}). From σ_{N}^{q+1} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩), using P roposition 3.10, we obtain that f_{N} ⊩_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩), i.e. ⟩\overline{x}, \overline{y}) ∈ Ψ_{e}(f_{N}^{−1}(𝔄))). But (f_{N}(x_{1}) … f_{N}(x_{a}), y_{1} … y_{b}) = (\overline{s}, \overline{y}) ∉ Σ, i.e. ⟨\overline{x}, \overline{y}⟩ ∉ f_{N}^{−1}(Σ) and therefore f_{N}^{−1}(Σ) ≠ Ψ_{e}(f_{N}^{−1}(𝔄)).

In Subcase 1.2, ∀τ_{N} ⊇ σ_{N}^{q+1} (τ_{N} ⊮_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩)), (\overline{s}, \overline{y}) ∈ Σ, and σ_{N}^{q+1}(d_{j}) = s_{j} for 1 ≤ j ≤ a (then we have f_{N}(x_{j}) = s_{j} and therefore ⟨\overline{x}, \overline{y}⟩ ∈ f_{N}^{−1}(Σ)). From ∀τ_{N} ⊇ σ_{N}^{q+1} (τ_{N} ⊮_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩)), using P roposition3.10, it follows that f_{N} ⊮_{𝔄} F_{e}(⟨\overline{x}, \overline{y}⟩), i.e. ⟨\overline{x}, \overline{y}⟩ ∉ Ψ_{e}(f_{N}^{−1}(𝔄)). Therefore f_{N}^{−1}(Σ) ≠ Ψ_{e}(f_{N}^{−1}(𝔄)).

We have proven that for all e, f_{N}^{−1}(Σ) ≠ Ψ_{e}(f_{N}^{−1}(𝔄)), i.e. f_{N}^{−1}(Σ) ≰_{e} f_{N}^{−1}(𝔄), which is a contradiction. Therefore our assumption is false, i.e. Σ has normal form in 𝔄.

2) (2) follows from(1).

Suppose Σ has normal form in 𝔄.

We can prove that Σ̂ ∈ SC(Σ̂_{1} … Σ̂_{k}, ˆ=_{N}, ˆ≠_{N}), which according to the definition means Σ ≤_{SC} (Σ_{1} … Σ_{k}, =_{N}, ≠_{N}), i.e. that Σ ≤_{SC} 𝔄. Since Σ has normal form in 𝔄, (∃e ∈ ω, ∃δ and N-string, ∃x_{1} … x_{a} ∉ Dom(δ_{N})) (∀s_{1} … s_{a} ∈ N, ∀y_{1} … y_{b} ∈ ω) ((\overline{s}, \overline{y}) ∈ Σ iff

∃τ_{N} ⊇ δ_{N} (τ_{N}(x_{1}) = s_{1} & … & τ_{N}(x_{a}) = s_{a} & τ_{N} ⊩_{𝔄} F_{e}(⟨\overline{x}\overline{y}⟩))),

therefore Σ̂(s) = 0^{∗} iff ∃s_{1} … s_{a} ∈ N ∃y_{1} … y_{b} ∈ ω (s = ⟨s_{1} … s_{a}, y_{1}^{∗} … y_{b}^{∗}⟩& (\overline{s}, \overline{y}) ∈ Σ) iff (s = ⟨\overline{s}, \overline{y}^{∗}⟩ & s_{j} ∈ N & y_{l}^{∗} ∈ ω^{∗} & ∃τ ⊇ δ (τ_{N}(x_{1}) = s_{1} &… & τ_{N}(x_{a}) = s_{a} & ∃v(⟨v, ⟨\overline{x}, \overline{y}⟩⟩ ∈ W_{e} & τ_{N} ⊩_{𝔄} D_{v}))).

Note that the functions χ_{ω^{∗}}, χ_{N}, I_{j}^{m}, (where I_{j}^{m}(r) = r_{j} ⇔ r = ⟨r_{1} … r_{m}⟩), h_{0}, (where h_{0}(s) = 0^{∗} ⇔ s = ⌜τ_{N}⌝), h_{1}, (where h_{1}(⟨⌜τ_{N}⌝, ⌜σ_{N}⌝⟩) = 0^{∗} ⇔ τ_{N} ⊆ σ_{N}, h_{2}, (where h_{2}(⟨⌜τ_{N}⌝, x^{∗}, s⟩) = 0^{∗} ⇔ τ_{N}(x) = s) are PC. The function φ (the semicharacteristic function of the set W_{e}), is partial recursive and therefore (see Proposition 1.4) the function φ^{∗} is PC, for the same reason the function ⟨·, ·⟩^{∗}, the coding of pair of natural numbers (where ⟨x^{∗}, y^{∗}⟩ = z^{∗} ⇔ ⟨x, y⟩ = z) is PC.

It is not difficult to check that the function g, such that g(⌜τ_{N}⌝, v^{∗}) = 0^{∗} ⇔ τ_{N} ⊩_{𝔄} D_{v} ⇔ ∀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} τ_{N}(y) ∨ u = ⟨0, 2⟨x, y⟩ + 1⟩ & x, y ∈ Dom(τ_{N}) & τ_{N}(x) ≠ τ_{N}(y)), is PC(Σ̂_{1} … Σ̂_{k}, ˆ=_{N}, ˆ≠).

Therefore Σ ≤_{SC} 𝔄.

□

4 Enumerations

Definition 4.1 An enumeration is a pair α = (f_{N}, R_{α}), where f_{N} : ω → N is a total surjective function and R_{α} ⊆ ω.

The structure of the enumeration α is the structure 𝔄_{α} = 𝔄(Gr(f_{N}), R_{α}), where Gr(f_{N}) = {(s, x) | f_{N}(x) = s} ⊆ N × ω.

Definition 4.2 For every enumeration α = (f_{N}, R_{α}) we define the following sets: 1. E_{α} := {⟨x, y⟩ | f_{N}(x) =_{N} f(y)} = E_{f} = f_{N}^{−1}(=_{N}) ⊆ ω.

2. D(α) = E_{α}^{+} ⊕ R_{α}.

Proposition 4.3 Let a structure 𝔄 = 𝔄(Σ_{1} … Σ_{k}) and an enumeration α = (f_{N}, R_{α}) and a predicate Σ ⊆ N^{a} × ω^{b} be given. Then Σ ≤_{SC} 𝔄 ⊕ 𝔄_{α} if and only if f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄) ⊕ R_{α}.

Proof: (⇒)Let Σ ≤_{SC} 𝔄⊕𝔄_{α}, where 𝔄⊕𝔄_{α} = (Σ_{1} … Σ_{k}, Gr(f_{N}), R_{α}). Then from The Normal Form Theorem(3.12) it follows that f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄 ⊕ 𝔄_{α}), i.e. f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ f_{N}^{−1}(Gr(f_{N})) ⊕ f_{N}^{−1}(R_{α}) ⊕ E_{f}^{+}, but f_{N}^{−1}(Gr(f_{N})) = {⟨x, y⟩ | (f_{N}(x), y) ∈ Gr(f_{N})} = {⟨x, y⟩ f_{N}(y) =_{N} f_{N}(x)} = f_{N}^{−1}(=_{N}) = E_{α}. Then f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(Σ_{1})⊕…⊕f_{N}^{−1}(Σ_{k})⊕f_{N}^{−1}(R_{α})⊕E_{α}^{+}, but f_{N}^{−1}(R_{α}) = R_{α} ⊆ ω, and therefore f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄) ⊕ R_{α}. (⇐) Let

(1) f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(𝔄) ⊕ R_{α}.

Consider an arbitrary N-enumeration g_{N} : ω → N, for which we can prove that g_{N}^{−1}(Σ) ≤_{e} g_{N}^{−1}(𝔄 ⊕ 𝔄_{α}), from which, using the Normal form theorem (3.12) follows that Σ ≤_{SC} 𝔄 ⊕ 𝔄_{α}.

We know that g_{N}^{−1}(Gr(f_{N})) = {⟨x, y⟩ | (g_{N}(x), y) ∈ Gr(f_{N})} = {⟨x, y⟩ | g_{N}(x) = f_{N}(y)} , and g_{N}^{−1}(R_{α}) = R_{α}.

(2) g_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(Σ) ⊕ g_{N}^{−1}(Gr(f_{N})), since ⟨\overline{x}, \overline{y}⟩ ∈ g_{N}^{−1}(Σ) ⇔ (g_{N}(x) … g_{N}(x_{a}), y_{1} … y_{b}) ∈ Σ ⇔ ∃ z_{1} … z_{a} (⟨x_{1}, z_{1}⟩ , …, ⟨_{a}, z_{a}⟩ ∈ g_{N}^{−1}(Gr(f_{N})) & (f_{N}(z_{1}), …, f_{N}(z_{a}), y_{1} … y_{b}) ∈ Σ) ⇔ ∃z_{1} … z_{a} (⟨x_{1}, z_{1}⟩ , …, ⟨x_{a}, z_{a}⟩ ∈ g_{N}^{−1}(Gr(f_{N})) & ⟨\overline{z}, \overline{y}⟩ ∈ f_{N}^{−1}(Σ)).

(3) f_{N}^{−1}(Σ_{i}) ≤_{e} g_{N}^{−1}(Σ_{i}) ⊕ Gr(f_{N}), for all 1 ≤ i ≤ k, since ⟨\overline{x}, \overline{y}⟩ ∈ f_{N}^{−1}(Σ_{i}) ⇔ (f_{N}(x_{1}) … f_{N}(x_{a_{i}}), y_{1} … y_{b_{i}}) ∈ Σ ⇔ ∃z_{1} … z_{a_{i}} (⟨z_{1}, x_{1}⟩ … ⟨z_{a_{i}}, x_{a_{i}}⟩ ∈ g_{N}^{−1}(Gr(f_{N})) & ⟨\overline{z}, \overline{y}⟩ ∈ g_{N}^{−1}(Σ_{i})).

Using the same reasoning as in (3), we obtain E_{α} = E_{f} = f_{N}^{−1}(=_{N}) ≤ g_{N}^{−1}(=_{N})⊕g_{N}^{−1}(Gr(f_{N})) = E_{g} ⊕g_{N}^{−1}(Gr(f_{N})) and \overline{E_{α}} ≤_{e} \overline{E_{g}} ⊕g_{N}^{−1}(Gr(f_{N})).

From (1), (2) and (3) it follows that g_{N}^{−1}(Σ) ≤_{e} g_{N}^{−1}(𝔄 ⊕ 𝔄_{α}).

□

Corollary 4.4 For any enumeration α = (f_{N}, R_{α}) and predicate Σ ⊆ N^{a}×ω^{b}, Σ ≤_{SC} 𝔄_{α} if and only if f_{N}^{−1}(Σ) ≤_{e} D(α).

Proof:

Let ∅ = (N, ω; =_{N}, ≠_{N}) be the empty structure. From Proposition 4.3 if follows that Σ ≤_{SC} ∅⊕𝔄_{α} ⇔ f_{N}^{−1}(Σ) ≤_{e} f_{N}^{−1}(∅)⊕R_{α}, but f_{N}^{−1}(∅) = E_{α}^{+}, i.e. Σ ≤_{SC} ∅ ⊕ 𝔄_{α} ⇔ f_{N}^{−1}(Σ) ≤_{e} D(α).

□

Corollary 4.5 For any structure 𝔄 = (Σ_{1} … Σ_{k}) and enumeration α = (f_{N}, R_{α}), 𝔄 ≤ 𝔄_{α} if and only if f_{N}^{−1}(𝔄) ≤_{e} D(α).

Proof:

Form Corollary 4.4 it follows that 𝔄 ≤_{SC} 𝔄_{α} ⇔ ∀i_{1≤i≤k} Σ_{i} ≤_{SC} 𝔄_{α} ⇔ ∀i_{1≤i≤k} f_{N}^{−1}(Σ_{i}) ≤_{e} D(α) ⇔ f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ≤_{e} f_{N}^{−1}(Σ_{1}) ⊕ … ⊕ f_{N}^{−1}(Σ_{k}) ⊕ E_{α}^{+} ≤_{e} D(α) ⇔ f_{N}^{−1}(𝔄) ≤_{e} D(α).

□

Definition 4.6 The pair f = (f_{N}, f_{ω}), where f_{N} : ω → N and f_{ω} : ω → ω are total functions, is called an N-ω-enumeration.

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

Remark: The N-ω-enumerations f = (f_{N}, f_{ω}) are enumerations α = (f_{N}, R_{α}) with R_{α} = Gr(f_{ω}), D(α) = D(f) = E_{f}^{+} ⊕ Gr(f_{ω}); 𝔄_{α} = 𝔄_{f} = 𝔄(Gr(f_{N}), Gr(f_{ω})); E_{α} = E_{f} = f_{N}^{−1}(=_{N}).