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

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
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
e-mail: ssmarchen@yandex.ru

 © Sobolev Institute of Mathematics, 2015