Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application

Technische Samenvatting: "Hindman's stelling codeert $\emptyset^{(\omega)}$ niet in één enkele toepassing"

Probleemstelling
Het artikel behandelt de computationeel-theoretische complexiteit van de stelling van Hindman (HT), specifiek met betrekking tot de sterkte van de oplossingen die het produceert ten opzichte van de invoerkleuring. De stelling van Hindman stelt dat voor elke eindige kleuring van de natuurlijke getallen $\mathbb{N}$, er een oneindige verzameling $H$ bestaat waarvoor de verzameling van alle niet-lege eindige sommen van verschillende elementen van $H$ (aangeduid als $FS(H)$) monochroom is.

Eerder werk bepaalde de volgende grenzen:

1. Bovengrens: Blass, Hirst en Simpson (1987) bewezen dat voor elke berekenbare kleuring er een oplossing bestaat die berekenbaar is vanuit de $\omega$-sprong van de lege verzameling, $\emptyset^{(\omega)}$.
2. Ondergrens: Dezelfde auteurs bewezen dat er een berekenbare kleuring bestaat waarbij elke oplossing de halting-verzameling $\emptyset'$ berekent. Later verbeterde Liao (2026) dit door aan te tonen dat voor sommige berekenbare kleuringen geen $\Pi^0_3$-oplossing bestaat.

De centrale openstaande vraag die dit artikel adresseert, is of de bovengrens van $\emptyset^{(\omega)}$ optimaal is voor een enkele toepassing van de stelling. Specifiek: admitteert elke arithmetische instantie van de stelling van Hindman een oplossing die $\emptyset^{(\omega)}$ niet berekent?

Methodologie
De auteurs maken gebruik van een forcing-techniek die is aangepast van Towsners combinatorische bewijs van de stelling van Hindman. De methodologie bevat de volgende componenten:

1. Herformulering: Het probleem wordt vertaald naar de taal van de Finite Union Theorem (FUT), die computationeel equivalent is aan HT. Dit houdt in dat de kleuring van de verzameling van niet-lege eindige deelverzamelingen van $\mathbb{N}$, $P_{fin}(\mathbb{N})$, wordt onderzocht, waarbij gezocht wordt naar een oneindige bloksequentie $H$ waarvoor de verzameling van eindige unies $FU(H)$ monochroom is.
2. Towsner-bomen en Matching: De auteurs maken gebruik van de concepten "half-match" en "full-match" van Towsner. Een eindige verzameling $F$ half-matchen een oneindige bloksequentie $X$ als voor elke eindige unie $b \in FU(X)$ er een $a \in F$ bestaat waarvoor $f(a \cup b) = f(b)$. Een full-match vereist $f(a) = f(a \cup b) = f(b)$.
   • Zij construeren een "Towsner-sequentie", een geneste sequentie van half-matches die een boomstructuur induceert (de Towsner-boom).
   • Zij stellen vast dat voor een arithmetische kleuring $f$, een $f''$-berekenbare Towsner-sequentie bestaat.
3. Forcing-begrip: Er wordt een nieuw forcing-begrip gedefinieerd met behulp van "P-condities", die paren zijn van $(I, X)$ waarbij $I$ een eindige verzameling van bloksequenties is en $X$ een oneindige reservoir. Een conditie is "f-matching" als deze een specifieke extensie-eigenschap voldoet die gerelateerd is aan de kleuring.
4. Controle van de eerste sprong (First-Jump Control): De kerninnovatie is het ontwerp van een "forcing vraag" met specifieke definieerbaarheidseigenschappen. Dit maakt de constructie van een generieke filter mogelijk waarbij de resulterende oplossing $G$ een specifieke niet-arithmetische verzameling $C$ vermijdt. De forcing-relatie is ontworend om de eerste sprong van de oplossing te controleren, waardoor de oplossing binnen een specifieke arithmetische graad ten opzichte van de invoer blijft, terwijl de doel-kegel wordt vermeden.
5. Diagonalisatie: Om te garanderen dat $C \not\leq_T G$, worden de eisen $R^C_e: W^G_e \neq C$ vervuld. Door de forcing-vraag voor $\Sigma^0_1$ formules te analyseren, demonstreren zij dat men, voor elke niet-arithmetische verzameling $C$ en arithmetische kleuring, condities kan uitbreiden om $G$ te dwingen te verschillen van $C$ op een bepaald element.

Belangrijkste Bijdragen en Resultaten

1. Hoofdstelling (Kegelvermijding/Cone Avoidance): Het primaire resultaat (Hoofdstelling 1.5) stelt: Laat $C$ een verzameling zijn van een niet-arithmetische graad. Voor elke $\ell \geq 1$ en elke kleuring $f: \mathbb{N} \to \ell$ (of $P_{fin}(\mathbb{N}) \to \ell$) van arithmetische graad, bestaat er een oneindige verzameling $H$ zodanig dat $FS(H)$ $f$-monochroom is en $C \not\leq_T H$.

   • Corollary: Door $C = \emptyset^{(\omega)}$ te stellen, bewijzen de auteurs dat elke arithmetische instantie van de stelling van Hindman een oplossing heeft die $\emptyset^{(\omega)}$ niet berekent. Dit demonstreert dat de computationele bovengrens van $\emptyset^{(\omega)}$ niet optimaal is voor een enkele toepassing van de stelling van Hindman.

2. Beperkingen van Iteratie: De auteurs verduidelijken dat dit resultaat niet impliceert dat de stelling van Hindman zwakker is dan $\text{ACA}^+_0$ in de reverse mathematics. De kegelvermijding geldt voor Turing-reducibiliteit ($C \not\leq_T H$), maar niet noodzakelijkerwijs voor arithmetische reducibiliteit. Daarom kan de stelling niet geïtereerd worden om een $\omega$-model van de stelling van Hindman te bouwen dat $\emptyset^{(\omega)}$ uitsluit.

3. Eenvoudige Kleuringen: Het artikel onderzoekt beperkingen van HT tot "eenvoudige kleuringen" (kleuringen waarbij de kleur van een unie alleen afhangt van de kleuren van de componenten en hun relatieve posities).

   • Zij bewijzen dat de beperking van de Finite Union Theorem tot eenvoudige kleuringen equivalent is aan $\text{ACA}_0$ over $\text{RCA}_0$.
   • Zij tonen aan dat de specifieke kleuring die door Blass, Hirst en Simpson werd gebruikt om de ondergrens te bewijzen (gebaseerd op "zeer korte gaten"), een eenvoudige kleuring is.

4. Complexiteit van Towsner-bomen: De auteurs bewijzen (Propositie 2.24) dat voor de specifieke kleuring geconstrueerd door Blass, Hirst en Simpson, elke Towsner-sequentie $\emptyset'$ berekent. Dit suggereert dat hoewel Towsner-bomen krachtige instrumenten zijn, hun bestaan voor bepaalde berekenbare kleuringen inherent significante computationele kracht codeert, hoewel dit de existentie van andere bewijzen of full-matches die niet op dergelijke bomen rusten, niet uitsluit.

Betekenis
Dit artikel lost de vraag op of de $\emptyset^{(\omega)}$ bovengrens nauw aansluit bij een enkele toepassing van de stelling van Hindman. Door te bewijzen dat niet-arithmetische kegels vermeden kunnen worden, laten de auteurs zien dat de stelling van Hindman niet inherent de volledige kracht van de $\omega$-sprong vereist om een oplossing voor arithmetische inputs te produceren. Dit verfijnt het begrip van de computationele inhoud van de stelling, door het onderscheid te maken tussen de complexiteit die nodig is om een oplossing te vinden versus de complexiteit die nodig is om een oplossing te vinden die specifieke hoge graden berekent. Het werk overbrugt ook combinatorische bewijzen (van Towsner) met forcing-technieken om een precieze controle over de Turing-graden van de oplossingen te bereiken.