Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T18:09:37.266Z Has data issue: false hasContentIssue false

LEBESGUE DENSITY AND $\prod _1^0$ CLASSES

Published online by Cambridge University Press:  09 March 2016

MUSHFEQ KHAN*
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF HAWAII AT MANOA 2565 MCCARTHY MALL (KELLER HALL 401A) HONOLULU, HAWAII 96822, USAE-mail: khan@math.hawaii.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Analyzing the effective content of the Lebesgue density theorem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this inquiry: the positive density points with respect to effectively closed (or $\prod _1^0$) sets of reals, and a proper subclass, the density-one points. Bienvenu, Hölzl, Miller, and Nies have shown that the Martin-Löf random positive density points are exactly the ones that do not compute the halting problem. Treating this theorem as our starting point, we present several new results that shed light on how density, randomness, and computational strength interact.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2016