Topological aspects of the Medvedev lattice

Archive for Mathematical Logic 50 (3-4):319-340 (2011)
  Copy   BIBTEX

Abstract

We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
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.
Coding true arithmetic in the Medvedev and Muchnik degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.

Analytics

Added to PP
2013-10-27

Downloads
44 (#343,283)

6 months
2 (#1,136,865)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Andrew Lewis
Graduate Theological Union

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Computability Theory.S. Barry Cooper - 2003 - Chapman & Hall.
Distributive Lattices.Raymond Balbes & Philip Dwinger - 1977 - Journal of Symbolic Logic 42 (4):587-588.
[Omnibus Review].M. Lerman - 1985 - Journal of Symbolic Logic 50 (2):550-552.

View all 16 references / Add more references