Minimal Predicates for Δ-Definability

A. S. Morozov; D. A. Tussupov

doi:10.1007/s10469-020-09605-9

Minimal Predicates for Δ-Definability

A. S. Morozov, D. A. Tussupov

Кафедра дискретной математики и информатики ММФ и СУНЦ

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	328-340
Число страниц	13
Журнал	Algebra and Logic
Том	59
Номер выпуска	4
DOI	https://doi.org/10.1007/s10469-020-09605-9
Состояние	Опубликовано - сен 2020

Доступ к документу

10.1007/s10469-020-09605-9

Ссылка на публикацию в Scopus

Fingerprint Подробные сведения о темах исследования «Minimal Predicates for Δ-Definability». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{2661c36bd0e742b7a3abe82c542efd9d,

title = "Minimal Predicates for Δ-Definability",

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 = "existential formula, minimal degrees, ordered structure of degrees, Δ-definability, -definability, EXISTENTIAL INTERPRETABILITY, &#916",

author = "Morozov, {A. S.} and Tussupov, {D. A.}",

year = "2020",

month = sep,

doi = "10.1007/s10469-020-09605-9",

language = "English",

volume = "59",

pages = "328--340",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "4",

}

TY - JOUR

T1 - Minimal Predicates for Δ-Definability

AU - Morozov, A. S.

AU - Tussupov, D. A.

PY - 2020/9

Y1 - 2020/9

N2 - 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.

AB - 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.

KW - existential formula

KW - minimal degrees

KW - ordered structure of degrees

KW - Δ-definability

KW - -definability

KW - EXISTENTIAL INTERPRETABILITY

KW - &#916

UR - http://www.scopus.com/inward/record.url?scp=85096546882&partnerID=8YFLogxK

U2 - 10.1007/s10469-020-09605-9

DO - 10.1007/s10469-020-09605-9

M3 - Article

AN - SCOPUS:85096546882

VL - 59

SP - 328

EP - 340

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 4

ER -