Journal of Mathematical Logic

We lift Jensen's coding method into the context of Woodin cardinals. By a theorem of Woodin, any real which preserves a "strong witness" to Woodinness is set-generic. We show however that there are class-generic reals which are not set-generic but preserve Woodinness, using "weak witnesses".

As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let be the halting probability of U^A; this gives a natural uniform way of producing an A-random real for every A ∈ 2^ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory and this Omega operator. But unlike the jump, which is invariant (up to computable permutation) under the choice of an effective enumeration of the partial computable functions, can be vastly different for different choices of U. Even for a fixed U, there are oracles A =* B such that and are 1-random relative to each other. We prove this and many other interesting properties of Omega operators. We investigate these operators from the perspective of analysis, computability theory, and of course, algorithmic randomness.

Our aim is to show that it is impossible to find a bound for the power of the first fixed point of the aleph function.

We give an algorithm for deciding whether an embedding of a finite partial order into the enumeration degrees of the -sets can always be extended to an embedding of a finite partial order .