Code universal arithmetical sets by a hyperarithmetical set? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T18:31:17Z http://mathoverflow.net/feeds/question/71083 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71083/code-universal-arithmetical-sets-by-a-hyperarithmetical-set Code universal arithmetical sets by a hyperarithmetical set? Cole Leahy 2011-07-23T20:17:47Z 2011-07-25T15:31:09Z <p>For each n, there is a (lightface) &Sigma;<sup>0</sup><sub>n</sub> set S<sub>n</sub> &subseteq; &omega;<sup>2</sup> that's universal for the &Sigma;<sup>0</sup><sub>n</sub> subsets of &omega;. Since {n} &times; S<sub>n</sub> is &Sigma;<sup>0</sup><sub>n</sub>, there is a union R of arithmetical sets such that (n, j, k) &in; R iff (j, k) &in; S<sub>n</sub>. Clearly R is not itself arithmetical, and offhand I don't see why it should be &Delta;<sup>1</sup><sub>1</sub>.</p> <p>If we define the sets S<sub>n</sub> with care, is there a &Delta;<sup>1</sup><sub>1</sub> set Q &subseteq; &omega;<sup>3</sup> such that (n, j, k) &in; Q iff (j, k) &in; S<sub>n</sub>? </p> http://mathoverflow.net/questions/71083/code-universal-arithmetical-sets-by-a-hyperarithmetical-set/71089#71089 Answer by Ali Enayat for Code universal arithmetical sets by a hyperarithmetical set? Ali Enayat 2011-07-23T22:04:13Z 2011-07-23T22:38:24Z <blockquote> <p>The answer to your question is positive.</p> </blockquote> <p>Note that the sets $S_n$ that you define can be identified with the set $TA_n$ of Gödel numbers of all first order $\Sigma_n$ sentences true in the structure $(\omega, +, \cdot)$. Let $TA$ (true arithmetic) be the set of Gödel numbers of <strong>all</strong> first order sentences true in the structure $(\omega, +, \cdot)$. </p> <blockquote> <p>$TA$ is not only hyperarithmetic, but it is an <em>arithmetic singleton</em> (this is sometimes rephrased as "$TA$ is <em>implicitly definable</em>"). This means there is first order formula $\phi(X)$, formulated in the arithmetical vocabulary augmented with a new unary predciate $X$ such that:</p> <p>For all subsets $X$ of $\omega$, $(\omega, +, \cdot, X)$ satisfies $\phi(X)$ iff $X=TA$.</p> </blockquote> <p>The implicit definability of $TA$ is attributed to Hilbert, Bernays, Kuznecov, and Trahtenbrot in Roger's <strong>Theory of Effective Functions and Effective Computability</strong> (p.344. Thm XII; see also p.381, Thm XI, where $TA$ is referred to as $V$).</p> <p>It is easy to see that every arithmetic singleton is hyperarithmetic, but the converse is false. For example, there is a hyperarithmetic set that is arithmetically generic; and of course no arithmetically generic set can be an arithmetic singleton.</p> <p>For more more detail on the above paragraph, as well as an exposition of implicit definability of $TA$, see the text <strong>Computability and Logic</strong>, by Boolos, Jeffrey, and Burgess.</p> http://mathoverflow.net/questions/71083/code-universal-arithmetical-sets-by-a-hyperarithmetical-set/71167#71167 Answer by Cole Leahy for Code universal arithmetical sets by a hyperarithmetical set? Cole Leahy 2011-07-25T00:44:55Z 2011-07-25T14:43:41Z <p>There is a (lightface) &Sigma;<sup>0</sup><sub>1</sub> set A &subseteq; &omega; such that for each p > 0 the &Sigma;<sup>0</sup><sub>1</sub> set T<sup>p</sup> &subseteq; &omega;<sup>p</sup> given by</p> <blockquote> <p>T<sup>p</sup>( j,x<sub>1</sub>,&hellip;,x<sub>p</sub> ) iff &exist;t[ &lang; j,&lang; x<sub>1</sub>,&hellip;,x<sub>p</sub>,t &rang;,1 &rang; &in; A ]</p> </blockquote> <p><em>parametrizes</em> the &Sigma;<sup>0</sup><sub>1</sub> subsets of &omega;<sup>p</sup>, in the sense that X &subseteq; &omega;<sup>p</sup> is &Sigma;<sup>0</sup><sub>1</sub> iff for some j, X is the j-section</p> <blockquote> <p>{ (x<sub>1</sub>,&hellip;,x<sub>p</sub>) : T<sup>p</sup>( j,x<sub>1</sub>,&hellip;,x<sub>p</sub> ) }</p> </blockquote> <p>of T<sup>p</sup>. The set A is obtained by formalizing Kleene's notion of recursive derivation. (For details, see p. 127 of Moschovakis's <em>Descriptive Set Theory</em>, Second Edition. Any odd notation I use below is from that book; for instance, the asterisk will denote concatenation.)</p> <p>We use A to define, for each pair p,n > 0, a set S<sup>p</sup><sub>n</sub> &subseteq; &omega;<sup>p+1</sup> that parametrizes the &Sigma;<sup>0</sup><sub>n</sub> subsets of &omega;<sup>p</sup>. It will be useful to write &phi;(&alpha;) as shorthand for the conjunction of this</p> <blockquote> <p>&forall;j &forall;y [ &exist;i (&alpha;(i) = &lang;1,j,y&rang;) &leftrightarrow; (Seq(y) &wedge; &exist;t (&lang;j,y&ast;&lang;t&rang;,1 &in; A)) ]</p> </blockquote> <p>with this</p> <blockquote> <p>&forall;j &forall;y &forall;m>0 [ &exist;i (&alpha;(i) = &lang;m+1,j,y&rang;) &leftrightarrow; (Seq(y) &wedge; &exist;t &not;&exist;h (&alpha;(h) = &lang;m,j,y&ast;&lang;t&rang;&rang;)) ].</p> </blockquote> <p>Here &alpha; ranges over <sup>&omega;</sup>&omega; and the Roman letters range over &omega;. Maintaining this convention, write &psi;(&alpha;,n,j,y) for</p> <blockquote> <p>&exist;m [ n = m+1 &wedge; &exist;i (&alpha;(i) = &lang;m+1,j,y&rang;) ].</p> </blockquote> <p>Notice that &phi;(&alpha;) &wedge; &psi;(&alpha;,n,j,y) defines an arithmetical subset of <sup>&omega;</sup>&omega; &times; &omega;<sup>3</sup>. Hence the set H &subseteq; &omega;<sup>3</sup> given by</p> <blockquote> <p>H(n,j,k) iff &exist;&alpha; (&phi;(&alpha;) &wedge; &psi;(&alpha;,n,j,y))</p> </blockquote> <p>is &Sigma;<sup>1</sup><sub>1</sub> since that pointclass is closed under projection along <sup>&omega;</sup>&omega;. Moreover, induction on n reveals that</p> <blockquote> <p>&exist;&alpha; (&phi;(&alpha;) &wedge; &psi;(&alpha;,n,j,y))</p> </blockquote> <p>is equivalent to</p> <blockquote> <p>&forall;&alpha; (&phi;(&alpha;) &rightarrow; &psi;(&alpha;,n,j,y))</p> </blockquote> <p>so that H is in fact &Delta;<sup>1</sup><sub>1</sub>. Now for p,n > 0 define</p> <blockquote> <p>S<sup>p</sup><sub>n</sub> = { (j,x<sub>1</sub>,&hellip;,x<sub>p</sub>) : H(n,j,&lang;x<sub>1</sub>,&hellip;,x<sub>p</sub>&rang;) }.</p> </blockquote> <p>By induction on n, for each p the set S<sup>p</sup><sub>n</sub> parametrizes the &Sigma;<sup>0</sup><sub>n</sub> subsets of &omega;<sup>p</sup>. For the base, use the first conjunct of &phi;(&alpha;) to show that S<sup>p</sup><sub>1</sub> = T<sup>p</sup> for each p. For the inductive step, use the inductive hypothesis and the second conjunct of &phi;(&alpha;).</p> <p>Finally, let Q &subseteq; &omega;<sup>3</sup> be the &Delta;<sup>1</sup><sub>1</sub> set given by</p> <blockquote> <p>Q(n,j,k) iff H(n,j,&lang;k&rang;)</p> </blockquote> <p>so that (n,j,k) &in; Q iff (j,k) &in; S<sup>1</sup><sub>n</sub>. If the foregoing is free of errors, this answers my original question.</p> <p>The motivation for that question might have been obvious, but I'll put it down for the record.</p> <blockquote> <p><em>The set Q witnesses that the arithmetical sets are not the "effective analog" of the Borel sets.</em></p> </blockquote> <p>A classical result of Suslin is that the (boldface) <b>&Delta;<sup>1</sup><sub>1</sub></b> sets coincide with the Borel sets. Since the arithmetical hierarchy resembles the Borel hierarchy, one might expect that the relationship between &Delta;<sup>1</sup><sub>1</sub> and arithmetical resembles that between <b>&Delta;<sup>1</sup><sub>1</sub></b> and Borel, enough perhaps that &Delta;<sup>1</sup><sub>1</sub> and arithmetical would coincide. It is well known that this expectation is false, and indeed the &Delta;<sup>1</sup><sub>1</sub> set Q witnesses this. For if Q were arithmetical, it would be &Sigma;<sup>0</sup><sub>n</sub> for some n. Taking any &Sigma;<sup>0</sup><sub>n+1</sub> set P &subseteq; &omega;, there is some j such that for all k</p> <blockquote> <p>P(k) iff (j,k) &in; S<sup>1</sup><sub>n+1</sub> iff (n+1,j,k) &in; Q.</p> </blockquote> <p>Since Q is &Sigma;<sup>0</sup><sub>n</sub> by hypothesis, so is P. But then, since P was arbitrary, every &Sigma;<sup>0</sup><sub>n+1</sub> subset of &omega; is in fact &Sigma;<sup>0</sup><sub>n</sub>, contradicting the theorem that the arithmetical hierarchy is proper.</p> http://mathoverflow.net/questions/71083/code-universal-arithmetical-sets-by-a-hyperarithmetical-set/71215#71215 Answer by Andreas Blass for Code universal arithmetical sets by a hyperarithmetical set? Andreas Blass 2011-07-25T12:06:18Z 2011-07-25T12:06:18Z <p>Perhaps the quickest answer to the original question is that the clause "If we define the sets <code>$S_n$</code> with care" makes things look worse than they are. If you use any of the standard constructions of the universal <code>$\Sigma^0_n$</code> sets <code>$S_n$</code>, then the $Q$ obtained by stacking them next to each other will be hyperarithmetical. Care (of a somewhat perverse sort) would be needed to get $Q$ <em>not</em> to be hyperarithmetical. (Perverse care might consist of coding some non-hyperarithmetical set by putting its $n$-th bit into the $(0,0)$ position of <code>$S_n$</code>.) </p>