Algorithmic randomness, reverse mathematics, and the dominated convergence theorem.

*(English)*Zbl 1259.03021The authors use techniques of reverse mathematics to analyze the relative strength of several versions of the dominated convergence theorem for Lebesgue integration. Let DCT\(^\prime\) denote the assertion that, given \(f\), \(g\), and a sequence \(\langle f_n \rangle\) of elements of \(\mathcal L^1 (X)\), if \(\langle f_n \rangle\) is dominated by \(g\) and converges pointwise a.e. to \(f\), then \(\langle \int f_n \rangle\) converges to \(\int f\). Working in RCA\(_0\), the authors prove that DCT\(^\prime\) is equivalent to DCT\(^\ast\), which says that if \(\langle f_n (x) \rangle\) is Cauchy a.e. and dominated by \(g\), then \(\langle \int f_n \rangle\) is Cauchy also. Both of these versions of the dominated convergence theorem are shown to be equivalent to the principle 2-POS, which asserts that any \(G_\delta\) subset of Cantor space with positive measure is nonempty. The principle 2-POS is equivalent to B\(\Sigma^0_2\) plus 2-RAN, that is, to a pigeonhole principle plus a formalization of the existence of 2-random sets. All these principles are stronger than WWKL, incomparable to WKL, and strictly weaker than ACA, refuting a conjecture of Simpson related to the stronger form of DCT analyzed by X. Yu [Math. Log. Q. 40, No. 1, 1–13 (1994; Zbl 0804.03047)].

Reviewer: Jeffry L. Hirst (Boone)

##### MSC:

03B30 | Foundations of classical theories (including reverse mathematics) |

03F35 | Second- and higher-order arithmetic and fragments |

03D32 | Algorithmic randomness and dimension |

03F60 | Constructive and recursive analysis |

##### Keywords:

algorithmic randomness; reverse mathematics; dominated convergence; WWKL; WKL; 2-RAN; \(G\)-delta; measure; rainbow Ramsey; Lebesgue integration##### References:

[1] | Vasco Brattka, Joseph S. Miller, André Nies, Randomness and differentiability, preprint. · Zbl 1402.03062 |

[2] | Cholak, Peter; Greenberg, Noam; Miller, Joseph S., Uniform almost everywhere domination, J. symbolic logic, 71, 3, 1057-1072, (2006) · Zbl 1109.03034 |

[3] | Csima, Barbara F.; Mileti, Joseph R., The strength of the rainbow Ramsey theorem, J. symbolic logic, 74, 4, 1310-1324, (2009) · Zbl 1188.03044 |

[4] | Downey, Rodney G.; Hirschfeldt, Denis R., Algorithmic randomness and complexity, (2010), Springer New York · Zbl 1221.68005 |

[5] | Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal, Dynamical systems, simulation, abstract computation, Preprint · Zbl 1293.37001 |

[6] | Hájek, Petr; Pudlák, Pavel, Metamathematics of first-order arithmetic, (1993), Springer Berlin · Zbl 0781.03047 |

[7] | Hoyrup, Mathieu; Rojas, Cristóbal, Applications of martin-Löf randomness to effective probability theory, (), 260-269 · Zbl 1268.03055 |

[8] | Hoyrup, Mathieu; Rojas, Cristóbal, Computability of probability measures and martin-Löf randomness over metric spaces, Inform. and comput., 207, 7, 830-847, (2009) · Zbl 1167.68023 |

[9] | Bjørn Kjos-Hanssen, Joseph S. Miller, Reed Solomon, Lowness notions, measure, and domination, J. Lond. Math. Soc., in press. · Zbl 1262.03068 |

[10] | Kučera, Antonín, Measure, \(\Pi_1^0\)-classes and complete extensions of PA, () · Zbl 0622.03031 |

[11] | Nies, André, Computability and randomness, (2009), Oxford University Press Oxford · Zbl 1169.03034 |

[12] | Pathak, Noopur, A computational aspect of the Lebesgue differentiation theorem, J. log. anal., 1:9, 1-15, (2009) · Zbl 1285.03065 |

[13] | Jason Rute, Algorithmic randomness, martingales, and differentiability I, in preparation. · Zbl 1364.03064 |

[14] | Simpson, Stephen G., Subsystems of second-order arithmetic, (2009), Cambridge University Cambridge · Zbl 1181.03001 |

[15] | Simpson, Stephen G., Mass problems and measure-theoretic regularity, Bull. symbolic logic, 15, 4, 385-409, (2009) · Zbl 1191.03007 |

[16] | Simpson, Stephen G.; Smith, Rick, Factorization of polynomials and \(\Sigma_1^0\) induction, Ann. pure appl. logic, 31, 2-3, 289-306, (1986) · Zbl 0603.03019 |

[17] | Weihrauch, Klaus, Computability on the probability measures on the Borel sets of the unit interval, Theoret. comput. sci., 219, 1-2, 421-437, (1999) · Zbl 0916.68043 |

[18] | Yu, Xiaokang, Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Ann. pure appl. logic, 59, 1, 65-78, (1993) · Zbl 0770.03018 |

[19] | Yu, Xiaokang, Lebesgue convergence theorems and reverse mathematics, MLQ math. log. Q., 40, 1, 1-13, (1994) · Zbl 0804.03047 |

[20] | Yu, Xiaokang; Simpson, Stephen G., Measure theory and weak Königʼs lemma, Arch. math. logic, 30, 3, 171-180, (1990) · Zbl 0718.03043 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.