User liang yu - MathOverflow

Countable admissible ordinals

2012-04-05T02:58:26Z

Jensen claimed that for any finite increasing sequence countable admissible ordinals $\omega= \alpha_0<\alpha_1\cdots <\alpha_n$, there is a real $x$ so that, for each $m\leq n$, $\alpha_m$ is the $m+1$-th admissible ordinal relative to $x$.

Anybody knows the proof? Or where to find it?

Answer by Liang Yu for Definition of HYP in $L_{\omega_1^{CK}}[a]$?

2013-01-12T14:38:14Z

The following is not the answer of your question. But I think it is what you really want.

I guess you might be figuring out Leo's proof of McLaughlin's conjecture and his answer to Question 65 in Harvey's problem collection paper. The point is that by applying a nonstandard ordinal, Leo obtained a nonstandard $\Pi^0_1$-singleton so that it is not hyperarithmetic.

There are several ways to see above. One is by applying Barwise compactness. Another is to use Gandy's basis. By either way, you may obtain a nonstandard $\omega$-model $M$ of KP with $\omega_1^M=\omega_1^{CK}$ in which there is a nonhyperarithmetic (in the real sense) $\Pi^0_1$-singleton $x$ which has the property below.

To see it by Gandy's basis theorem. Just apply it to obtain an $\omega$-model $M\models KP$ in which $\omega_1^{CK}$ is nonstandard. In $M$, fix a nonstandard recursive ordinal $\alpha$, we can perform Leo's proof to produce a nonhyperarithmetic $\Pi^0_1$-singleton $x$so that for any $\beta<\alpha$, those reals computed by $x^{\beta}$ and $\emptyset^{\alpha}$ are precisely those computed by $\emptyset^{\beta}$.

Now take $N=L_{\omega_1^{CK}}[x]$. Since $x\leq_h M$, we have that $N\models KP$. It is not difficult to see that $N\models$ ''$x$ is a $\Pi^0_1$-singleton$"$.

The left is to show $N\models$`` $x$ is not hyperarithmetic".

$\bf{Proof}$: Otherwise, there must be some nonstandard ordinal $\gamma_0$ in $N$ so that $N\models \emptyset^{\gamma_0} $ exists. We may assume that $\gamma_0<\alpha$. Since $\omega_1^x=\omega_1^{CK}$, there must be some standard recursive ordinal $\gamma_1<\gamma_0$ so that $x^{\gamma_1}\geq_T \emptyset^{\gamma_0}$. Via some absoluteness (see below), it is not difficult to see $\emptyset^{\gamma_0}<_T \emptyset^{\alpha}$. Then by the property of $x$, $\emptyset^{\gamma_0}<\emptyset^{\gamma_1}$, a contradiction.[]

To see that $\emptyset^{\gamma_0}<_T \emptyset^{\alpha}$. There is recursive tree $T$ so that $N\models \emptyset^{\gamma_0} \mbox{ is the unique path in } T$. Note that there is also a real $z$, which is $\emptyset^{\gamma_0}$ in $M$, so that $M\models z \mbox{ is the unique path in } T$. If $\emptyset^{\gamma_0}=z$, then we have the conclusion. Otherwise, $\emptyset^{\gamma_0}$ does not belong to $M$. But $\emptyset^{\gamma_0}$ is hyperarithemtic in $x$ and so must belong to $M$, a contradiction.

In fact, by the proof above, every real which is hyperarithmetic in $N$ is actually hyperarithmetic.

$\Delta^1_2$-well ordering vs $\Delta^1_3$

2012-12-15T16:46:50Z

It is a classical result that if $0^{\sharp}$ exists, then there is a model of $ZFC$ in which there is a $\Delta^1_3$ well ordering of reals but no $\Delta^1_2$-well ordering.

My question is: Is $0^{\sharp}$ necessary to prove this? Or does the statement $\mathbf{CON}(ZFC+\mbox{there is a }\Delta^1_3\mbox{ well ordering of reals but no }\Delta^1_2 )$ implies the consistency of the existence of $0^{\sharp}$?

Decomposing $\mathbf{\Pi}^1_1$ sets into closed sets

2012-05-11T03:26:26Z

It is well known that every $\mathbf{\Pi}^1_1$-set is a union of $\aleph_1$-many Borel sets. I wonder whether it can be improved under certain reasonable set theory axioms assumption.

For example, assuming $ZFC+CH$, then it is trivially true that every set is a union of $\aleph_1$-many closed sets. But this seems heavily depends on $CH$ since if $ZFC+\neg CH+MA$, then there is a lightface $\Pi^0_2$-set which cannot be a union of $\aleph_1$-many closed sets.

So my question is: is it consistent with $ZFC+\neg CH$ that every $\mathbf{\Pi}^1_1$-set is a union of $\aleph_1$-many closed sets?

Answer by Liang Yu for To find an element of a $\Pi^1_1$ set

2012-07-22T01:59:41Z

The least such ordinal is the least ordinal which cannot be a $\Delta^1_2$-well-ordering over natural numbers.

Let $$\delta^1_2=\mbox{ supremum of the }\Delta^1_2 \mbox{ wellorderings of } \omega,$$ and $$\delta=\min\{\alpha\mid L\setminus L_{\alpha}\mbox{ contains no }\Pi^1_1 \mbox{ singleton}\}.$$

We claim that $\delta=\delta^1_2$.

$\mathbf{Proof}$: If $\alpha<\delta$, then there is a $\Pi^1_1$ singleton $x \in L_{\delta}\setminus L_{\alpha}$. Since $x\in L_{\omega_1^x}$ and $\omega_1^x$ is a $\Pi^1_1(x)$-wellordering, it must be that $\alpha<\omega_1^x<\delta^1_2$. So $\delta\leq \delta^1_2$.

If $\alpha<\delta^1_2$, there is a $\Delta^1_2$ wellordering relation $R\subseteq \omega\times \omega$ of order type $\alpha$. So there are two arithmetical relations $S, T\subseteq (\omega^{\omega})^2\times \omega^2$ so that $$R(n,m)\Leftrightarrow \exists f \forall g S(f,g,n,m), \mbox{ and}$$ $$\neg R(n,m)\Leftrightarrow \exists f \forall g T(f,g,n,m).$$ Define $\Pi^1_1$ sets $$R_0=\{(h,\langle n,m\rangle)\mid h(0)=0\wedge \exists f\forall g (S(f,g,n,m)\wedge \forall n(f(n)=h(n+1)))\}$$ and $$R_1=\{(h,\langle n,m\rangle)\mid h(0)=1\wedge \exists f\forall g (T(f,g,n,m)\wedge \forall n(f(n)=h(n+1)))\}.$$ By $\Pi^1_1$-uniformization Theorem, they both can be uniformized by $\Pi^1_1$ partial functions $p_{R_0}:\omega\to \omega^{\omega}$ and $p_{R_1}:\omega\to \omega^{\omega}$. Let $p=p_{R_0} \cup p_{R_1}$. Then $p$ is a $\Pi^1_1$ total function and can viewed as a $\Pi^1_1$-singleton. Then $R$ is recursive in $p$ and so $\alpha<\omega_1^p<\delta$.

Thus $\delta^1_2=\delta$.

Answer by Liang Yu for Vitali Sets vs Bernstein Sets...

2012-05-20T02:14:28Z

For your second definition of Vitali set, I have a weak partial answer. Namely the existence of a Bernstein set does not imply the existence of a $T$-Vitali set. The answer can be found in logic blog maintained by Andre Nies:
http://dl.dropbox.com/u/370127/Blog/Blog2012.pdf

Note that a Turing degree does not need to be an addition group.

I don't know whether the existence of a Vitali set implies the existence of a Bernstein set. But it is not difficult to see, under $ZF+DC$, that there is a Vitali set (if it exists) which contains a perfect subset.

For you first definition of Vitali set, I have no idea.

ZFC+``every analytical set is measurable"

2012-04-26T06:31:32Z

I know that "ZFC+the existence of an inaccessible cardinal" is equconsistent to
"ZFC + every $\mathbf{\Sigma}^1_3$ set is measurable".

Then how about the light face case?

Without large cardinal assumption, can we have a ZFC model in which every analytical set (or lightface $\Sigma^1_3$) is measurable?

Here a set is analytical if it is $\Sigma^1_n$ for some $n$.

Edited:

This was already answered by Shelah. ''It is known that there is a generic extension of $L$ not collapsing cardinals nor violating CH, in which every definable (with no parameter!) set of reals is measurable..." from the 3rd remark, page 18, Shelah's paper.

Answer by Liang Yu for Probability that a Turing machine will nontrivially reduce a real

2012-04-29T03:51:41Z

Not sure whether the following answers your question, but they might be helpful.

Fix any number $n\geq 2012$.

1 For any $e_0$ so that $\Phi_{e_0}^X=X_0$ where $X_0$ is the unique real so that $X=X_0\oplus X_1$. Then for such $e_0$, $m(N_{e_0})=1$.

2 For any $e_1$ so that $\Phi_{e_1}^X=0$ if $X(0)=0$ and $\Phi_{e_1}^X=X_0$ if $X(0)=1$. Then for such $e_1$, $m(N_{e_1})=\frac{1}{2}$.

3 $m(N_e)$ must be $\Delta^0_n$. Just note that $N_e$ is a $\Delta^0_{n-1}$ set.

4 $m(N_e)>0$ if and only if $N_e$ contains an $n$-random real.

\begin{proof}

If $m(N_e)>0$, then obviously $N_e$ contains an $n$-random real.

$N_e$ is a $\Delta^0_{n-1}$ set. So if it is null, then it does not contain any $n$-random real.

\end{proof}

5 $m(N_e)=1$ if and only if $N_e$ contains all $n$-random reals.

The proof is similar to 4.

The lower bound $2012$ can be certainly significantly smaller.

For randomness notions, you may refer Downey and Hirschfeldt (2010) or Nies (2009).

Answer by Liang Yu for Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets

2011-11-14T01:59:18Z

Here is another example from recursion theory:

Take a chain $\{x_{\alpha}\}_{\alpha<\omega_1}$ from Turing degrees.

For each $\alpha<\omega_1$, let $A_{\alpha}$ be the collection of the reals neither in $\bigcup_{\beta<\alpha}A_{\beta}$ nor Turing-computing $x_{\alpha}$.

Then $\{A_{\alpha}\}_{\alpha<\omega_1}$ is a Borel partition of $\mathbb{R}$.

Answer by Liang Yu for A G-delta-sigma that is not F-sigma?

2011-05-22T08:41:14Z

Here are some examples from recursion theory which are boldface $\mathbf{\Pi^0_3}$ (the first is $\Pi^0_3(\emptyset')$ and the others are lightface $\Pi^0_3$) but not boldface $\mathbf{\Sigma^0_3}$:

The collection of weakly-2-random reals;

The collection of Schnorr random reals;

The collection of computably random reals.

References:

The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. ACM Transactions on Computational Logic, 2007.
Descriptive set theoretical complexity of randomness notions. Liang Yu. To appear.

Answer by Liang Yu for A compactness property for Borel sets

2011-05-07T03:51:49Z

Here is a even simpler example.

Let $\{x_{\alpha} \}_{\alpha\in \omega_1}$ be an increasing chain in the Turing degrees. For every $\alpha$, let $B_{\alpha}=\{y\mid y\geq_T x_{\alpha}\}$. Each $B_{\alpha}$ is a boldface $\Sigma^0_3$ set.

Then for any countable ordinal $\beta$, $\bigcap_{\alpha<\beta}B_{\alpha}$ is not empty but $\bigcap_{\alpha<\omega_1}B_{\alpha}=\emptyset$.

Answer by Liang Yu for Martin's cone theorem and recursion theory

2011-04-13T09:07:43Z

I would like to add another example.

Given a sentence $\phi$ from partial order language, then for any Turing degree $x$, either $D(\leq x)\models \phi$ or $D(\leq x)\models \neg\phi$. By the BD, there is a Turing degree $x_{\phi}$ so that either for all $y\geq_T x_{\phi}$, $D(\leq y)\models \phi$ or for all $y\geq_T x$, $D(\leq y)\models \neg \phi$.

Let $z$ be a Turing degree above all the $x_{\phi}$'s, then for every $y\geq_T z$, $D(\leq y)$ is elementary equivalent to $D(\leq z)$.

I don't know a natural base for this.

Comment by Liang Yu

2013-04-11T12:30:47Z

ooops, you are right. I misread his question.

Comment by Liang Yu

2013-04-03T15:00:54Z

Joel, you are right. There should be +1 there.

Comment by Liang Yu

2013-02-12T05:36:28Z

The rough idea is if the open player has a winning strategy, then for any node $\sigma$ with an even length in the tree $T$, we may define a partial function $f(\sigma)=\inf_n\sup_m f(\sigma ^{\smallfrown} n ^{\smallfrown}m)$ and ensure $f(\emptyset)$ always exists.

Comment by Liang Yu

2013-02-12T05:23:08Z

This was proved by Andreas Blass in ``A. Blass, Complexity of winning strategies, Discrete Math. 3 (1972), 295–300. "

Comment by Liang Yu

2013-02-09T02:01:24Z

He does not. But he used this fact. See the first sentence in section 4 at page 397.

Comment by Liang Yu

2013-02-09T01:59:01Z

Actually the results are quite natural from recursion theory point view. Essentially the whole results were just telling some "lowness phenomenon". If we replace $ZF$ with $KP$, then all the results remain true and become totally recursion theoretic.

Comment by Liang Yu

2013-02-09T01:52:44Z

The existence of an inaccessible cardinal is used to guarantee that there is a countable ordinal $\alpha$ so that $L_{\alpha}\models ZF+V=L$. Based on this, Sacks can perform a ramified analysis for random forcing to prove the results.

Comment by Liang Yu

2013-02-05T04:59:10Z

Ted, you are right. But the proof heavily depends on Jensen's theorem. Actually in the proof of Lemma 4.3, they need Lemma 3.3 that is Jensen's result.

Comment by Liang Yu

2013-02-04T07:14:08Z

I asked Prof. Jensen, when he was in NUS, whether he has a model theoretical proof, or by applying Barwise compactness, of his result. He said no. So I guess Harrington's proof must be highly nontrivial.

Comment by Liang Yu

2013-02-04T04:14:37Z

Ted, thanks. In Simpon-Weitkamp's paper, it is claimed that Harrington has a model theoretical proof. But where to find it?

Comment by Liang Yu

2013-01-13T21:33:09Z

I fixed an error in the proof. To show that $x$ is not hyperarithemtic in $N$, we really need Leo's proof.

Comment by Liang Yu

2013-01-13T00:33:44Z

Having some recursion theory knowledge would also be very helpful to understand Solovay's construction.

Comment by Liang Yu

2013-01-12T23:54:33Z

$\Pi^0_1$-singletoness is not a absoluteness notion among the $\omega$-models. Also you have to apply Gandy's basis to get a model not the singleton. I added more details.

Comment by Liang Yu

2013-01-12T14:41:31Z

Check mathoverflow.net/questions/118706/… . It might be helpful for you.

Comment by Liang Yu

2012-12-15T17:18:57Z

Andres, thanks! I just got the paper. It seems that Leo also proved the lightface $\Delta^1_3$ one in the same paper.