Relation Between T -Degrees and Σ-Degrees of a Model

Asylkhan Khisamiev

Consider those models that consist of a countable universe and a finite number of predicates and functions. Yu.L. Ershov has introduced in [1] the notion of Σ-definability of a model 𝔄 in the admissible set HF (𝔅) over a model 𝔅. We say that a model 𝔄 is Σ-reducible to a model 𝔅 and write 𝔄 ≤_{Σ} 𝔅 (or simply 𝔄 ≤ 𝔅), if a model 𝔄 is Σ-definable in HF (𝔅). From results of Ershov [2, p. 179] we obtain that the relation ≤ on the class K of all models is a preorder with the least elements. If we use ≤_{Σ} to generate a equivalence ≡_{Σ} on class K, where 𝔄 ≡ 𝔅 iff 𝔄 ≤ 𝔅 and 𝔅 ≤ 𝔄, then the model L_{Σ} =< K/_{≡}, ≤> is a partially ordered set. The class \overline{𝔄} ∈ L_{Σ} containing a model 𝔄 is called the Σ-degree of the model 𝔄. Let 𝔄 ⊕ 𝔅 be the disjoint union of models 𝔄 and 𝔅. Then the class \overline{𝔄 ⊕ 𝔅} is the least upper bound of classes \overline{𝔄} and \overline{𝔅}, i.e. we have the following

PROPOSITION 1. The model L_{Σ} is an upper semilattice with the least element.

Remark. From results of S.S. Goncharov [3] we obtain that a Σ-degree of \overline{𝔄 × 𝔅} is not always equal to \overline{𝔄 ⊕ 𝔅}.

From results of [4,6] we obtain

PROPOSITION 2. If models 𝔄 and 𝔅 has degrees a and b respectively and 𝔄 ≤_{Σ} 𝔅 then a ≤_{T} b. PROPOSITION 3. There are models 𝔄 and 𝔅 whose universe is the set of natural numbers and

degrees of their open diagrams are equal, but 𝔅 is not Σ-definable in HF (𝔄).

Assume that a map φ from a set of T -degrees to L_{Σ} is defined by φ(a) = \overline{𝔄}, where 𝔄 is a finitely generated model of degree a. Then we obtain

THEOREM. The map φ is an embedding of the upper semilattice of T -degrees into the upper semilattice of Σ-degrees.

References

1. Ershov Yu.L.(1985) Σ-Definability in admissible sets, Dokl. Akad. Nayk SSSR, v.285, no. 4, pp. 792–795.

2. Ershov Yu.L.(1996) Definability and computability, Plenum, New-York.

3. Goncharov S.S.(1979) Constructivization of Cartesian powers of models, 15-th All-Union algebraic conference, Krasnoyarsk.

4. Khisamiev A.N.(1998) On definability of a model in a hereditary finite admissible set, Generalized definability and computability, Vychislitel’nye sistemy, no. 161, pp. 15–20.

5. Khisamiev A.N.(1997) Numbering and definability in the hereditary finite superstructure of a model, Siberian Advances in Mathematics, v. 7, no. 3, pp. 63–74.

6. Khisamiev A.N.(1998) Strong Δ-definability of a model in an admisible set, Siberian Math. J., vol. 39, no. 1, 1998, pp. 168–176.

Address: Sobolev Institute of Mathematics of Siberian Branch of Russian Academy of Sciences, Apt. 154, Tereshkova street, 12, Novosibirsk, 630090, Russia

E-mail: hisamiev@math.nsc.ru