5
$\begingroup$

This is a follow-up to my question on $\Delta^{1}_{2}$ and degrees of constructibility of real numbers that was answered by the user "William", see here: Can $\Delta^{1}_{2}$ separate degrees of constructibility?

Let us say that the real number $r$ encodes the heriditarily countable set $x$ if and only if there is a bijection $f:\omega\rightarrow\text{tc}(x)\cup\{x\}$ such that $f(0)=x$ and $r=\{p(i,j):f(i)\in f(j)\}$, where $p$ is Cantor's pairing function and $\text{tc}(x)$ denotes the transitive closure of $x$.

Let us say that a $\Delta^{1}_{2}$-formula $\phi$ is "coding invariant" if and only if, for any two codes of the same set $x$, $\phi$ either holds of both or of neither of them; thus, $\phi$ expresses a classification of the heriditarily countable sets. If $x$ is heriditarily countable, we will say that $\phi$ holds of $x$ and write $\phi(x)$ if and only if $\phi$ holds of every real code of $x$.

My question now is whether the following holds: When $\phi$ is a coding invariant $\Delta^{1}_{2}$-formula, $A$ is the set of heriditarily countable sets of which $\phi$ holds and $\bar{A}$ is the set of heriditarily countable sets of which $\phi$ does not hold, does one of $A$ and $\bar{A}$ contain elements of all degrees of constructibility of heriditarily countable sets?

In other words, can $\Delta^{1}_{2}$ separate degrees of constructibility "$\textbf{on the set level}$"?

Note that the answer to Can $\Delta^{1}_{2}$ separate degrees of constructibility? does not immediately yield an answer here, for at least two reasons: (1) not every real number codes a set and (2) codes for the same set can come from very different degrees of constructibility. (3) [added after Douglas Ulrich's comment to Liang Yu's answer]: Not every heriditarily countable set is $L$-equivalent to a real number.

[Here was a wrong example of a heriditarily countable set not $L$-equivalent to a real number, which I deleted after Liang Yu's comment below.]

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The degree of $\omega_1^L$ is $0$. $\endgroup$ Commented Nov 1, 2018 at 11:53
  • 1
    $\begingroup$ I think that there should be a negative solution to the question. But the proof is too lengthy to be presented here. $\endgroup$ Commented Nov 13, 2018 at 1:07
  • $\begingroup$ Can you give a sketch? $\endgroup$ Commented Nov 14, 2018 at 9:06

1 Answer 1

Reset to default
3
$\begingroup$

Here is a partial positive answer: i.e. either $A$ or $\bar{A}$ contain elements of all degrees of constructibility of reals.

Given an infinite set of numbers $x$, let $f:\omega\to \omega\cup \{x\} $ so that $f(n+1)=n$ and $f(0)=x$. Then the corresponded $r_x\equiv_T x$. Now if $A$ is a coding invariant $\Delta^1_2$-set, then either $A$ or the complement of $A$ contains a nonconstructible $r_x$. W.l.o.g, we assume that $A$ contains a nonconstructible $r_x$. Let $B=\{s\in A\mid s \mbox{ is a coding like }r_x\}=\{s \in A\mid \{p(i,j)\mid 1\leq i\leq j\}\subseteq s \subseteq \{p(i,j)\mid 1\leq i\leq j\}\cup\{p(i,0)\mid i\in \omega\}\}$

Then $B$ is a $\Delta^1_2$ set and $r_x\in B$. So $B$ has a perfect subset $T\in L$. But for each real $s\in [T]$, there is a real $y$ such that $s=r_y\equiv_T y$. So the coded heriditarily countable sets range over all the $L$-degrees.

The partial answer is not quite far away the full one. Since for any heriditarily countable set x, there are two sets of numbers $y$ and $z$ so that $L[z]\cap L[y]=L[\{x\}\cup \mathrm{tc}(x)]$.

Here is a partial negative answer to your question: I.e. there is a $\Pi^1_1$-formula as you required for which $A$ contain elements of all degrees of constructibility of reals but not all degrees of constructibility of heriditarily countable sets.

Given the function as above. Note that for any $x$ set of numbers and $s$ coding $x$, $r_x\leq_h s$. Now let $B=\{s\mid \exists r\leq_h s(r\cong s\wedge (r \mbox{ is }r_x \mbox{ for some }x))\}$ be a set defined by a $\Pi^1_1$-formual $\phi$. Then $\phi$ satisfies your requirements. Let $A$ be the corresponded collection of heriditarily countable sets of which $\phi$ holds. Then $A$ exactly contains all the constructible degrees of reals. If $\omega_1^L$ is countable, the set $\{(\alpha,g_{\alpha})\mid \alpha<\omega_1^L\}$, the sequence produced by a finite supported Cohen forcing of length $\omega_1^L$ over $L$, does not belong to $A$. Actually it has no a constructible degree of reals.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I believe you are misinterpreting the question. We are looking at the constructible degrees of the hereditarily countable sets; note for instance that not every hereditarily countable set need have the same degree as a real. $\endgroup$ Commented Oct 30, 2018 at 19:39
  • $\begingroup$ Ah, you are right. $\endgroup$ Commented Oct 31, 2018 at 5:19

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.