A measure-theoretic proof of Turing incomparability

Annals of Pure and Applied Logic 162 (1):83-88 (2010)
  Copy   BIBTEX

Abstract

We prove that if is an ω-model of weak weak König’s lemma and , is incomputable, then there exists , such that A and B are Turing incomparable. This extends a recent result of Kučera and Slaman who proved that if is a Scott set and , Aω, is incomputable, then there exists , Bω, such that A and B are Turing incomparable

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2010.07.004

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,337

External links

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

Through your library

My notes

Similar books and articles

Infima in the Recursively Enumerable Weak Truth Table Degrees.Rich Blaylock, Rod Downey & Steffen Lempp - 1997 - Notre Dame Journal of Formal Logic 38 (3):406-418.
Decomposition and infima in the computably enumerable degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
Computational randomness and lowness.Sebastiaan Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Π 1 0 classes, L R degrees and Turing degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
The ω-Turing degrees.Andrey C. Sariev & Hristo Ganchev - 2014 - Annals of Pure and Applied Logic 165 (9):1512-1532.
Variations on determinacy and ℵω1.Ramez L. Sami - 2022 - Journal of Symbolic Logic 87 (2):721-731.
Nonbounding and Slaman triples.Steven D. Leonhardi - 1996 - Annals of Pure and Applied Logic 79 (2):139-163.
Maximal Chains in the Turing Degrees.C. T. Chong & Liang Yu - 2007 - Journal of Symbolic Logic 72 (4):1219 - 1227.
The Bolzano–Weierstrass Theorem is the jump of Weak Kőnig’s Lemma.Vasco Brattka, Guido Gherardi & Alberto Marcone - 2012 - Annals of Pure and Applied Logic 163 (6):623-655.

Analytics

Added to PP
2013-12-18

Downloads
30 (#750,757)

6 months
11 (#345,260)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Weakly 2-randoms and 1-generics in Scott sets.Linda Brown Westrick - 2018 - Journal of Symbolic Logic 83 (1):392-394.

Add more citations

References found in this work

Measure theory and weak König's lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
On relative randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.

Add more references