Algorithmic randomness, reverse mathematics, and the dominated convergence theorem

Annals of Pure and Applied Logic 163 (12):1854-1864 (2012)
  Copy   BIBTEX

Abstract

We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent to the conjunction of the statement asserting the existence of a 2-random relative to any given set and the principle of Σ2 collection

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

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

The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
Uniform distribution and algorithmic randomness.Jeremy Avigad - 2013 - Journal of Symbolic Logic 78 (1):334-344.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
Questioning Constructive Reverse Mathematics.I. Loeb - 2012 - Constructivist Foundations 7 (2):131-140.
Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Reverse mathematics and a Ramsey-type König's Lemma.Stephen Flood - 2012 - Journal of Symbolic Logic 77 (4):1272-1280.
Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
On the Indecomposability of $\omega^{n}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.

Analytics

Added to PP
2013-10-27

Downloads
21 (#627,796)

6 months
2 (#658,848)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Edward Dean
Carnegie Mellon University
Jeremy Avigad
Carnegie Mellon University

Citations of this work

Splittings and Disjunctions in Reverse Mathematics.Sam Sanders - 2020 - Notre Dame Journal of Formal Logic 61 (1):51-74.
Program extraction for 2-random reals.Alexander P. Kreuzer - 2013 - Archive for Mathematical Logic 52 (5-6):659-666.
Randomness notions and reverse mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.

Add more citations

References found in this work

Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Factorization of polynomials and °1 induction.S. G. Simpson - 1986 - Annals of Pure and Applied Logic 31:289.
Measure theory and weak König's lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.

View all 10 references / Add more references