Kenneth Gill - Indivisibility and uniform computational strength

lmcs:13563 - Logical Methods in Computer Science, June 10, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:22)2025
Indivisibility and uniform computational strengthArticle

Authors: Kenneth Gill

    A countable structure is indivisible if for every coloring with finite range there is a monochromatic isomorphic subcopy of the structure. Each indivisible structure naturally corresponds to an indivisibility problem which outputs such a subcopy given a presentation and coloring. We investigate the Weihrauch complexity of the indivisibility problems for two structures: the rational numbers $\mathbb{Q}$ as a linear order, and the equivalence relation $\mathscr{E}$ with countably many equivalence classes each having countably many members. We separate the Weihrauch degrees of both corresponding indivisibility problems from several benchmarks, showing in particular that the indivisibility problem for $\mathbb{Q}$ cannot solve the problem of finding a monochromatic rational interval given a coloring for which there is one; and that the Weihrauch degree of the indivisibility problem for $\mathscr{E}$ is strictly between those of $\mathsf{RT}^2$ and $\mathsf{SRT}^2$, two widely studied variants of Ramsey's theorem for pairs whose reverse-mathematical separation was open until recently.


    Volume: Volume 21, Issue 2
    Published on: June 10, 2025
    Accepted on: March 7, 2025
    Submitted on: May 9, 2024
    Keywords: Mathematics - Logic,Computer Science - Logic in Computer Science,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 341 times.
    This article's PDF has been downloaded 132 times.