show/hide this revision's text 2 added 84 characters in body

Here are some examples from recursion theory which are boldface $\mathbf{\Pi^0_3}$ (the first is $\Pi^0_3(\emptyset')$ and the others are lightface $\Pi^0_3$ \Pi^0_3$) but not boldface $\mathbf{\Sigma^0_3}$:

The collection of weakly-2-random reals;

The collection of Schnorr random reals;

The collection of computably random reals.

References:

  1. The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. ACM Transactions on Computational Logic, 2007.

  2. Descriptive set theoretical complexity of randomness notions. Liang Yu. To appear.
show/hide this revision's text 1

Here are some examples from recursion theory which are lightface $\Pi^0_3$ but not boldface $\mathbf{\Sigma^0_3}$:

The collection of weakly-2-random reals;

The collection of Schnorr random reals;

The collection of computably random reals.

References:

  1. The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. ACM Transactions on Computational Logic, 2007.

  2. Descriptive set theoretical complexity of randomness notions. Liang Yu. To appear.