Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor space coded by $r$. For $M\models PA$ nonstandard, let $\mathcal{S}(M)$ be the standard system of $M$ thought of as a topological space (namely, as a subspace of Cantor space).

Say that a closed set pattern on a topological space $(X,\tau)$ is an assignment $c$ of $\tau$-closed sets to points in $X$.

EDIT: while it doesn't impact this question or the followup question, it seems natural in retrospect to also add the condition that the relation "$x\in c(y)$" be closed in the product topology; that is, the pattern itself should also be closed.

Every nonstandard $M\models PA$ has a corresponding closed set pattern on $\mathcal{S}(M)$ given by $$c_M: r\mapsto [r]\cap SS(M).$$ If $M$ is countable the space $\mathcal{S}(M)$ is homeomorphic to the rationals, so any interesting behavior is concentrated on $c_M$.

I would like to understand how closed set patterns of the form $c_M$ behave, and the following seems a good starting point. Say that closed set patterns $c_1,c_2$ on $\mathcal{X},\mathcal{Y}$ respectively are equivalent (and write $c_1\sim c_2$) if they differ by a homeomorphism - that is, if there is an $H:\mathcal{X}\cong\mathcal{Y}$ satisfying $$x\in c_1(y)\leftrightarrow H(x)\in c_2(H(y))$$ for all $x,y\in\mathcal{X}$. My question is:

Are there countable nonstandard $M,N\models PA$ such that $c_M\not\sim c_N$?

The knee-jerk approach to a positive answer would be a back-and-forth argument, but since the assignment of closed sets to reals isn't continuous in any good sense that doesn't seem to work here. On the other hand, I don't even see how to start approaching a negative answer.

  • $\begingroup$ Note that any countable Scott set is the standard system of a model of PA so I could have talked about those instead; my choice of language reflects my motivation ($c_M$ can be thought of as a "type-2 standard system" of $M$ in a sense), as does my choice in tags. The "reverse-math" tag is rather dubious, though, and I have no real objection to it being deleted if that connection is considered too weak. $\endgroup$ – Noah Schweber Feb 20 at 18:13
  • $\begingroup$ I'm also happy to alter the coding $r\mapsto [r]$, but that does seem to be the most natural choice at the moment. $\endgroup$ – Noah Schweber Feb 20 at 18:27
  • $\begingroup$ I have an idea that would seem to indicate that the answer is yes, but there's some computability facts you're going to have to fill in for me. The idea is to build a Scott set that is closed under Cantor-Bendixson derivatives, i.e. for any $r$ for every countable $\alpha$, there is an $s$ such that $[s]$ is the $\alpha$th Cantor-Bendixson derivative of $[r]$. This is only really countably many additional sets, so you can easily build a Scott set with this property. $\endgroup$ – James Hanson Feb 20 at 18:36
  • $\begingroup$ So the point is that for any $\Pi^0_1$ class $F$ in this Scott set, the Scott set computes every point in $F$ with ordinal CB rank. I want to say that a dumb Scott set, such as one in which everything is low, does not have this property, and I also want to say that this property is visible in corresponding closed set patterns (because of the easy observation that the topological closure of $c_M(r)$ in $2^{\omega}$ is $[r]$). $\endgroup$ – James Hanson Feb 20 at 18:36
  • $\begingroup$ Actually that last part is only easy if you're requiring that the homeomorphism is the restriction of an ambient homeomorphism, but it might still work without that requirement. $\endgroup$ – James Hanson Feb 20 at 18:39

Given any topological space $X$ and subset $F\subseteq X$, define the Cantor-Bendixson sequence of $F$ in $X$ as:

  • $F^{(0)} = F$
  • $F^{(\alpha +1)} = F^{(\alpha)} \setminus \{x \in F^{(\alpha)} : x \text{ is isolated in }F^{(\alpha)}\}$
  • $F^{(\beta)} = \bigcap_{\alpha < \beta} F^{(\alpha)}$, $\beta$ a limit ordinal.

Now we'll define the CB-rank of $F$, written $CB(F)$, to be the least ordinal $\alpha$ such that $F^{(\alpha)} = F^{(\alpha +1)}$ (I think this is a slightly non-standard definition). Note that this doesn't actually depend on the ambient space $X$. The typical argument gives us that for second countable $F$, $CB(F) < \omega_1$ (specifically, take a countable base for the topology on $F$, each set in this base can only be removed at most once in the sequence), and crucially $CB(F)$ only depends on the topological properties of $F$.

Fix a non-standard model $M$ of $PA$. Now, since $\mathcal{S}(M)$ is countable, we have that $\gamma = \sup _{r \in \mathcal{S}(M)}CB(c_M(r))$ is also a countable ordinal.

Now fix a countable closed subset $F \subseteq 2^{\omega}$ with $CB(F) > \gamma$ (such a set always exists, since $\alpha$ is countable). Pick a real $r$ such that $[r] = F$ and now take a countable model $N$ of $PA$ such that $r \in \mathcal{S}(N)$ and $F \subseteq \mathcal{S}(N)$. This is always possible by your comment that every Scott set is the standard system of some countable model of $PA$. (EDIT: But also just compactness and the downward Löwenheim–Skolem theorem, since we don't really care about the particular Scott set in question.)

So now clearly we have $c_N(r) = F$, so $CB(c_N(r)) = CB(F) >CB(c_M(s))$ for every $s \in \mathcal{S}(M)$, and thus we have $c_M\not\sim c_N$.

| cite | improve this answer | |

Here's another way to apply Cantor-Bendixson derivatives (following James Hanson): only some $M$s have the property that $ran(c_M)$ is closed under (single) Cantor-Bendixson derivatives. Specifically, let $T$ be the downward closure of the set of strings of the form $0^n1^k0^s$ such that $s=0$ or $\Phi_n(n)$ has halted by stage $k$ - so that the non-isolated paths of $T$ (besides the all-$0$s path) are those of the $0^n1^\infty$-form for $n$ in the halting problem. Any tree $S$ with $[S]=CB([T])$ would enumerate the complement of the halting problem: $n$ is not in the halting problem iff the part of $S$ above $0^n1$ eventually dies out. In particular, if $\mathcal{S}(M)$ doesn't contain the halting problem then $ran(c_M)$ won't contain $[CB(T)]\cap \mathcal{S}(M)$.

We can also use prunings. For $r\in \mathcal{S}(M)$, let $B_r=\{s\in\mathcal{S}(M): c_M(s)\supseteq c_M(r)\}$. Then we have that $B_r\in ran(c_M)$ for all $r$ iff in $\mathcal{S}(M)$ every tree has a pruning (= subtree with no dead ends and the same paths), which is of course equivalent to being arithmetically closed.

The right-to-left direction is essentially immediate: if $P$ is pruned then $[T]\not\supseteq [P]$ iff for some $\sigma\in P$ we have $\sigma\not\in T$, which is an open condition. In the left-to-right direction, note that a code for $B_r$ lets us enumerate the extendible nodes of the tree coded by $r$ ($\sigma$ is extendible in the tree coded by $r$ iff the real coding the tree of strings $\not\succcurlyeq\sigma$ is not in $B_r$), and the non-extendible nodes of the tree are a priori (relatively) computably enumerable.

Two final remarks:

  • Note that when we shift attention to the $\omega$-models of $WKL_0$ given by the standard systems, the two arguments above are pointing at $ACA_0$: for $M\models PA$ nonstandard, $ran(c_M)$ is closed under (single) Cantor-Bendixson derivatives iff $B_r\in ran(c_M)$ for all $r\in \mathcal{S}(M)$ iff $\mathcal{S}(M)$ is arithmetically closed. I've followed up on this line of thought here.

  • All these arguments so far leave open the problem of whether we can have $c_M\not\sim c_N$ for "finer" reasons. Specifically, for $c_1,c_2$ closed set patterns on $\mathcal{X},\mathcal{Y}$, write $c_1\approx c_2$ if there is some $H:\mathcal{X}\cong\mathcal{Y}$ such that $ran(c_2)=\{H[A]: A\in ran(c_1)\}$; then we can ask whether there countable nonstandard $M,N\models PA$ with $c_M\not \sim c_N$ but $c_M\approx c_N$, and I don't see how to attack this at the moment.

| cite | improve this answer | |

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.