MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$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?

share|cite|improve this question
If you think about $L_\omega$ (or equivalently just $\omega$) instead of $L_{\omega_1}$, then this situation is familiar from recursion theory: $R_1(X,Y)$ then is a weak form of enumeration reducibility of $Y$ to $X$, while $R_2(X,Y)$ says that $Y$ is r.e. relative to $X$. These relations are distinct, and $R_2$ is not transitive --- because of complementation issues as in Joel's answer. – Andreas Blass Aug 19 '12 at 14:40
Thank you for your comment! – Song Li Aug 29 '12 at 4:54
up vote 3 down vote accepted

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.

share|cite|improve this answer
Thank you so much for your answer, it is very helpful for me. I have been on a travel without internet these days, so it is so late to reply your answer. – Song Li Aug 29 '12 at 4:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.