User zhang jing - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T08:13:17Z http://mathoverflow.net/feeds/user/23835 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130832/non-standard-model-of-the-domination-principle Non-standard model of the domination principle Zhang Jing 2013-05-16T13:34:14Z 2013-05-18T10:22:47Z <p>(Base theory $RCA_0$)The domination principle says there exists a function g such that g dominates any X-recursive function for any X in the model. i.e. For any $f\le_T X$, $\exists b\in M$ such that $g(a)>f(a) \forall a>b$. Here the second order structure (countable) is $\langle M,S_M,+_M,\cdot_M,0_M,1_M \rangle$.</p> <p>In the context of $\omega$ models, models satisfying such principle could be characterized by closure of high sets with respect to the existing sets in the model by Martin's characterization of high sets. I am curious about the non-$\omega$ models of the domination principle and I was trying to look up the some higher recursion theory texts but so far I could not find anything interesting. My guess is some bounding scheme is necessary. I am not very sure about this and is there more concrete characterization?</p> <p><strong>EDIT:</strong> (some update) I was trying to separate the domination principle from $B\Sigma_2^0$. Starting from a countable first order model of arithmetic $M$ such that $\neg B\Sigma_2^0 + I\Sigma_1^0$ holds, I was trying to add into the second order part the dominating functions. Dominating functions exist by $B\Sigma_1^0$. However, I need to prove that after augmenting the model with a dominating function $f$, $M[f]$ preserves $I\Sigma_1^0$. I found some similar forcing arguments on trees (Lemma IX.2.4) in Simpson's book and the augmented set is one generic set. However, I am not sure how to impose the special requirement (i.e. dominating property) on the choice of the generic set.</p> http://mathoverflow.net/questions/121103/cohesive-sets-with-degree-below-some-non-high-1-generic-degrees Cohesive sets with degree below some non-high 1-generic degrees? Zhang Jing 2013-02-07T18:18:51Z 2013-04-04T16:52:32Z <p>Terminology: Cohesive sets: $A\subset \omega$, for each recursively enumerable set $W_e$, either $A\cap W_e$ is finite or $A\cap \omega$\$W_e$ is finite. Non-high degrees: Degree $a$ such that $a'\not \geq 0''$. I'm wondering if it is possible to construct a cohesive set using some non-high 1-generic degree as an oracle? i.e. are there $A$ cohesive, and $B$ non-high 1-generic such that $A\leq_T B$? Thanks in advance!</p> http://mathoverflow.net/questions/124627/indices-of-r-e-sets Indices of r.e. sets Zhang Jing 2013-03-15T16:34:42Z 2013-03-17T12:14:42Z <p>The last part of the paper <em>Located Sets and Reverse Mathematics</em> [Journal of Symbolic Logic 65 (1999), 1451&ndash;1480] by Giusto and Simpson involves a proof as follows:</p> <p>Given $A$ an effectively immune set, i.e. there exists a recursive function $p$ such that $A$ is infinite and $W_e\subseteq A$ implies $|W_e|&lt; p(e)$, construct a r.e. set as follows:</p> <p>$$W_{g(e)}=\begin{cases}\text{the first } p(\varphi_e(e)) \text{ elements from A} &amp; \text{if }\varphi_e(e)\downarrow \\ \emptyset &amp;\text{otherwise} \end{cases}$$</p> <p>It was claimed that $g\leq_TA$, but an issue here is should the set be r.e relative to A, namely the set generated should be $W_{g(e)}^A$, which then should give a different index? The definition here seems to require unbounded amount of information about A to be known ahead of time so A should be deemed as an oracle, shouldn't it? Thanks! (BTW, the fact that the resulting set is r.e. not with respect to any nontrivial oracle is crucial in the proof that follows).</p> http://mathoverflow.net/questions/121965/sigma-10-coh $\Sigma_1^0-COH$? Zhang Jing 2013-02-16T05:06:47Z 2013-02-16T22:01:33Z <p>In reverse mathematics, $COH$ is a statement that there is a cohesive set for any uniform array of sets. Here uniform array of sets means that there exists a set $B$ such that $x\in B_e \leftrightarrow (e,x)\in B$, while a set $A$ is cohesive for $\lbrace B_e: e\in \omega\rbrace$ if and only if $A\subset^* B_e$ or $A\subset^*\bar B_e$ for any $e\in \omega$.</p> <p>I am thinking of a stronger version of $COH:$ replace the uniform family of sets by $\Sigma^0_1$ family, namely there exists a set $B$ such that $x\in B_e \leftrightarrow \exists z (e,x,z)\in B$ and a cohesive for $\lbrace B_e: e\in \omega\rbrace$ exists. I am searching for literatures that studied this principle previously but so far have not found anything interesting. Does anyone know what has been done regarding this principle?</p> http://mathoverflow.net/questions/100876/proof-of-the-existence-of-hyperimmune-free-degrees Proof of the existence of hyperimmune-free degrees Zhang Jing 2012-06-28T16:37:09Z 2013-01-12T09:12:22Z <p>In Classical Recursion Theory Vol.I by P.Odifreddi, section V.5 on the Tree Method, the proof for the existence of hyperimmune-frees involves the construction of a series of trees. Some definitions first:</p> <ul> <li>Tree: a function from initial segments to initial segments (binary) s.t. (1) $T(\sigma)\downarrow \wedge \tau \subseteq\sigma \rightarrow T(\tau)\downarrow \wedge T(\tau) \subseteq T(\sigma)$; (2) if one of $T(\sigma * 0), T(\sigma * 1)$ is defined, both are defined and incompatible.</li> <li>A is a branch of tree T if $T(\sigma) \subseteq A$ for infinitely many $\sigma$'s;</li> <li>Q is a subtree of T ($Q \subseteq T$) if for every $\sigma \in ran(Q), \sigma \in ran(T)$ </li> </ul> <p>My question is concerning the following technical lemma:</p> <p>$Lemma (Totality)$: Given $e$ and a recursive tree $T$, there is a recursive tree $Q \subseteq T$ s.t. one of the following holds:</p> <ul> <li>for every branch $A$ on $Q$, {$e$}$^A$ is not total;</li> <li>for every branch $A$ on $Q$, {$e$}$^A$ is total and $(\forall n)(\forall \sigma)(|\sigma|=n \rightarrow${$e$}$^{Q(\sigma)}(n)\downarrow)$</li> </ul> <p>Ideas in the proof: First step is to see whether the following condition is fulfilled, $(\exists \sigma \in T)(\exists x)(\forall \gamma \supseteq \sigma)(\gamma \in T \rightarrow${$e$}$^{\gamma}(x)\uparrow)$. If it exists, the first condition the fulfilled since we can take the full subtree above $\gamma$ on $T$. If not, $Q(\emptyset)= least$ $\gamma\in T$ s.t. {$e$}$^\gamma \downarrow$, inductively, for $Q(\sigma)$ there is an extension of it $T(\gamma)$ on $T$ s.t. {$e$}$^{T(\gamma)}(|\sigma|)\downarrow$, let $Q(\sigma *i) = T(\gamma * i)$, for $i=0,1$.</p> <p>But is the following assertion true? {$e$}$^A (n) \leq max_{|\sigma|=n}$ {$e$}$^{Q(\sigma)}(n)$, for any branch A on Q s.t. {$e$}$^A$ is total. The claim in the book is it is true since {$e$}$^A(n)$ is already defined on the $n^{th}$ level of the tree $Q$. However, is it reasonable to consider the possible e-splitting as well, namely, $\tau_1, \tau_2$ are two different strings s.t. {$e$}$^{\tau_1}\downarrow,$ {$e$}$^{\tau_2}\downarrow$ but they are not equal? The above construction only makes sure the existence of the value on the n$^{th}$ level, but will the value change later on?</p> http://mathoverflow.net/questions/106933/borel-sets-preserved-under-open-maps Borel sets preserved under open maps? Zhang Jing 2012-09-11T17:35:10Z 2012-09-11T21:58:09Z <p>Given open map f: $R^n$ to $R^n$ such that each open set $U\in R^n$, $f(U)$ is also open. Are Borel sets in $R^n$ preserved under f?</p> <p>Motivation: Pre-image of Borel sets under continuous map is a Borel set in $R^n$.</p> <p>The problem of the analogous statement above is when $U$ and $V$ are open, $f(U\cap V) \subset f(U)\cap f(V)$, but they may not be equal. Is it possible to construct a concrete counter-example to the statement?</p> http://mathoverflow.net/questions/101785/a-proof-of-zf-vdash-acl/101788#101788 Answer by Zhang Jing for A proof of $ZF \vdash AC^L$ Zhang Jing 2012-07-09T16:34:10Z 2012-07-09T16:34:10Z <p>The usual strategy is to define inductively a well-ordering on $L(\alpha)$ for each ordinal $\alpha$. Since under the assumption $V=L$, any set $x \in L (or$ $V), x\subseteq L(\beta)$ for some $\beta \in ORD$, thus $x$ is well-orderable. I guess your approach is correct. I suppose the canonical well-ordering you are talking about is as that in Kunen's book.</p> http://mathoverflow.net/questions/100742/history-of-provably-total-functions-of-a-theory/100743#100743 Answer by Zhang Jing for History of provably total functions of a theory Zhang Jing 2012-06-27T05:03:19Z 2012-06-27T05:03:19Z <p>One of the references I would recommend is P. Odifreddi's Classical Recursion Theory Volume II. On Page 324-326, it contains many references about the development of provably total functions (if you are seeking for the development within the Peano Arithmetic).</p> http://mathoverflow.net/questions/100460/absoluteness-of-countability Absoluteness of Countability Zhang Jing 2012-06-23T14:19:41Z 2012-06-23T16:23:11Z <p>Let M be a countable transitive model for ZFC, <strong>P</strong> is a partial order in M. Notions like "partial orders" and "dense" are absolute. Consider the following set $S$={$D\in M: D$ is dense in $P$} = {$D: D$ is dense in $P$}$^M$, the superscript notion denotes relativization. The remark is the set is usually not countable in $M$. (Note: since $M$ is countable, from $V$, the class of all sets, anything lies in $M$ should be countable with respect to $V$). I know from Skolem's Paradox, countability is not absolute. However, if considering the following function: f: $S$ $\rightarrow$ $\omega$ and f is in $V$ and f is injective. Since $f\in P(S\times \omega)$, and $S, \omega \in M$, therefore, by the fact that $M$ is a transitive model of ZFC $f \in M$. The only conclusion I can draw at this point is when relativized to $M, f$ is not one-to-one. However, I feel confused and could not see how this is the case. I am asking for somewhat better example illustrating the non-absoluteness of notion of countability. </p> <p>By the way, the question originates from Chapter VII Section 2 on Kunen's Set Theory (1980).</p> http://mathoverflow.net/questions/100033/interesting-mathematical-documentaries/100367#100367 Answer by Zhang Jing for Interesting mathematical documentaries Zhang Jing 2012-06-22T15:27:42Z 2012-06-22T15:27:42Z <p>Well, you may want to check out some short documentaries about beautiful minds. For example, my mathematical idol Kurt Gödel, here is the clip <a href="http://www.youtube.com/watch?v=i2KP1vWkQ6Y" rel="nofollow">http://www.youtube.com/watch?v=i2KP1vWkQ6Y</a> There can be many more examples, just to give the students a taste of what it is like to be a mathematician. </p> http://mathoverflow.net/questions/130832/non-standard-model-of-the-domination-principle/130983#130983 Comment by Zhang Jing Zhang Jing 2013-05-19T08:20:58Z 2013-05-19T08:20:58Z What is the forcing language here (sorry for getting into messy details)? For example, what is $(s,j)\Vdash \bar{n}\in X$? In the normal context of strings, $\sigma\Vdash \bar{n}\in X \leftrightarrow \sigma(n)=1$ (I got from Odifreddi's book). In addition, my intention was to preserve the first-order universe so that $B\Sigma_2^0$ is still false. But I am not sure whether the forcing mentioned here would alter the first order universe. Thanks! http://mathoverflow.net/questions/130832/non-standard-model-of-the-domination-principle/130983#130983 Comment by Zhang Jing Zhang Jing 2013-05-18T10:21:34Z 2013-05-18T10:21:34Z @Fran&#231;ois: Thanks! Can I just have it clarified what it means to say $g\geq f$ in the definition of poset? Since I am interested in the non-standard universe, do you think the same argument goes through (it occurs to me so). http://mathoverflow.net/questions/130832/non-standard-model-of-the-domination-principle Comment by Zhang Jing Zhang Jing 2013-05-17T01:47:51Z 2013-05-17T01:47:51Z Yeah the first property was what I was asking about. http://mathoverflow.net/questions/130832/non-standard-model-of-the-domination-principle Comment by Zhang Jing Zhang Jing 2013-05-16T17:36:02Z 2013-05-16T17:36:02Z Indeed. That was poorly phrased. I was thinking about the confinality in the ordinal (in order to define a dominating function if any). In this case, it is indeed bounding schemes that may be helpful. http://mathoverflow.net/questions/130832/non-standard-model-of-the-domination-principle Comment by Zhang Jing Zhang Jing 2013-05-16T17:12:18Z 2013-05-16T17:12:18Z @Jason: Sorry for its being poorly phrased. I am actually looking for some non-standard model in which RCA_0 and Domination principle hold. My guess of the universe being a regular cardinal is not a characterization for sure because one could easily produce a counter-example. To be exact, I would love some examples of non-standard models in which the principle holds. http://mathoverflow.net/questions/129520/powers-of-infinite-cardinals-in-the-generic-extension Comment by Zhang Jing Zhang Jing 2013-05-03T11:47:55Z 2013-05-03T11:47:55Z Sorry Please delete this. I meant to ask on stack exchange. http://mathoverflow.net/questions/124627/indices-of-r-e-sets Comment by Zhang Jing Zhang Jing 2013-03-17T16:41:37Z 2013-03-17T16:41:37Z Thanks! I think I should remove that! http://mathoverflow.net/questions/124627/indices-of-r-e-sets Comment by Zhang Jing Zhang Jing 2013-03-16T11:38:26Z 2013-03-16T11:38:26Z @Fran&#231;ois: Exactly. However, I was trying to adapt this to prove something else as explained in the EDIT. I think there is a hole in this argument though. http://mathoverflow.net/questions/124627/indices-of-r-e-sets Comment by Zhang Jing Zhang Jing 2013-03-15T17:36:24Z 2013-03-15T17:36:24Z @Joel: An algorithm I had in mind was: Suppose e is given, given input x, run $phi_e(e)$. If it converges, take the value $y$ and if x is among the first $p(y)$ elements from A, halt. We could code the description of the program to get a Goedel number which will have the desired property. But the problem is the potential use of A is infinite in the program, I am not sure whether it's okay to claim the program is recursive in A and further it has domain $W_{g(e)}$ instead of $W_{g(e)}^A$? http://mathoverflow.net/questions/124627/indices-of-r-e-sets Comment by Zhang Jing Zhang Jing 2013-03-15T17:29:23Z 2013-03-15T17:29:23Z @Fran&#231;ois: I agree on the possibility. But it is still not clear for me how to produce such index given the unknown status of $\phi_e(e)$. http://mathoverflow.net/questions/124627/indices-of-r-e-sets Comment by Zhang Jing Zhang Jing 2013-03-15T17:05:48Z 2013-03-15T17:05:48Z @Joel: Since A is effectively immune, A is not possible to be c.e, since if so, A is the subset of itself and the cardinality is not bounded. I mean the members of A in the natural number order. http://mathoverflow.net/questions/124627/indices-of-r-e-sets Comment by Zhang Jing Zhang Jing 2013-03-15T17:03:11Z 2013-03-15T17:03:11Z @Emil: Well, but the problem is whether the r.e. index could be found recursively in A. If yes, is it possible to exhibit such program? http://mathoverflow.net/questions/121965/sigma-10-coh/122023#122023 Comment by Zhang Jing Zhang Jing 2013-02-19T16:41:55Z 2013-02-19T16:41:55Z @Fran&#231;ois: Oh Thanks! I will check the references first! http://mathoverflow.net/questions/121965/sigma-10-coh/122023#122023 Comment by Zhang Jing Zhang Jing 2013-02-19T14:32:50Z 2013-02-19T14:32:50Z Then $\bar D$ would be a cohesive set for $&lt;R_k: k\in \omega&gt;$ since $\bar D \subset \bar R_k$ for all $k\in \omega$. But why $\bar D \subset ^* X$ or $\bar D\subset ^* \bar X$ holds? Making $D$ cofinite might help. Another thing I noticed was for the first bullet you phrased $X$ as $A-computable$, but $\Sigma_1^0$ actually states that for any collection of sets such that each set is r.e. in A, there exists a cohesive set for this collection. Thus I suppose there does exists a uniform listing but it is a listing of all r.e. sets in A. http://mathoverflow.net/questions/121965/sigma-10-coh/122023#122023 Comment by Zhang Jing Zhang Jing 2013-02-19T13:24:39Z 2013-02-19T13:24:39Z I guess I did not fully see the last two characterizations. What would the cohesive set be like? Thanks!