Random reals, the rainbow Ramsey theorem, and arithmetic conservation
Chris J. Conidis, Theodore A. Slaman · Journal of Symbolic Logic · 2013
Abstract We investigate the question “To what extent can random reals be used as a tool to establish number theoretic facts?” Let 2-RANbe the principle that for every realXthere is a realRwhich is 2-random relative toX. In Section 2, we observe that the arguments of Csima and Mileti [3] can be implemented in the base theoryRCA0and soRCA0+ 2-RANimplies the Rainbow Ramsey Theorem. In Section 3, we show that the Rainbow Ramsey Theorem is not conservative overRCA0for arithmetic sentences. Thus, from the Csima–Mileti fact that the existence of random reals has infinitary-combinatorial consequences we can conclude that 2-RANhas non-trivial arithmetic consequences. In Section 4, we show that 2-RANis conservative overRCA0+BΣ2for -sentences. Thus, the set of first-order consequences of 2-RANis strictly stronger thanP−+IΣ1and no stronger thanP−+BΣ2.