RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2020 Volume 59, Number 4, Pages 480–499 (Mi al2628)

This article is cited in 3 papers

Minimal predicates for $\Delta$-definability

A. S. Morozovab, D. A. Tussupovc

a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
c Eurasian National University named after L.N. Gumilyov, Nur-Sultan

Abstract: 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.

UDC: 512.5:510.6

Received: 04.12.2019
Revised: 24.11.2020

DOI: 10.33048/alglog.2020.59.405


 English version:
Algebra and Logic, 2020, 59:4, 328–340

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024