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

Technische Zusammenfassung: „Hindman's Theorem kodiert $\emptyset^{(\omega)}$ nicht in einer einzelnen Anwendung“

Problemstellung
Die Arbeit befasst sich mit der computertheoretischen Komplexität des Satzes von Hindman (HT), insbesondere hinsichtlich der Stärke der Lösungen im Verhältnis zur Eingabefärbung. Der Satz von Hindman besagt, dass es für jede endliche Färbung der natürlichen Zahlen $\mathbb{N}$ eine unendliche Menge $H$ gibt, sodass die Menge aller nichtleeren endlichen Summen verschiedener Elemente von $H$ (bezeichnet als $FS(H)$) monochrom ist.

Vorherige Arbeiten etablierten die folgenden Schranken:

1. Obere Schranke: Blass, Hirst und Simpson (1987) bewiesen, dass für jede berechenbare Färbung eine Lösung existiert, die aus dem $\omega$-Sprung der leeren Menge, $\emptyset^{(\omega)}$, berechenbar ist.
2. Untere Schranke: Dieselben Autoren bewiesen, dass es für bestimmte berechenbare Färbungen eine Lösung gibt, die die Halte Menge $\emptyset'$ berechnet. Später verbesserte Liao (2026) dies, indem er zeigte, dass für einige berechenbare Färbungen keine $\Pi^0_3$-Lösung existiert.

Die zentrale offene Frage, die diese Arbeit adressiert, ist, ob die obere Schranke von $\emptyset^{(\omega)}$ für eine einzelne Anwendung des Satzes optimal ist. Konkret: Besitzt jede arithmetische Instanz des Satzes von Hindman eine Lösung, die $\emptyset^{(\omega)}$ nicht berechnet?

Methodik
Die Autoren verwenden eine Verzweigungstechnik (Forcing), die aus Towsners kombinatorischem Beweis des Satzes von Hindman adaptiert wurde. Die Methodik umfasst folgende Komponenten:

1. Reformulierung: Das Problem wird in die Sprache des Finite Union Theorems (FUT) übersetzt, welches berechenbar äquivalent zu HT ist. Dies beinhaltet das Färben der Menge der nichtleeren endlichen Teilmengen von $\mathbb{N}$, $P_{fin}(\mathbb{N})$, und die Suche nach einer unendlichen Blocksequenz $H$, sodass die Menge der endlichen Vereinigungen $FU(H)$ monochrom ist.
2. Towsner-Bäume und Matching: Die Autoren nutzen Towsners Konzepte des „Half-Match“ und „Full-Match“. Eine endliche Menge $F$ half-matched eine unendliche Blocksequenz $X$, wenn für jede endliche Vereinigung $b \in FU(X)$ ein $a \in F$ existiert, sodass $f(a \cup b) = f(b)$. Ein Full-Match erfordert $f(a) = f(a \cup b) = f(b)$.
   • Sie konstruieren eine „Towsner-Sequenz“, eine verschachtelte Sequenz von Half-Matches, die eine Baumstruktur induziert (den Towsner-Baum).
   • Sie stellen fest, dass für eine arithmetische Färbung $f$ eine $f''$-berechenbare Towsner-Sequenz existiert.
3. Forcing-Konzept: Ein neues Konzept des Forcing wird unter Verwendung von „P-Bedingungen“ definiert, bei denen es sich um Paare $(I, X)$ handelt, wobei $I$ eine endliche Menge von Blocksequenzen und $X$ ein unendlicher Reservoir ist. Eine Bedingung ist „f-matching“, wenn sie eine spezifische Erweiterungseigenschaft in Bezug auf die Färbung erfüllt.
4. Kontrolle des ersten Sprungs (First-Jump Control): Die zentrale Innovation ist das Design einer „Forcing-Frage“ mit spezifischen Definierbarkeitseigenschaften. Dies ermöglicht die Konstruktion eines generischen Filters, bei dem die resultierende Lösung $G$ eine bestimmte nicht-arithmetische Menge $C$ nicht berechnet. Die Forcing-Relation ist so konzipiert, dass sie den ersten Sprung der Lösung kontrolliert, um sicherzustellen, dass die Lösung innerhalb eines spezifischen arithmetischen Grades relativ zur Eingabe bleibt und gleichzeitig den Zielkegel vermeidet.
5. Diagonalisierung: Um sicherzustellen, dass $C \not\leq_T G$, erfüllen die Autoren die Anforderungen $R^C_e: W^G_e \neq C$. Durch die Analyse der Forcing-Frage für $\Sigma^0_1$-Formeln zeigen sie, dass man für jede nicht-arithmetische Menge $C$ und jede arithmetische Färbung Bedingungen erweitern kann, um zu erzwingen, dass $G$ auf einem Element von $C$ abweicht.

Wesentliche Beiträge und Ergebnisse

1. Hauptsatz (Kegelvermeidung/Cone Avoidance): Das primäre Ergebnis (Hauptsatz 1.5) besagt: Sei $C$ eine Menge nicht-arithmetischer Gradstufe. Für jede $\ell \geq 1$ und jede Färbung $f: \mathbb{N} \to \ell$ (oder $P_{fin}(\mathbb{N}) \to \ell$) arithmetischer Gradstufe existiert eine unendliche Menge $H$, sodass $FS(H)$ $f$-monochrom ist und $C \not\leq_T H$.

   • Korollar: Durch Setzung von $C = \emptyset^{(\omega)}$ beweisen die Autoren, dass jede arithmetische Instanz des Satzes von Hindman eine Lösung besitzt, die $\emptyset^{(\omega)}$ nicht berechnet. Dies zeigt, dass die computertheoretische obere Schranke von $\emptyset^{(\omega)}$ nicht optimal für eine einzelne Anwendung des Satzes von Hindman ist.

2. Limitierungen der Iteration: Die Autoren klären, dass dieses Ergebnis nicht impliziert, dass der Satz von Hindman schwächer als $\text{ACA}^+_0$ in der Reverse Mathematik ist. Die Kegelvermeidung gilt für die Turing-Reduzierbarkeit ($C \not\leq_T H$), aber nicht notwendigerweise für die arithmetische Reduzierbarkeit. Daher kann der Satz nicht iteriert werden, um ein $\omega$-Modell des Satzes von Hindman aufzubauen, das $\emptyset^{(\omega)}$ ausschließt.

3. Einfache Färbungen: Das Paper untersucht die Einschränkung von HT auf „einfache Färbungen“ (Färbungen, bei denen die Farbe einer Vereinigung nur von den Farben der Komponenten und deren relativer Position abhängt).

   • Sie beweisen, dass die Einschränkung des Finite Union Theorems auf einfache Färbungen über $\text{RCA}_0$ äquivalent zu $\text{ACA}_0$ ist.
   • Sie zeigen, dass die spezifische Färbung, die von Blass, Hirst und Simpson verwendet wurde, um die untere Schranke zu beweisen, eine einfache Färbung ist.

4. Komplexität von Towsner-Bäumen: Die Autoren beweisen (Proposition 2.24), dass für die spezifische Färbung, die von Blass, Hirst und Simpson konstruiert wurde, jede Towsner-Sequenz $\emptyset'$ berechnet. Dies deutet darauf hin, dass, obwohl Towsner-Bäume ein mächtiges Werkzeug sind, ihre Existenz für bestimmte berechenbare Färbungen inhärent signifikante computationale Kraft kodiert, was jedoch die Existenz anderer Beweise oder Full-Matches nicht ausschließt, die nicht auf diesen Bäumen beruhen.

Bedeutung
Das Paper löst die Frage, ob die $\emptyset^{(\omega)}$-obere Schranke für einzelne Anwendungen des Satzes von Hindman eng gefasst ist. Durch den Beweis, dass nicht-arithmetische Kegel vermieden werden können, zeigen die Autoren, dass der Satz nicht inhärent die volle Stärke des $\omega$-Sprungs benötigt, um eine Lösung für arithmetische Eingaben zu erzeugen. Dies präzisiert das Verständnis des computationalen Inhalts des Satzes und unterscheidet zwischen der Komplexität, die zur Findung einer Lösung erforderlich ist, und der Komplexität, die erforderlich ist, um eine Lösung zu finden, die spezifische hohe Grade berechnet. Die Arbeit schlägt eine Brücke zwischen kombinatorischen Beweisen (Towsner) und Forcing-Techniken, um eine präzise Kontrolle über die Turing-Grade der Lösungen zu erreichen.