Constructing minimal pairs of degrees

TitleConstructing minimal pairs of degrees
Publication TypeJournal Article
Year of Publication1997
AuthorsSoskov I
JournalAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Volume89
IssueLivre 1 - Mathématiques et Mecanique
Pagination101-112
ISSN0205-0808
KeywordsDegrees, enumerations, forcing, minimal pairs, reducibilities
Abstract

We prove that there exist sets of natural numbers $A$ and $B$ such that $A$ and $B$ form a minimal pair with respect to Turing reducibility, enumeration reducibility, hyperarithmetical reducibility and hyperenumeration reducibility. Relativized versions of this result are presented as well.

1991/95 MSC

03D30

AttachmentSize
PDF icon 89-101-112.pdf1.12 MB