Geodesic
Minimal predicates for $\Delta$-definability
Algebra i logika, Tome 59 (2020) no. 4, pp. 480-499.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider two kinds of reducibilities on finite families of predicates on a countable set: the definability of predicates and their complements of one family via another by means of existential formulas with parameters and the same definability on isomorphism types of families. Ordered structures of degrees generated by families of unary predicates are described. It is proved that for both reducibilities, there exist continuum many minimal nonzero degrees.
Keywords: $\Delta$-definability, existential formula, ordered structure of degrees, minimal degrees. 
@article{AL_2020_59_4_a4,
     author = {A. S. Morozov and D. A. Tussupov},
     title = {Minimal predicates for $\Delta$-definability},
     journal = {Algebra i logika},
     pages = {480--499},
     publisher = {mathdoc},
     volume = {59},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2020_59_4_a4/}
}
TY  - JOUR
AU  - A. S. Morozov
AU  - D. A. Tussupov
TI  - Minimal predicates for $\Delta$-definability
JO  - Algebra i logika
PY  - 2020
SP  - 480
EP  - 499
VL  - 59
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2020_59_4_a4/
LA  - ru
ID  - AL_2020_59_4_a4
ER  - 
%0 Journal Article
%A A. S. Morozov
%A D. A. Tussupov
%T Minimal predicates for $\Delta$-definability
%J Algebra i logika
%D 2020
%P 480-499
%V 59
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2020_59_4_a4/
%G ru
%F AL_2020_59_4_a4
A. S. Morozov; D. A. Tussupov. Minimal predicates for $\Delta$-definability. Algebra i logika, Tome 59 (2020) no. 4, pp. 480-499. http://geodesic.mathdoc.fr/item/AL_2020_59_4_a4/

[1] C. Spector, “On degrees of recursive unsolvability”, Ann. Math. (2), 64:3 (1956), 581–592 | DOI | MR | Zbl

[2] G. E. Sacks, “A minimal degree less than $0'$”, Bull. Am. Math. Soc., 67 (1961), 416–419 | DOI | MR | Zbl

[3] A. S. Morozov, “Ob odnoi svodimosti i ekzistentsialnoi interpretiruemosti struktur”, Sib. matem. zh., 58:2 (2017), 365–374 | MR | Zbl

[4] A. S. Morozov, A. Zh. Satekbaeva, J. A. Tussupov, “On the existential interpretability of structures”, Sib. elektron. matem. izv., 11 (2014), 557–566 http://semr.math.nsc.ru/v11/p557-566.pdf | MR | Zbl

[5] Yu. L. Ershov, Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980