Density of the Medvedev lattice of \(\Pi^0_1\) classes
type: Item
instance of: scholarly article
title: Density of the Medvedev lattice of \(\Pi^0_1\) classes
zbMATH Open document ID: 1037.03040
author: Douglas Cenzer
author: Peter G. Hinman
published in: Archive for Mathematical Logic
publication date: 2003-09-16T00:00:00Z
review text: The Medvedev reducibility is a binary relation between sets of infinite binary sequences. One such subset \(P \subseteq \{0,1\}^\omega\) is reducible to another subset \(Q \subseteq \{0,1\}^\omega\) (notation \(P \leq_M Q\)) if there is a partial computable functional \(\Phi\) which maps \(P\) into \(Q\) (thus, given an element of \(Q\), one can find an element of \(P\)). A \(\Pi^0_1\) class \(P \subseteq \{0,1\}^\omega\) is a set that can be viewed as the set of infinite paths in a computable binary tree. This paper studies the lattice of degrees induced by the Medvedev reducibility on the \(\Pi^0_1\) classes of sets. The main result is that the partial ordering \(\leq_M\) is dense. For two disjoint computably enumerable sets, the class of separating sets form a \(\Pi^0_1\) class, called a ``c.e. separating class.'' It is shown that the above density result holds in the sublattice generated by c.e. separating classes.
reviewed by: Marius Zimand
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 1982534
zbMATH Keywords: degree of difficulty
zbMATH Keywords: Medvedev lattice
zbMATH Keywords: recursive functional
zbMATH Keywords: density
MaRDI profile type: Publication
full work available at URL: s00153-002-0166-7
OpenAlex ID: W1990923977
DOI: 10.1007/S00153-002-0166-7
description: scientific article; zbMATH DE number 1982534