User liang yu - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T21:39:53Z http://mathoverflow.net/feeds/user/14340 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93182/countable-admissible-ordinals Countable admissible ordinals Liang Yu 2012-04-05T02:58:26Z 2013-02-03T19:57:50Z <p>Jensen claimed that for any finite increasing sequence countable admissible ordinals $\omega= \alpha_0&lt;\alpha_1\cdots &lt;\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$.</p> <p>Anybody knows the proof? Or where to find it?</p> http://mathoverflow.net/questions/118706/definition-of-hyp-in-l-omega-1cka/118732#118732 Answer by Liang Yu for Definition of HYP in $L_{\omega_1^{CK}}[a]$? Liang Yu 2013-01-12T14:38:14Z 2013-01-14T02:27:19Z <p>The following is not the answer of your question. But I think it is what you really want.</p> <p>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. </p> <p>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.</p> <p>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&lt;\alpha$, those reals computed by $x^{\beta}$ and $\emptyset^{\alpha}$ are precisely those computed by $\emptyset^{\beta}$.</p> <p>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$"$. </p> <p>The left is to show $N\models$ $x$ is not hyperarithmetic".</p> <p>$\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&lt;\alpha$. Since $\omega_1^x=\omega_1^{CK}$, there must be some standard recursive ordinal $\gamma_1&lt;\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}&lt;_T \emptyset^{\alpha}$. Then by the property of $x$, $\emptyset^{\gamma_0}&lt;\emptyset^{\gamma_1}$, a contradiction.[]</p> <p>To see that $\emptyset^{\gamma_0}&lt;_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. </p> <p>In fact, by the proof above, every real which is hyperarithmetic in $N$ is actually hyperarithmetic.</p> http://mathoverflow.net/questions/116463/delta1-2-well-ordering-vs-delta1-3 $\Delta^1_2$-well ordering vs $\Delta^1_3$ Liang Yu 2012-12-15T16:46:50Z 2012-12-15T17:41:36Z <p>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.</p> <p>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}$?</p> http://mathoverflow.net/questions/96639/decomposing-mathbf-pi1-1-sets-into-closed-sets Decomposing $\mathbf{\Pi}^1_1$ sets into closed sets Liang Yu 2012-05-11T03:26:26Z 2012-09-01T21:22:01Z <p>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.</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/102810/to-find-an-element-of-a-pi1-1-set/102850#102850 Answer by Liang Yu for To find an element of a $\Pi^1_1$ set Liang Yu 2012-07-22T01:59:41Z 2012-07-22T03:14:05Z <p>The least such ordinal is the least ordinal which cannot be a $\Delta^1_2$-well-ordering over natural numbers. </p> <p>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}\}.$$</p> <p>We claim that $\delta=\delta^1_2$.</p> <p>$\mathbf{Proof}$: If $\alpha&lt;\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&lt;\omega_1^x&lt;\delta^1_2$. So $\delta\leq \delta^1_2$.</p> <p>If $\alpha&lt;\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&lt;\omega_1^p&lt;\delta$. </p> <p>Thus $\delta^1_2=\delta$.</p> http://mathoverflow.net/questions/71575/vitali-sets-vs-bernstein-sets/97453#97453 Answer by Liang Yu for Vitali Sets vs Bernstein Sets... Liang Yu 2012-05-20T02:14:28Z 2012-05-21T00:41:47Z <p>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:<br> <a href="http://dl.dropbox.com/u/370127/Blog/Blog2012.pdf" rel="nofollow">http://dl.dropbox.com/u/370127/Blog/Blog2012.pdf</a></p> <p>Note that a Turing degree does not need to be an addition group.</p> <p>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.</p> <p>For you first definition of Vitali set, I have no idea.</p> http://mathoverflow.net/questions/95231/zfcevery-analytical-set-is-measurable ZFC+every analytical set is measurable" Liang Yu 2012-04-26T06:31:32Z 2012-04-29T07:24:11Z <p>I know that "ZFC+the existence of an inaccessible cardinal" is equconsistent to<br> "ZFC + every $\mathbf{\Sigma}^1_3$ set is measurable". </p> <p>Then how about the light face case?</p> <p>Without large cardinal assumption, can we have a ZFC model in which every analytical set (or lightface $\Sigma^1_3$) is measurable? </p> <p>Here a set is analytical if it is $\Sigma^1_n$ for some $n$.</p> <p>Edited:</p> <p>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.</p> http://mathoverflow.net/questions/95479/probability-that-a-turing-machine-will-nontrivially-reduce-a-real/95485#95485 Answer by Liang Yu for Probability that a Turing machine will nontrivially reduce a real Liang Yu 2012-04-29T03:51:41Z 2012-04-29T04:02:55Z <p>Not sure whether the following answers your question, but they might be helpful.</p> <p>Fix any number $n\geq 2012$.</p> <p>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$. </p> <p>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}$.</p> <p>3 $m(N_e)$ must be $\Delta^0_n$. Just note that $N_e$ is a $\Delta^0_{n-1}$ set.</p> <p>4 $m(N_e)>0$ if and only if $N_e$ contains an $n$-random real.</p> <p>\begin{proof}</p> <p>If $m(N_e)>0$, then obviously $N_e$ contains an $n$-random real.</p> <p>$N_e$ is a $\Delta^0_{n-1}$ set. So if it is null, then it does not contain any $n$-random real.</p> <p>\end{proof}</p> <p>5 $m(N_e)=1$ if and only if $N_e$ contains all $n$-random reals. </p> <p>The proof is similar to 4.</p> <p>The lower bound $2012$ can be certainly significantly smaller. </p> <p>For randomness notions, you may refer Downey and Hirschfeldt (2010) or Nies (2009).</p> http://mathoverflow.net/questions/72259/partitioning-mathbbr-into-aleph-1-borel-sets/80858#80858 Answer by Liang Yu for Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets Liang Yu 2011-11-14T01:59:18Z 2011-11-14T01:59:18Z <p>Here is another example from recursion theory:</p> <p>Take a chain $\{x_{\alpha}\}_{\alpha&lt;\omega_1}$ from Turing degrees.</p> <p>For each $\alpha&lt;\omega_1$, let $A_{\alpha}$ be the collection of the reals neither in $\bigcup_{\beta&lt;\alpha}A_{\beta}$ nor Turing-computing $x_{\alpha}$.</p> <p>Then $\{A_{\alpha}\}_{\alpha&lt;\omega_1}$ is a Borel partition of $\mathbb{R}$.</p> http://mathoverflow.net/questions/56632/a-g-delta-sigma-that-is-not-f-sigma/65697#65697 Answer by Liang Yu for A G-delta-sigma that is not F-sigma? Liang Yu 2011-05-22T08:41:14Z 2011-05-22T15:16:34Z <p>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}$:</p> <p>The collection of weakly-2-random reals;</p> <p>The collection of Schnorr random reals;</p> <p>The collection of computably random reals.</p> <p>References:</p> <ol> <li><p>The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. ACM Transactions on Computational Logic, 2007.</p></li> <li><p>Descriptive set theoretical complexity of randomness notions. Liang Yu. To appear.</p></li> </ol> http://mathoverflow.net/questions/64095/a-compactness-property-for-borel-sets/64170#64170 Answer by Liang Yu for A compactness property for Borel sets Liang Yu 2011-05-07T03:51:49Z 2011-05-07T04:26:55Z <p>Here is a even simpler example.</p> <p>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.</p> <p>Then for any countable ordinal $\beta$, $\bigcap_{\alpha&lt;\beta}B_{\alpha}$ is not empty but $\bigcap_{\alpha&lt;\omega_1}B_{\alpha}=\emptyset$.</p> http://mathoverflow.net/questions/45574/martins-cone-theorem-and-recursion-theory/61523#61523 Answer by Liang Yu for Martin's cone theorem and recursion theory Liang Yu 2011-04-13T09:07:43Z 2011-04-13T09:07:43Z <p>I would like to add another example.</p> <p>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$.</p> <p>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)$. </p> <p>I don't know a natural base for this.</p> http://mathoverflow.net/questions/126865/definability-in-a-language-with-a-single-binary-predicate/127216#127216 Comment by Liang Yu Liang Yu 2013-04-11T12:30:47Z 2013-04-11T12:30:47Z ooops, you are right. I misread his question. http://mathoverflow.net/questions/121549/complexity-of-winning-strategies-for-open-games-for-open-player Comment by Liang Yu Liang Yu 2013-04-03T15:00:54Z 2013-04-03T15:00:54Z Joel, you are right. There should be +1 there. http://mathoverflow.net/questions/121549/complexity-of-winning-strategies-for-open-games-for-open-player Comment by Liang Yu Liang Yu 2013-02-12T05:36:28Z 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. http://mathoverflow.net/questions/121549/complexity-of-winning-strategies-for-open-games-for-open-player Comment by Liang Yu Liang Yu 2013-02-12T05:23:08Z 2013-02-12T05:23:08Z This was proved by Andreas Blass in A. Blass, Complexity of winning strategies, Discrete Math. 3 (1972), 295–300. &quot; http://mathoverflow.net/questions/121251/why-has-sacks-measure-theoretic-uniformity-not-been-more-influential Comment by Liang Yu Liang Yu 2013-02-09T02:01:24Z 2013-02-09T02:01:24Z He does not. But he used this fact. See the first sentence in section 4 at page 397. http://mathoverflow.net/questions/121251/why-has-sacks-measure-theoretic-uniformity-not-been-more-influential Comment by Liang Yu Liang Yu 2013-02-09T01:59:01Z 2013-02-09T01:59:01Z Actually the results are quite natural from recursion theory point view. Essentially the whole results were just telling some &quot;lowness phenomenon&quot;. If we replace $ZF$ with $KP$, then all the results remain true and become totally recursion theoretic. http://mathoverflow.net/questions/121251/why-has-sacks-measure-theoretic-uniformity-not-been-more-influential Comment by Liang Yu Liang Yu 2013-02-09T01:52:44Z 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. http://mathoverflow.net/questions/93182/countable-admissible-ordinals/120698#120698 Comment by Liang Yu Liang Yu 2013-02-05T04:59:10Z 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. http://mathoverflow.net/questions/93182/countable-admissible-ordinals/120698#120698 Comment by Liang Yu Liang Yu 2013-02-04T07:14:08Z 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. http://mathoverflow.net/questions/93182/countable-admissible-ordinals/120698#120698 Comment by Liang Yu Liang Yu 2013-02-04T04:14:37Z 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? http://mathoverflow.net/questions/118706/definition-of-hyp-in-l-omega-1cka/118732#118732 Comment by Liang Yu Liang Yu 2013-01-13T21:33:09Z 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. http://mathoverflow.net/questions/104450/road-to-solovays-land/104456#104456 Comment by Liang Yu Liang Yu 2013-01-13T00:33:44Z 2013-01-13T00:33:44Z Having some recursion theory knowledge would also be very helpful to understand Solovay's construction. http://mathoverflow.net/questions/118706/definition-of-hyp-in-l-omega-1cka/118732#118732 Comment by Liang Yu Liang Yu 2013-01-12T23:54:33Z 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. http://mathoverflow.net/questions/118705/omega-models-of-mathbf-sigma1-1-dc-and-mathbf-delta1-1-ca Comment by Liang Yu Liang Yu 2013-01-12T14:41:31Z 2013-01-12T14:41:31Z Check <a href="http://mathoverflow.net/questions/118706/definition-of-hyp-in-l-omega1-cka" rel="nofollow" title="definition of hyp in l omega1 cka">mathoverflow.net/questions/118706/&hellip;</a> . It might be helpful for you. http://mathoverflow.net/questions/116463/delta1-2-well-ordering-vs-delta1-3/116465#116465 Comment by Liang Yu Liang Yu 2012-12-15T17:18:57Z 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.