User zhang jing - MathOverflow

Non-standard model of the domination principle

2013-05-16T13:34:14Z

(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$.

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?

EDIT: (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.

Cohesive sets with degree below some non-high 1-generic degrees?

2013-02-07T18:18:51Z

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!

Indices of r.e. sets

2013-03-15T16:34:42Z

The last part of the paper Located Sets and Reverse Mathematics [Journal of Symbolic Logic 65 (1999), 1451–1480] by Giusto and Simpson involves a proof as follows:

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|< p(e)$, construct a r.e. set as follows:

$$W_{g(e)}=\begin{cases}\text{the first } p(\varphi_e(e)) \text{ elements from A} & \text{if }\varphi_e(e)\downarrow \\ \emptyset &\text{otherwise} \end{cases}$$

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).

$\Sigma_1^0-COH$?

2013-02-16T05:06:47Z

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

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?

Proof of the existence of hyperimmune-free degrees

2012-06-28T16:37:09Z

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:

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.
A is a branch of tree T if $T(\sigma) \subseteq A$ for infinitely many $\sigma$'s;
Q is a subtree of T ($Q \subseteq T$) if for every $\sigma \in ran(Q), \sigma \in ran(T)$

My question is concerning the following technical lemma:

$Lemma (Totality)$: Given $e$ and a recursive tree $T$, there is a recursive tree $Q \subseteq T$ s.t. one of the following holds:

for every branch $A$ on $Q$, {$e$}$^A$ is not total;
for every branch $A$ on $Q$, {$e$}$^A$ is total and $(\forall n)(\forall \sigma)(|\sigma|=n \rightarrow ${$e$}$^{Q(\sigma)}(n)\downarrow)$

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

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?

Borel sets preserved under open maps?

2012-09-11T17:35:10Z

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?

Motivation: Pre-image of Borel sets under continuous map is a Borel set in $R^n$.

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?

Answer by Zhang Jing for A proof of $ZF \vdash AC^L$

2012-07-09T16:34:10Z

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.

Answer by Zhang Jing for History of provably total functions of a theory

2012-06-27T05:03:19Z

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).

Absoluteness of Countability

2012-06-23T14:19:41Z

Let M be a countable transitive model for ZFC, P 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.

By the way, the question originates from Chapter VII Section 2 on Kunen's Set Theory (1980).

Answer by Zhang Jing for Interesting mathematical documentaries

2012-06-22T15:27:42Z

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 http://www.youtube.com/watch?v=i2KP1vWkQ6Y There can be many more examples, just to give the students a taste of what it is like to be a mathematician.

Comment by Zhang Jing

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!

Comment by Zhang Jing

2013-05-18T10:21:34Z

@Franç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).

Comment by Zhang Jing

2013-05-17T01:47:51Z

Yeah the first property was what I was asking about.

Comment by Zhang Jing

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.

Comment by Zhang Jing

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.

Comment by Zhang Jing

2013-05-03T11:47:55Z

Sorry Please delete this. I meant to ask on stack exchange.

Comment by Zhang Jing

2013-03-17T16:41:37Z

Thanks! I think I should remove that!

Comment by Zhang Jing

2013-03-16T11:38:26Z

@Franç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.

Comment by Zhang Jing

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

Comment by Zhang Jing

2013-03-15T17:29:23Z

@Franç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)$.

Comment by Zhang Jing

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.

Comment by Zhang Jing

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?

Comment by Zhang Jing

2013-02-19T16:41:55Z

@François: Oh Thanks! I will check the references first!

Comment by Zhang Jing

2013-02-19T14:32:50Z

Then $\bar D$ would be a cohesive set for $<R_k: k\in \omega>$ 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.

Comment by Zhang Jing

2013-02-19T13:24:39Z

I guess I did not fully see the last two characterizations. What would the cohesive set be like? Thanks!