A strong law of computationally weak subsets

Journal of Mathematical Logic 11 (1):1-10 (2011)
  Copy   BIBTEX

Abstract

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event [Formula: see text] such that if [Formula: see text] then X has an infinite subset Y such that no element of [Formula: see text] is Turing computable from Y.

Categories

Keywords

Reprint years

DOI

10.1142/s0219061311000980

Links

PhilArchive



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

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

Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Strengths and weaknesses of weak and strong supervenience.Mark Moyer - unknown
Problems of ontological complexity of law.Jerzy Wroblewski - 1986 - Theoria 1 (3):641-654.
Weak and global supervenience are strong.Mark Moyer - 2008 - Philosophical Studies 138 (1):125 - 150.
Various Concepts of “Supervenience” and Their Relations：A Comment on Kim’s Theory of Supervenience.Xiaoping Chen - 2011 - Frontiers of Philosophy in China 6 (2):316-333.
Strong versus weak quantum consequence operations.Jacek Malinowski - 1992 - Studia Logica 51 (1):113 - 123.
A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
A coup d'état in law's empire: Dworkin's Hercules meets Atlas. [REVIEW]R. P. Peerenboom - 1990 - Law and Philosophy 9 (1):95 - 113.
Weak and global supervenience: Functional bark and metaphysical bite?Mark Moyer - 2000
Perelman’s Interpretation of Reverse Probability Arguments as a Dialectical Mise en Abyme.Manfred Kraus - 2010 - Philosophy and Rhetoric 43 (4):362-382.
Did Searle attack strong strong AI or weak strong AI?Aaron Sloman - 1986 - In Artificial Intelligence and its Applications. Chichester.
Weak and strong judicial review.Walter Sinnott-Armstrong - 2003 - Law and Philosophy 22 (s 3-4):381-392.
Arrow's Theorem with a fixed feasible alternative.John A. Weymark, Aanund Hylland & Allan F. Gibbard - unknown
Deciding to Believe Again.Keith Frankish - 2007 - Mind 116 (463):523 - 547.

Analytics

Added to PP
2011-09-13

Downloads
44 (#336,932)

6 months
2 (#1,015,942)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Bjørn Kjos-Hanssen
University of Hawaii

Citations of this work

Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
Partition Genericity and Pigeonhole Basis Theorems.Benoit Monin & Ludovic Patey - forthcoming - Journal of Symbolic Logic:1-29.

Add more citations

References found in this work

Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.

Add more references