Embedding FD(ω) into {mathcal{P}_s} densely

Archive for Mathematical Logic 46 (7-8):649-664 (2008)
  Copy   BIBTEX

Abstract

Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any ${\mathcal{U} < _s \mathcal{V}}$ , we can lattice embed FD(ω) into ${\mathcal{P}_s}$ strictly between ${deg_s(\mathcal{U})}$ and ${deg_s({\mathcal V})}$ . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,343

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

Mass Problems and Intuitionism.Stephen G. Simpson - 2008 - Notre Dame Journal of Formal Logic 49 (2):127-136.
Covering properties of ideals.Marek Balcerzak, Barnabás Farkas & Szymon Gła̧b - 2013 - Archive for Mathematical Logic 52 (3-4):279-294.
Convergence of measures after adding a real.Damian Sobota & Lyubomyr Zdomskyy - 2023 - Archive for Mathematical Logic 63 (1):135-162.
Degrees of difficulty of generalized r.e. separating classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
Goodness in the enumeration and singleton degrees.Charles M. Harris - 2010 - Archive for Mathematical Logic 49 (6):673-691.
On the Existence of Strong Proof Complexity Generators.Jan Krajíček - 2024 - Bulletin of Symbolic Logic 30 (1):20-40.
Partitions of large Rado graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.

Analytics

Added to PP
2013-11-23

Downloads
65 (#338,733)

6 months
7 (#469,699)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.

Add more citations

References found in this work

Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
A splitting theorem for the Medvedev and Muchnik lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Mass problems and almost everywhere domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.

View all 6 references / Add more references