Luzin's (N) and randomness reflection

2020/06/13 by Pauly, Arno, Westrick, Linda, Yu, Liang
#03D32 #26A30 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2006.07517

Abstract

We show that a computable function f:\mathbb R→\mathbb R has Luzin's property (N) if and only if it reflects Π¹₁-randomnes, if and only if it reflects Δ¹₁(\mathcal O)-randomness, and if and only if it reflects \mathcal O-Kurtz randomness, but reflecting Martin-Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever f(x) is R-random, then x is R-random as well. If additionally f is known to have bounded variation, then we show f has Luzin's (N) if and only if it reflects weak-2-randomness, and if and only if it reflects ∅'-Kurtz randomness. This links classical real analysis with algorithmic randomness.

Related

• When does randomness come from randomness?
• Randomness notions and reverse mathematics
• Randomness and differentiability in higher dimensions
• Algorithmic randomness and the weak merging of computable probability measures
• Functions that preserve p-randomness