User william - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T01:00:59Z http://mathoverflow.net/feeds/user/16761 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101708/wadge-determinacy-of-some-related-classes Wadge Determinacy of some related classes. William 2012-07-08T21:53:00Z 2012-08-20T03:22:01Z <p>Let $A, B \subset \omega^\omega$. The Wadge Game $(A, B)$ is played as followed: Player I plays $a_0 \in \omega$. Then Player II plays $b_0 \in \omega$. Then Player I choose $a_1 \in \omega$; afterward player II plays $b_1 \in \omega$. And so on. In the end player I produces a sequence $f = (a_0, a_1, a_2, ...)$ and player II produces a sequence $g = (b_0, b_1, b_2, ...)$. </p> <p>We say that player II wins if $f \in A$ if and only if $g \in B$. Player I wins otherwise. The game $(A,B)$ is <em>determined</em> if one of the players has a winning strategy in this game. </p> <p>Suppose that $\Lambda, \Gamma \subset \mathscr{P}(\omega^\omega)$. $(\Gamma, \Lambda)$ wadge determinacy is the statement that for all $A \in \Lambda$ and $B \in \Gamma$, the Wadge game $(A, B)$ is determined.</p> <p>Define $\neg \Gamma = {\omega^\omega - A : A \in \Gamma}$. It is clear that $(\Gamma, \Lambda)$ determinacy implies $(\neg \Gamma, \neg\Lambda)$ determinacy. A winning strategy for player I (respectively player II) in $(A,B)$ is a winning strategy for player I (respectively player II) in the game $(\omega^\omega - A, \omega^\omega - B)$. </p> <p>My question is does $(\Gamma, \Lambda)$-determinacy implies the determinacy of $(\neg \Gamma, \Lambda)$ or $(\Lambda, \neg\Gamma)$? This appears to be equivalent to whether the determinacy of $(\Gamma,\Lambda)$ implies the determinacy of $(\Lambda, \Gamma)$? Do these classes need to be closed under certain operations for this hold? </p> <p>The cases I am most interested in is when $\Lambda, \Gamma$ are classes in the Borel Hierarchy, for example $(\Sigma_1^0, \Pi_1^0)$, i.e. (Open, Closed) and whether $(\Sigma_1^0, \Pi_1^0)$ Wadge determinacy is equivalent to $(\Sigma_1^0, \Sigma_1^0)$ Wadge determinacy. </p> <p>Thanks for any insight anyone can provide. </p> http://mathoverflow.net/questions/98844/strength-of-delta-10-subset-of-2-mathbbn-as-finite-union-of-specific-bas Strength of $\Delta_1^0$ subset of $2^\mathbb{N}$ as finite union of specific basic open sets. William 2012-06-05T05:41:44Z 2012-06-05T16:21:14Z <p>This question is to find the Reverse Mathematical strength of writing $\Delta_1^0$ (clopen) subset of $2^\mathbb{N}$ as a finite union $\bigcup_{\sigma \in F} [|\sigma|]$ where $F \subset 2^{&lt;\mathbb{N}}$ is finite and $[|\sigma|] = {f \in 2^{\mathbb{N}} : \sigma \prec f}$. </p> <p>More formally, if $\varphi(f)$ is a $\Delta_1^0$ formula in second order arithmetics, does there exists a finite set $F \subset 2^{&lt;\mathbb{N}}$ such that for any $f \in 2^\mathbb{N}$, $\varphi(f)$ hold if and only if there exists a $\sigma \in F$ such that $\sigma \prec f$. </p> <p>I am quite sure that $WKL_0$ can prove this by formalizing the usual compactness argument in Cantor space. Is this property equivalent to $WLK_0$ over $RCA_0$? Can anyone see a proof of this result from weaker systems like $WWLK_0$, $RCA_0$?</p> <p>Thanks for any help you can provide. I have proved something using the clopen principle above and an idea of the strength of this result would help me pinpoint the proof theoretic strength of what I am really interested in. Thanks very much. </p> http://mathoverflow.net/questions/71420/the-reverse-mathematics-of-writing-a-set-as-a-union The Reverse Mathematics of writing a set as a union? William 2011-07-27T17:39:13Z 2011-07-28T01:49:03Z <p>To be more precise, a countable collection of sets $(S_n)_{n \in \mathbb{N}}$ is encoded as the row of some given set $S$, i.e. $S_n = S^{[n]}$. Futhermore, for any function from $\mathbb{N} \rightarrow 2$, let $\bigcup_f S$ denote the union of the $S_n$ where $f(n) = 1$.</p> <p>The question is what is the strength of the following statement (over $\text{RCA}_0$) : For all $X$, if for all $m \in X$, there exists a $n$ such that $m \in S_n$ and $S_n \subset X$, then there exist a $f : \mathbb{N} \rightarrow 2$ such that $X = \bigcup_f S$.</p> <p>Clearly $\text{ACA}_0$ can prove this. However, I can not reverse this, over $\text{RCA}_0$. If it helps, this property feels very much like a special collection principle. That is for any $\Pi_1^0$ formula $\varphi(m,n)$ in free variable $m$ and $n$ : $(\forall m)(\exists n)\varphi(m,n) \Rightarrow (\exists X)(\forall m)(\exists n)(n\in X \wedge \varphi(m,n) \wedge (\forall n)(n \in X \Rightarrow (\exists m)\varphi(m,n))$. So this asserts that the solution for every $m$ exists in $X$ and all the elements of $x$ are solutions for some $m$. With this and using the $\Pi_1^0$ formula asserts $S_n$ is a subset, I can prove the union property above. However, I am not sure if I can go the other way. I am not certain of the strength of this collection principle either. </p> <p>Could someone tell me if the union property or the collection principle is equivalent to any well known systems over $\text{RCA}_0$ or how they relate to well-known systems. Thanks for any help. </p> http://mathoverflow.net/questions/103835/does-higher-order-arithmetic-interpret-the-axiom-of-choice Comment by William William 2012-08-03T03:15:53Z 2012-08-03T03:15:53Z If its helpful to know, second order arithmetics is a first order theory. The set variable are not actually second order variables. Usually the language would include a unary predicate that indicates something is a &quot;set&quot;. http://mathoverflow.net/questions/101708/wadge-determinacy-of-some-related-classes/101727#101727 Comment by William William 2012-07-09T03:39:23Z 2012-07-09T03:39:23Z So I should be more precise. Martin's result is proved in $ZF$ (maybe choice is needed). I want to work over a very weak system of set theory or second order arithmetic that is not capable of proving Wadge Determinacy. Now given particular determinacy like $(\Sigma_1^0, \Pi_1^0)$ can I use this determinacy to prove $(\Sigma_1^0, \Sigma_1^0)$ determinacy.