Problem Reducibility of Weakened Ginsburg—Sands Theorem

Abstract: A recent paper by Benham, DeLapo, Dzhafarov, Solomon, and Villano entitled “Ginsburg—Sands theorem and computability theory” analyzes computability theoretical and reverse mathematical strength of a topological theorem by Ginsburg and Sands, along with several weakened versions. The original theorem states that every infinite topological space has an infinite subspace homeomorphic to one of the following on the natural numbers: indiscrete, initial segment, final segment, discrete, or cofinite. In this original paper, it is claimed that the theorem is a consequence of Ramsey’s Theorem, and though it has been shown by Benham, DeLapo, Dzhafarov, Solomon, and Villano that the full theorem is equivalent over RCA_0 to ACA_0, there is a weakened version that is equivalent over RCA_0 to CAC (Chain-antichain Principle), a consequence of Ramsey’s Theorem. One interesting feature of the proof of this equivalence is that, not only an application CAC, but also an application of ADS (Ascending/descending Sequence Principle), which is a consequence of CAC, is used. This inspires the question of whether this weakened version of the Ginsburg—Sands Theorem and CAC, when viewed as problems, are Weihrauch equivalent.

I will present some new progress that has been made on this question. This progress involves developing several new combinatorial problems related to CAC and ADS, one of which is Weihrauch equivalent to the weakened version of the Ginsburg—Sands Theorem, and showing a variety of Weihrauch and computable reducibilities between them.

general topologylogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic