𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Almost everywhere domination and superhighness

✍ Scribed by Stephen G. Simpson

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
229 KB
Volume
53
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let ω be the set of natural numbers. For functions f, g: ω → ω, we say f is dominated by g if f (n) < g (n) for all but finitely many n ∈ ω. We consider the standard “fair coin” probability measure on the space 2__ω__ of in‐finite sequences of 0's and 1's. A Turing oracle B is said to be almost everywhere dominating if, for measure 1 many X ∈ 2^ω^ , each function which is Turing computable from X is dominated by some function which is Turing computable from B. Dobrinen and Simpson have shown that the almost everywhere domination property and some of its variant properties are closely related to the reverse mathematics of measure theory. In this paper we exposit some recent results of Kjos‐Hanssen, Kjos‐Hanssen/Miller/Solomon, and others concerning LR‐reducibility and almost everywhere domination. We also prove the following new result: If B is almost everywhere dominating, then B is superhigh, i. e., 0″ is truth‐table computable from B ′, the Turing jump of B. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 SIMILAR VOLUMES

Mass problems and almost everywhere domi
Mass problems and almost everywhere domination
✍ Stephen G. Simpson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

## Abstract We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the sets of reals which are almost everywhere dominating and Martin‐Löf random, respectively. Let __b__~1~, __b__~2~, and __b__~3~ be the degrees of unsolvability of the mass p