Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
type: Item
instance of: scholarly article
title: Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
zbMATH Open document ID: 1058.03041
author: Stephen Binns
author: Stephen G. Simpson
published in: Archive for Mathematical Logic
publication date: 2004-12-16T00:00:00Z
review text: This paper deals with Medvedev reducibility, as well as a weaker reducibility due to Muchnik. In both cases, if one restricts the reducibility to nonempty \(\Pi^0_1\) classes, the resulting degrees constitute a countable distributive lattice. The authors show that for the Muchnik version, the free countable Boolean algebra (and hence any countable distributive lattice) is embeddable into the lattice below any nonzero element. They conjecture that the same holds for the Medvedev version and prove that the free countable distributive lattice (and hence any finite distributive lattice) is so embeddable.
reviewed by: Leon Harkleroad
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 2123156
zbMATH Keywords: Medvedev reducibility
zbMATH Keywords: Muchnik reducibility
zbMATH Keywords: \(\Pi^0_1\) class
zbMATH Keywords: lattice embedding
MaRDI profile type: Publication
full work available at URL: s00153-003-0195-x
OpenAlex ID: W2010874076
DOI: 10.1007/S00153-003-0195-X
description: scientific article; zbMATH DE number 2123156