The Reverse Mathematics of writing a set as a union? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:34:47Z http://mathoverflow.net/feeds/question/71420 http://www.creativecommons.org/licenses/by-nc/2.5/rdf 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/71420/the-reverse-mathematics-of-writing-a-set-as-a-union/71428#71428 Answer by François G. Dorais for The Reverse Mathematics of writing a set as a union? François G. Dorais 2011-07-27T18:57:43Z 2011-07-27T18:57:43Z <p>I only have a partial answer so far... </p> <blockquote> <p>The Union Principle implies $\Sigma^0_1$-Separation (which is equivalent to the Weak König Lemma).</p> </blockquote> <p>Let $h_0, h_1:\mathbb{N}\to\mathbb{N}$ be two functions with disjoint ranges. Define $$S_{2n+i} = \{ m : m = n \lor (\exists k \leq m)(h_i(k) = n)\}.$$ Note that either $S_{2n} = \{n\}$ or $S_{2n+1} = \{n\}$ (possibly both) so every set $X$ satisfies the precondition for the Union Principle.</p> <p>Let $f_0,f_1:\mathbb{N}\to2$ be such that $\bigcup_{f_0} S_n$ is the set of even numbers and $\bigcup_{f_1} S_n$ is the set of odd numbers.</p> <p>Note that if $f_0(4n) = 1$ then $2n$ is not in the range of $h_0$ and if $f_0(4n+1) = 1$ then $2n$ is not in the range of $h_1$. Since we must have either $f_0(4n) = 1$ or $f_0(4n+1) = 1$, the set $$X_0 = \{2n : f_0(4n) = 1\}$$ is such that all the even values of $h_1$ are in $X_0$ and none of the even values of $h_0$ are in $X_0$.</p> <p>Similarly, if $f_1(4n+2) = 1$ then $2n+1$ is not in the range of $h_0$ and if $f_1(4n+3) = 1$ then $2n+1$ is not in the range of $h_1$. Since we must have either $f_1(4n+2) = 1$ or $f_1(4n+3) = 1$, the set $$X_1 = \{2n+1 : f_1(4n+2) = 1\}$$ is such that all the odd values of $h_1$ are in $X_1$ and none of the odd values of $h_0$ are in $X_1$.</p> <p>It follows that $X_0 \cup X_1$ separates the ranges of $h_0$ and $h_1$.</p> http://mathoverflow.net/questions/71420/the-reverse-mathematics-of-writing-a-set-as-a-union/71434#71434 Answer by Ricky Demer for The Reverse Mathematics of writing a set as a union? Ricky Demer 2011-07-27T20:16:13Z 2011-07-28T00:39:50Z <p>Let $Y$ be a member of the <a href="http://en.wikipedia.org/wiki/Turing_degree" rel="nofollow">Turing degree</a> $[Y\hspace{.04 in}]$. $\;$ Define <code>$canhalt : \omega \times \omega \to \{\text{false},\text{true}\}$</code> by <br><br> $canhalt(s,t) \iff$ <br> there exists an $s$-state $Y$-<a href="http://en.wikipedia.org/wiki/Oracle_machine" rel="nofollow">oracle machine</a> that runs exactly $t$ steps if started on a blank tape <br><br><br> Define $pair : \omega \times \omega \to \omega$ to be the <a href="http://en.wikipedia.org/wiki/Pairing_function" rel="nofollow">Cantor pairing function</a>. $\; \; pair$ has a graph and is a bijection. <br> There are only finitely many $m$-state $Y$-<a href="http://en.wikipedia.org/wiki/Oracle_machine" rel="nofollow">oracle machines</a>, and these are easily enumerated, <br> so define $\langle S_0,S_1,S_2,S_3,...\rangle$ by <br><br> $((2\cdot n)\in S_{pair(s,t)}) \iff n=s$ <br> and <br> $(((2\cdot n)+1)\in S_{pair(s,t)}) \iff (t\lt n$ and $canhalt(s,n))$ <br><br><br> and note that for all $s$, <code>$\{t : canhalt(s,t)\}$</code> is finite. <br> Define $bb_Y : \omega \to \omega$ by <code>$bb_Y(s) = \operatorname{max}(\{t : canhalt(s,t)\})$</code>. $\;$ ($bb_Y$ does not necessarily have a graph) <br> Define <code>$E = \{n : n\, \text{ is even} \}$</code>. $\;$ By construction, for all members $n$ of $E$, $\; n\in S_{pair(m,bb_Y(m))} \subseteq E \;$. <br> Assuming the Union Principle, let $I$ be a subset of $\omega$ such that $\; \; \; \displaystyle\bigcup_{i\in I} \; S_i \; \; = \; \; X \; \; \;$. <br><br> By the construction of $\langle S_0,S_1,S_2,S_3,...\rangle$ and $I$, for all $s$ there exists $t$ such that $pair(s,t)\in I$, <br> and for all $s$ and $t$ if $pair(s,t)\in I$ then $bb_Y(s) \leq t$. <br> Let $\langle mach_0,mach_1,mach_2,mach_3,...\rangle$ be a reasonable enumeration of the $Y$-<a href="http://en.wikipedia.org/wiki/Oracle_machine" rel="nofollow">oracle machines</a>. $\;$ Define $states : \omega \to \omega$ by $\; states(m) =$ the number of states in $mach_m \;$. <br> Since the enumeration is reasonable, $states$ has a graph. <br> For all $m$ and $t$, if $pair(states(m),t)\in I$ then <br><br> $mach_m$ halts within $t$ steps if started on a blank tape <br> $\implies$ <br> $mach_m$ halts if started on a blank tape <br> $\implies$ <br> $mach_m$ runs exactly a member of <code>$\{t : canhalt(states(m),t)\}$</code> steps if started on a blank tape <br> $\implies$ <br> $mach_m$ halts within $bb_Y(states(m))$ steps if started on a blank tape <br> $\implies$ <br> $mach_m$ halts within $t$ steps if started on a blank tape <br><br><br> Now, since the enumeration is reasonable, define <code>$H = \{m : mach_m\; \text{halts within}\; t\; \text{steps when started on a blank tape, where}\; pair(states(m),t)\in I \}$</code>. By the above, $[Y\hspace{.04 in}]' = [Y\hspace{.02 in}'] = [H\hspace{.02 in}]$ exists. $\;$ This works for all <a href="http://en.wikipedia.org/wiki/Turing_degree" rel="nofollow">Turing degrees</a>, so (RCA0 + Union Principle) proves all of ACA0. $\;$ Clearly ACA0 proves the Union principle, and ACA0 is stronger than RCA0. <br><br><br><br> Therefore the Union Principle is equivalent to ACA0 over RCA0.</p> http://mathoverflow.net/questions/71420/the-reverse-mathematics-of-writing-a-set-as-a-union/71440#71440 Answer by Carl Mummert for The Reverse Mathematics of writing a set as a union? Carl Mummert 2011-07-27T21:32:02Z 2011-07-28T01:49:03Z <p>Due to my own confusion, I had a hard time reading Ricky Demer's proof, but I think it is correct. I couldn't fit this remark in a comment so this is a community wiki post where I will try to rephrase the proof in a way that I can grasp more quickly. Maybe it will help others as well. </p> <p>We work in $RCA_0$. To establish $ACA_0$ it is sufficient to prove that the range of each injective function exists. Let $f\colon \mathbb{N} \to \mathbb{N}$ be injective. </p> <p>For each $i$ define <code>$$S_{(i,j)} = \{2i\} \cup \{ 2k+1 : j &lt; k \land f(k) &lt; i\}$$</code> The sequence <code>$\{ S_{(i,j)} : i,j \in \mathbb{N}\}$</code> is uniformly definable with a bounded-quantifier formula relative to $f$ so it can be formed in $RCA_0$.</p> <p>Because $f$ is injective, for each $i$ the set <code>$\{ k : f(k) &lt; i\}$</code> is bounded, and so for each $i$ there is a $j$ such that <code>$S_{(i,j)} = \{2i\}$</code>. To prove that the set is bounded seems to require an argument using bounded $\Sigma^0_1$ comprehension to form the set of elements less than $i$ in the range, then using quantifier-free bounding to show the range of this is bounded. (Is there an easier way?) In general, the "bounding principle" for a class of formulas $\Gamma$ says that the image of a bounded set of numbers under a $\Gamma$-definable function is bounded. </p> <p>Let $E$ be the set of even numbers. By the Union Principle, there is a set $I$ such that $E = \bigcup_{(i,j) \in I} S_{(i,j)}$. Note that if $(i,j) \in I$ then $S_{(i,j)} = \{2i\}$. Also note that for every $i$ there is at least one $j$ such that $(i,j) \in I$. Given $i$, let $h(i)$ be the first $j$ such that $(i,j) \in I$. Since $$(\exists k)(f(k) = \ell) \iff (\exists k &lt; h(\ell+1))(f(k) = \ell)$$ we can define the range of $f$ using only bounded quantifiers. Thus we can form the range of $f$ in $RCA_0$. </p>