On the Structure of the Medvedev Lattice

Journal of Symbolic Logic 73 (2):543 - 558 (2008)
Abstract
We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size $2^{2^{\aleph }0}$ , the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size $2^{2^{\aleph }0}$ , and in fact these big chains occur in every infinite interval. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1208359059
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,727
Through your library
References found in this work BETA
Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
On Suborderings of Degrees of Recursive Unsolvability.Gerald E. Sacks - 1961 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 7 (1-5):46-56.

Add more references

Citations of this work BETA
Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
Topological Aspects of the Medvedev Lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.

Add more citations

Similar books and articles
Some Remarks on the Algebraic Structure of the Medvedev Lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.
Embedding Brouwer Algebras in the Medvedev Lattice.Andrea Sorbi - 1991 - Notre Dame Journal of Formal Logic 32 (2):266-275.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.
Definable Structures in the Lattice of Recursively Enumerable Sets.E. Herrmann - 1984 - Journal of Symbolic Logic 49 (4):1190-1197.
Interpretations Into Monadic Algebras.Renato A. Lewin - 1987 - Studia Logica 46 (4):329 - 342.
Joins of Minimal Quasivarieties.M. E. Adams & W. Dziobiak - 1995 - Studia Logica 54 (3):371 - 389.
Added to PP index
2010-08-24

Total downloads
2 ( #797,630 of 2,197,330 )

Recent downloads (6 months)
1 ( #299,047 of 2,197,330 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature