2006/06/21 by Sebastiaan A. Terwijn, Terwijn, Sebastiaan A.
Computer Science · Mathematics · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #math.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0606529
arxiv created 2006/06/21 · arxiv updated 2009/12/01
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 22^ℵ0, the size of the lattice itself. We also prove that it is consistent that the lattice has chains of this size, and in fact that these big chains occur in every interval that has a big antichain. 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.