Reverse mathematics of a color basis theorem
The infinite pigeonhole theorem asserts that if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:mrow> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> <mml:mo stretchy="false">→</mml:mo> <mml:mi>m</mml:mi> </mml:math> is a function with a finite range, then there is a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>j</mml:mi> <mml:mo><</mml:mo> <mml:mi>m</mml:mi> </mml:math> such that the set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> <mml:mo>∣</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>j</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:math> is infinite. This article uses the techniques of reverse mathematics and Weihrauch analysis to examine the strength of a theorem that finds all the values that occur infinitely often in the range of a function.
Authors
- Jessica Ross (ORCID: https://orcid.org/0000-0001-6265-1966)
- Caleb Davis
- Jeffry L. Hirst (ORCID: https://orcid.org/0000-0002-8273-8951)
- Bryan W. Miller (ORCID: https://orcid.org/0000-0002-5665-376X)
- Silva Keohulian
Institutions
- Guilford Technical Community College (US)
- Appalachian State University (US)
Publication Details
- Journal
- Computability
- Published
- 2025-05-01
- DOI
- https://doi.org/10.1177/22113568241304637
- Primary Topic
- Matrix Theory and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00