Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
The Journal of symbolic logic, 2020-03, Vol.85 (1), p.271-299
Ort / Verlag
Pasadena: Cambridge University Press
Erscheinungsjahr
2020
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
Abstract
We investigate the strength of a randomness notion
${\cal R}$
as a set-existence principle in second-order arithmetic: for each
Z
there is an
X
that is
${\cal R}$
-random relative to
Z
. We show that the equivalence between 2-randomness and being infinitely often
C
-incompressible is provable in
$RC{A_0}$
. We verify that
$RC{A_0}$
proves the basic implications among randomness notions: 2-random
$\Rightarrow$
weakly 2-random
$\Rightarrow$
Martin-Löf random
$\Rightarrow$
computably random
$\Rightarrow$
Schnorr random. Also, over
$RC{A_0}$
the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal.