Volume 20, No 2, 2013, P. 88-101

UDC 519.71
Marchenkov S. S.
On maximal and minimal elements in partially ordered sets of Boolean degrees

Abstract:
The weakest variant of algorithmic reducibility called Boolean reducibility is considered. For various closed classes $Q$, the partially ordered sets $\mathcal L_Q$ of Boolean degrees are analyzed. It is proved that for many closed classes $Q$ the corresponding sets $\mathcal L_Q$ have no maximal elements. Examples of sufficiently large classes $Q$ are given for which the sets $\mathcal L_Q$ contain uncountably many maximal elements. It is established that for closed classes $T_{01}$ and $S$M the corresponding sets of degrees have uncountably many minimal elements.
Bibliogr. 8.

Keywords: Boolean reducibility, closed classes of Boolean functions.

Marchenkov Sergey Serafimovich ¹
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
e-mail: ssmarchen@yandex.ru