Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Randomizing Reals and the First-Order Consequences of Randoms

Abstract

In this dissertation we investigate two questions in the subject of algorithmic randomness. The first question we address is "Given a real, is there a probability measure for which the real is not an atom, but relative to which the real is algorithmically random?" This question was originally studied by Reimann and Slaman with respect to Martin-Lof randomness, and this research continues their investigation by considering the question with respect to stronger notions of randomness and by providing metamathematical analysis of Reimann and Slaman's methods.

The second question we investigate is "What are the first-order consequences of the existence of 2-random reals?" Conidis and Slaman showed that the consequences lie somewhere between IΣ1 and BΣ2, but left open the question of further classification. We show that the existence of 2-random reals does not imply BΣ2, and thus the consequences lie strictly between IΣ1 and BΣ2. Furthermore, by utilizing the methods in this proof we are able to construct a κ-like model in which BΣ2 fails and thereby answer an open question posed by Kaye in 1995.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View