Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

14 November 2006, Intervals in the Medvedev lattice, Bas Terwijn

Speaker: Bas Terwijn (RUU and Technical University of Vienna)
Date: Tuesday 14 November 2006
Time: 16:00-17:00
Location: Room 3.27, Plantage Muidergracht 24, 1018 TV, Amsterdam

The Medvedev lattice is a structure from computability theory with ties to constructive logic. We will briefly describe this connection and the relation to structures such as the Turing degrees. We will then discuss structural properties of the Medvedev lattice, in particular, the size of its intervals. 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^\aleph_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. The talk was given previously in the Mathematical Logic Seminar but many people missed it.

For more information, please contact

Please note that this newsitem has been archived, and may contain outdated information or links.