Minimal Predicates for Δ-Definability

A. S. Morozov, D. A. Tussupov

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)328-340
Number of pages13
JournalAlgebra and Logic
Volume59
Issue number4
DOIs
Publication statusPublished - Sep 2020

Keywords

  • existential formula
  • minimal degrees
  • ordered structure of degrees
  • Δ-definability
  • -definability
  • EXISTENTIAL INTERPRETABILITY
  • &#916

Fingerprint Dive into the research topics of 'Minimal Predicates for Δ-Definability'. Together they form a unique fingerprint.

Cite this