User william - MathOverflow

Wadge Determinacy of some related classes.

2012-07-08T21:53:00Z

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

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 determined if one of the players has a winning strategy in this game.

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.

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

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?

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.

Thanks for any insight anyone can provide.

Strength of $\Delta_1^0$ subset of $2^\mathbb{N}$ as finite union of specific basic open sets.

2012-06-05T05:41:44Z

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^{<\mathbb{N}}$ is finite and $[|\sigma|] = {f \in 2^{\mathbb{N}} : \sigma \prec f}$.

More formally, if $\varphi(f)$ is a $\Delta_1^0$ formula in second order arithmetics, does there exists a finite set $F \subset 2^{<\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$.

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

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.

The Reverse Mathematics of writing a set as a union?

2011-07-27T17:39:13Z

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

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

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.

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.

Comment by William

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 "set".

Comment by William

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.