At what level of the analytic hierarchy do Cohen reals lie?

Question

In his doctoral thesis titled "Three models of ordinal computability", Benjamin Seyfferth proved the following theorems:

i) A set $\mathtt A$ of reals is Ordinal Turing Machine-enumerable if and only if it is $\Sigma^{1}_2$

ii) A set $\mathtt A$ of reals is Ordinal Turing Machine-computable if and only if it is $\Delta^{1}_2$

In either case (by the fact that $\mathtt A$ should be able to be OTM-computable or enumerable without parameters or from a finite number of parameters), $\mathtt A$$\in$$\mathtt L$.

Now form the model $\mathtt L$[$\mathtt c$] where $\mathtt c$ is a Cohen real. By a theorem Prof. Hamkins proved in his answer to Mohammad Golshani's MathOverflow question "Reals added after Cohen forcing" (question 99013), $\mathtt L$[$\mathtt c$] has a perfect set $\mathtt P$ "all of whose finite subsets are mutually $\mathtt L$-generic Cohen reals".

I have several questions regarding $\mathtt P$.

i) Where does $\mathtt P$ lie in the (lightface) Analytic hierarchy.

ii) are all of the Cohen reals in $\mathtt P$ at the same level of the Analytic hierarchy and if so, what is that level?

iii) can $\mathtt P$ be defined in terms of OTM-computability or OTM-enumerability, even though $\mathtt P$ is neither OTM-computable nor OTM-enumerable?

Answer 1

You had asked about the perfect set $P$, but before treating that, let me first explain what is the complexity of the set of all $L$-generic Cohen reals:

Theorem. The set of reals that are $L$-generic for Cohen forcing is defined by a $\Pi^1_2$ definition. If non-empty, it is not defined by any $\Sigma^1_2$ definition. Hence in this case it is not $\Delta^1_2$.

Proof. Let $C$ be the set of $L$-generic Cohen reals. That is, $x\in C$ just in case $x\in 2^\omega$ and whenever $D\subset 2^{<\omega}$ is dense in this partial order and $D\in L$, then some initial segment of $x$ is in $D$. That is, $$x\in C\iff \forall D\left[(D\in L\text{ and }D\subset 2^{<\omega}\text{ is dense})\to\exists n\ (x\upharpoonright n)\in D\right].$$ This definition has complexity $\Pi^1_2$, because there is the universal quantifier $\forall D$ in front, which is quantifying over reals, and the statement $D\in L$ has complexity $\Sigma^1_2$, since $D\in L$ just in case there is a real coding a well-founded relation isomorphic to some $L_\alpha$ with $D\in L_\alpha$. The rest of the assertions inside the square braces are simple, and because $D\in L$ is on the hypothesis of the implication, it makes the whole implication inside the square braces have complexity $\Pi^1_2$, making the whole assertion $\Pi^1_2$.

Meanwhile, for the second claim, if $C$ is not empty, then the assertion $\exists x\ x\in C$ is true in $V$, but it cannot be true in $L$, since there are no $L$-generic Cohen reals in $L$, and so in this case $x\in C$ cannot be $\Sigma^1_2$ expressible, or it would be absolute to $L$ by Shoenfield absoluteness. QED

Now, about your questions concerning the perfect set $P$ from the other question. Since every branch through $P$ is an $L$-generic Cohen real, I claim that no such $P$ can be definable in $L[c]$ without parameters. The reason is that if $P$ were definable, then the left-most branch $d$ through $P$ would also be definable, and so in $L[c]$ we will have defined the $L$-generic Cohen real $d$ without parameters. But this is impossible, since on homogeneity grounds, every hereditarily definable set in $L[c]$ is contained in $L$. So $P$ does not occur at all in the lightface hierarchy, and also none of its members occur there.