2
$\begingroup$

This question basically follows this earlier question of mine but shifting from standard systems of nonstandard models of $PA$ to $\omega$-models of $RCA_0$. For $X$ a Turing ideal we get the map $c_X$ on $2^\omega$ given by $c_X(x)=[b[x]]\cap X$ where $b$ is some computable bijection $\omega\cong 2^{<\omega}$; in the language of the linked question, this is a closed set pattern.

I'm trying to understand how much information this construction loses in the sense of second-order arithmetic. For $X$ a Turing ideal we also get an $\omega$-model of $RCA_0$ - which I'll freely conflate with $X$ itself - and I'm interested in what axioms of second-order arithmetic we can detect topologically.

(Below, $\sim$ denotes "difference by homeomorphism" - for $c,d$ closed set patterns on $\mathcal{X},\mathcal{Y}$ we write $c\sim d$ iff for some $H:\mathcal{X}\cong\mathcal{Y}$ we have $a\in c(b)\leftrightarrow H(a)\in d(H(b))$ for all $a,b\in\mathcal{X}$.)

Say that a theory of second-order arithmetic is topologically detectable if there is some $\sim$-respecting property of closed set patterns which holds of $c_X$ iff $X\models A$ for each Turing ideal $X$. For example:

  • $WKL_0$ is topologically detectable via "$c_X^{-1}(\emptyset)$ is open."

  • $ACA_0$ is topologically detectable in at least two ways (after adding $WKL_0$): via "$ran(c_X)$ is closed under (single) Cantor-Bendixson derivatives" and "for each $x\in X$ the set $\{y\in X: c(y)\supseteq c(x)\}$ is closed."

My question is essentially whether any other "weak combinatorial principles" are topologically detectable:

Is there some "reasonably natural" $A$ with $ACA_0\models A$ and $WKL_0\not\models_\omega A$ such that $A$ (or at least $WKL_0+A$) is topologically detectable?

(Here $\models_\omega$ is the restriction of $\models$ to $\omega$-models, which is needed to rule out e.g. $I\Sigma_{17}$. Note that if $A$ is topologically detectable then so is $WKL_0+A$, but the converse isn't obvious to me.)

The most tempting candidate is of course $RT^2_2$, but there are plenty of others.

$\endgroup$
  • $\begingroup$ Is there a good list of things that are know to follow from $ACA_0$ but not $WKL_0$? All of the examples I can find seem to be related to $RT_2^2$. $\endgroup$ – James Hanson Feb 29 at 17:24
  • $\begingroup$ @JamesHanson Re: your first question, at a glance they don't need that but I was being lazy - we can always throw on "... and $\{a: c_X(a)=\emptyset\}$ is open" to whatever characterization we have, as long as we're shooting for a principle above $WKL_0$. Re: your second question, yes the paradigm is Ramsey theory - the reverse math zoo is a good source. $\endgroup$ – Noah Schweber Feb 29 at 17:24
0
$\begingroup$

Statements about existence of $\omega$-models can be topologically detected.

Specifically, fix $X$ a Turing ideal. For $t\in X$ say that $t$ enumerates a family of sets if:

  • Exactly one $p\in c_X(t)\cap X$ has $c_X(p)=X$.

  • For every other $q\in c_X(t)$ we have $c_X(q)=\{a\}$ for some $a\in y$.

  • For each $a\in y$ there is exactly one $q\in c_X(t)$ with $c_X(q)=\{a\}$.

In such a case we say $t$ enumerates the family $$X_t:=\{q\in X: \exists a\in c_X(t)(c_X(a)=\{q\})\},$$ and we can talk about the induced closed set pattern coming from $X_t$. It's not hard to see$^*$ that every sequence of sets in $X$ (that is, the whole sequence is in $X$) corresponds to such an $X_t$, and this means:

If $A$ is a topologically detectable sentence, so is the statement $O_A$ = "Every real is contained in an $\omega$-model of $A$."

Taking $A=WKL_0$ then gives an affirmative answer to the question. Of course $RCA_0+O_{WKL_0}\vdash WKL_0$: if $X$ is an $\omega$-model of $RCA_0$ and $T$ is an infinite binary tree in $X$, then any $\omega$-model of $WKL_0$ containing $T$ also thinks $T$ is an infinite binary tree - and being a path through a tree is absolute between $\omega$-models. (More generally, we have $$RCA_0+ O_\varphi\vdash\varphi$$ for every $\varphi\in\Pi^1_2$.)

Meanwhile, $RCA_0+O_{RCA_0}\vdash WKL_0$, since from a coded $\omega$-model of $RCA_0$ we can whip up a $DNR_2$ function (and this relativizes). So this approach does not produce an example of a topologically detectable sentence incomparable with $WKL_0$.


$^*$Specifically, given a sequence of reals $F=(f_i)_{i\in\omega}$ let $s_i$ be the natural code for the tree $$\{\sigma\in 2^{<\omega}: \vert\sigma\vert<i\mbox{ or }\sigma\prec f\}.$$ The closure of $\{s_i: i\in\omega\}$ is the set of paths through a pruned tree $T$ - which is computable in $F$ - and $[T]$ has only one "extra" path, corresponding to $2^{<\omega}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Of course this isn't totally satisfying - something of Ramseyan flavor would be better, and I'll hold off on accepting this answer in the hopes of a better answer - but it does give something. $\endgroup$ – Noah Schweber Feb 29 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.