About Sigma_1 definability

Question

$L_{\omega_1}$ is the $\omega_1$-th constructible hierarchy. I define two binary relation on $P(\omega_1)$ as follows:

For $X,Y\in{P}(\omega_1)$,

$R_1(X,Y)$ means: there is $U\subset\omega_1\times\omega_1$ which is $\Sigma_1$ definable with parameters in $L_{\omega_1}$ such that $Y=\lbrace x\in\omega_1\mid\exists{t}\in{X}(t,x)\in{U}\rbrace$.

$R_2(X,Y)$ means: $Y$ is $\Sigma_1(X)$ in the model $(L_{\omega_1},\in)$, i.e. $Y$ is $\Sigma_1$-definable with $X$ as a unary predicate.

The question is:

1. $A$ is a subset of $\omega_1$, define $A'$ as follows: $A'$ is the set of all pairs $(a,b)$, $a,b\in\omega_1$, $K(a)\subset{A}$ and $K(b)\subset\omega_1\setminus{A}$.

   ($K:\omega_1\rightarrow{L_{\omega_1}}$ is the canonical emumeration of elements of $L_{\omega_1}$.)

   Then is $R_1(A,A')$ true?

2. Are $R_1$ and $R_2$ equivalent?

3. Is $R_1$ or $R_2$ transitive?

Answer 1

If I've followed your definitions, then the answer to question 1 is negative.

Specifically, if $A$ is $\Sigma_1$ but not $\Pi_1$, then $R_1(A,A')$ does not hold. The reason is that when $R_1(A,A')$ holds, we get $\Sigma_1$ information about the complement of $A$. To see what I mean, suppose $R_1(A,A')$ holds, via the $\Sigma_1$ definable set $U$. This means that $(a,b)\in A'$ if and only if $\exists t\in A\ (t,(a,b))\in U$. Furthermore, $\gamma\notin A$ if and only if $\exists (a,b)\in A'\ \gamma\in K(b)$, and this holds if and only if $\exists t\in A\ \exists (a,b)\ (t,(a,b))\in U$ and $\gamma\in K(b)$, which is a $\Sigma_1$ definition of the complement of $A$, contrary to the assumption that $A$ was not $\Pi_1$.

The same idea shows that $R_1$ and $R_2$ are not equivalent, since $R_2(A,A')$ does hold, as you can define $A'$ in a $\Sigma_1$ way using $A$ as an atomic predicate: $(a,b)\in A'$ if and only if every element of $K(a)$ is in $A$ and every element of $K(b)$ is not in $A$. This is $\Sigma_1(A)$, since we need one existential quantifier to get access to the values of $K(a)$ and $K(b)$, and then we can use bounded quantifiers to refer to the elements of these sets.

$R_2$ is not transitive, since by applying it several times allows us to successively take complements and projections, thereby allowing us to reach any $\Sigma_n$ definable set in $n$ steps, rather than merely the $\Sigma_1$ definable sets.