The Ginsburg--Sands theorem and computability theory
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913405133127680 |
|---|---|
| author | Benham, Heidi De Lapo, Andrew Dzhafarov, Damir Solomon, Reed Villano, Java Darleen |
| author_facet | Benham, Heidi De Lapo, Andrew Dzhafarov, Damir Solomon, Reed Villano, Java Darleen |
| contents | The Ginsburg--Sands theorem from topology states that every infinite topological space has an infinite subspace homeomorphic to exactly one of the following five topologies on $ω$: indiscrete, discrete, initial segment, final segment, and cofinite. The original proof is nonconstructive, and features an interesting application of Ramsey's theorem for pairs ($\mathsf{RT}^2_2$). We analyze this principle in computability theory and reverse mathematics, using Dorais's formalization of CSC spaces. Among our results are that the Ginsburg-Sands theorem for CSC spaces is equivalent to $\mathsf{ACA}_0$, while for Hausdorff spaces it is provable in $\mathsf{RCA}_0$. Furthermore, if we enrich a CSC space by adding the closure operator on points, then the Ginsburg-Sands theorem turns out to be equivalent to the chain/antichain principle ($\mathsf{CAC}$). The most surprising case is that of the Ginsburg-Sands theorem restricted to $T_1$ spaces. Here, we show that the principle lies strictly between $\mathsf{ACA}_0$ and $\mathsf{RT}^2_2$, yielding arguably the first natural theorem from outside logic to occupy this interval. As part of our analysis of the $T_1$ case we introduce a new class of purely combinatorial principles below $\mathsf{ACA}_0$ and not implied by $\mathsf{RT}^2_2$ which form a strict hierarchy generalizing the stable Ramsey's theorem for pairs ($\mathsf{SRT}^2_2$). We show that one of these, the $Σ^0_2$ subset principle ($Σ^0_2$-$\mathsf{Subset}$), has the property that it, together with the cohesive principle ($\mathsf{COH}$), is equivalent over $\mathsf{RCA}_0$ to the Ginsburg--Sands theorem for $T_1$ CSC spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05990 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Ginsburg--Sands theorem and computability theory Benham, Heidi De Lapo, Andrew Dzhafarov, Damir Solomon, Reed Villano, Java Darleen Logic The Ginsburg--Sands theorem from topology states that every infinite topological space has an infinite subspace homeomorphic to exactly one of the following five topologies on $ω$: indiscrete, discrete, initial segment, final segment, and cofinite. The original proof is nonconstructive, and features an interesting application of Ramsey's theorem for pairs ($\mathsf{RT}^2_2$). We analyze this principle in computability theory and reverse mathematics, using Dorais's formalization of CSC spaces. Among our results are that the Ginsburg-Sands theorem for CSC spaces is equivalent to $\mathsf{ACA}_0$, while for Hausdorff spaces it is provable in $\mathsf{RCA}_0$. Furthermore, if we enrich a CSC space by adding the closure operator on points, then the Ginsburg-Sands theorem turns out to be equivalent to the chain/antichain principle ($\mathsf{CAC}$). The most surprising case is that of the Ginsburg-Sands theorem restricted to $T_1$ spaces. Here, we show that the principle lies strictly between $\mathsf{ACA}_0$ and $\mathsf{RT}^2_2$, yielding arguably the first natural theorem from outside logic to occupy this interval. As part of our analysis of the $T_1$ case we introduce a new class of purely combinatorial principles below $\mathsf{ACA}_0$ and not implied by $\mathsf{RT}^2_2$ which form a strict hierarchy generalizing the stable Ramsey's theorem for pairs ($\mathsf{SRT}^2_2$). We show that one of these, the $Σ^0_2$ subset principle ($Σ^0_2$-$\mathsf{Subset}$), has the property that it, together with the cohesive principle ($\mathsf{COH}$), is equivalent over $\mathsf{RCA}_0$ to the Ginsburg--Sands theorem for $T_1$ CSC spaces. |
| title | The Ginsburg--Sands theorem and computability theory |
| topic | Logic |
| url | https://arxiv.org/abs/2402.05990 |