RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2010 Volume 46, Issue 4, Pages 83–90 (Mi ppi2027)

This article is cited in 2 papers

Large Systems

Complete and incomplete Boolean degrees

S. S. Marchenkov

M. V. Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Abstract: We study the partially ordered set of Boolean $P_2$-degrees. We introduce the notions of complete and incomplete Boolean degrees. We show that for each complete $P_2$-degree there exist both a countable decreasing chain of $P_2$-degrees and a countable antichain of $P_2$-degrees. We prove that above each incomplete $P_2$-degree there is a continuum of $P_2$-degrees. Thus, in total we show that in the partially ordered set of $P_2$-degrees there are no maximal elements.

UDC: 621.391.1+519.71

Received: 24.05.2010
Revised: 13.09.2010


 English version:
Problems of Information Transmission, 2010, 46:4, 346–352

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024