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

Sintesi Tecnica: "Il teorema di Hindman non codifica $\emptyset^{(\omega)}$ in un'unica applicazione"

Enunciato del Problema
L'articolo affronta la complessità della teoria della computabilità del Teorema di Hindman (HT), specificamente riguardo alla forza delle soluzioni che esso produce rispetto alla colorazione di input. Il Teorema di Hindman afferma che per ogni colorazione finita dei numeri naturali $\mathbb{N}$, esiste un insieme infinito $H$ tale che l'insieme di tutte le somme finite di elementi distinti di $H$ (denotato con $FS(H)$) è monocromatico.

Il lavoro precedente ha stabilito i seguenti limiti:

1. Limite Superiore: Blass, Hirst e Simpson (1987) hanno dimostrato che per ogni colorazione computabile, esiste una soluzione computabile dal salto $\omega$ dell'insieme vuoto, $\emptyset^{(\omega)}$.
2. Limite Inferiore: Gli stessi autori hanno dimostrato che esiste una colorazione computabile per la quale ogni soluzione computa l'insieme della fermata $\emptyset'$. Successivamente, Liao (2026) ha migliorato questo risultato mostrando che per alcune colorazioni computabili, non esiste una soluzione $\Pi^0_3$.

La questione aperta centrale affrontata da questo articolo è se il limite superiore di $\emptyset^{(\omega)}$ sia ottimale per una singola applicazione del teorema. Nello specifico, ogni istanza aritmetica del Teorema di Hindman ammette una soluzione che non computa $\emptyset^{(\omega)}$?

Metodologia
Gli autori utilizzano una tecnica di forcing adattata dalla prova combinatoria di Hindman di Towsner. La metodologia comprende i seguenti componenti:

1. Riformulazione: Il problema viene tradotto nel linguaggio del Teorema delle Unioni Finite (FUT), che è computabilmente equivalente a HT. Ciò comporta la colorazione dell'insieme delle sottoinsiemi finiti non vuoti di $\mathbb{N}$, $P_{fin}(\mathbb{N})$, e la ricerca di una sequenza a blocchi infinita $H$ tale che l'insieme delle unioni finite $FU(H)$ sia monocromatico.
2. Alberi di Towsner e Matching: Gli autori utilizzano i concetti di "half-match" (mezzo-corrispondenza) e "full-match" (corrispondenza completa) di Towsner. Un insieme finito $F$ half-matches una sequenza a blocchi infinita $X$ se per ogni unione finita $b \in FU(X)$, esiste un $a \in F$ tale che $f(a \cup b) = f(b)$. Un full-match richiede che $f(a) = f(a \cup b) = f(b)$.
   • Costruiscono una "sequenza di Towsner", una sequenza nidificata di half-matches che induce una struttura ad albero (l'albero di Towsner).
   • Stabiliscono che per una colorazione aritmetica $f$, esiste una sequenza di Towsner computabile da $f''$.
3. Nozione di Forcing: Viene definita una nuova nozione di forcing utilizzando "condizioni-P", che sono coppie $(I, X)$ dove $I$ è un insieme finito di sequenze a blocchi e $X$ è un serbatoio infinito. Una condizione è "f-matching" se soddisfa una specifica proprietà di estensione relativa alla colorazione.
4. Controllo del Primo Salto (First-Jump Control): L'innovazione centrale è la progettazione di una "domanda di forcing" con specifiche proprietà di definibilità. Ciò consente la costruzione di un filtro generico in cui la soluzione $G$ risultante evita di computare un particolare insieme non aritmetico $C$. La relazione di forcing è progettata per controllare il primo salto della soluzione, garantendo che la soluzione rimanga entro un grado aritmetico specifico rispetto all'input, evitando al contempo il cono bersaglio.
5. Diagonalizzazione: Per garantire che $C \not\leq_T G$, si soddisfano i requisiti $R^C_e: W^G_e \neq C$. Analizzando la domanda di forcing per formule $\Sigma^0_1$, gli autori dimostrano che per qualsiasi insieme non aritmetico $C$ e colorazione aritmetica, è possibile estendere le condizioni per forzare $G$ a differire da $C su un elemento.

Contributi Chiave e Risultati

1. Teorema Principale (Evitamento del Cono): Il risultato principale (Teorema Principale 1.5) afferma: Sia $C$ un insieme di grado non aritmetico. Per ogni $\ell \geq 1$ e ogni colorazione $f: \mathbb{N} \to \ell$ (o $P_{fin}(\mathbb{N}) \to \ell$) di grado aritmetico, esiste un insieme infinito $H$ tale che $FS(H)$è$f$-monocromatico e $C \not\leq_T H$.

   • Corollario: Impostando $C = \emptyset^{(\omega)}$, gli autori dimostrano che ogni istanza aritmetica del Teorema di Hindman ammette una soluzione che non computa $\emptyset^{(\omega)}$. Ciò dimostra che il limite superiore computazionale di $\emptyset^{(\omega)}$ non è ottimale per una singola applicazione di Hindman.

2. Limitazioni dell'Iterazione: Gli autori chiariscono che questo risultato non implica che il Teorema di Hindman sia più debole di $\text{ACA}^0_0$ nella matematica inversa. L'evitamento del cono vale per la riducibilità di Turing ($C \not\leq_T H$) ma non necessariamente per la riducibilità aritmetica. Pertanto, il teorema non può essere iterato per costruire un modello-$\omega$ di Hindman che escluda $\emptyset^{(\omega)}$.

3. Colorazioni Semplici: Il documento investiga le restrizioni di HT a "colorazioni semplici" (colorazioni in cui il colore di un'unione dipende solo dai colori dei componenti e dalle loro posizioni relative).

   • Dimostrano che la restrizione del Teorema delle Unioni Finite alle colorazioni semplici è equivalente a $\text{ACA}_0$ su $\text{RCA}_0$.
   • Mostrano che la colorazione specifica utilizzata da Blass, Hirst e Simpson per provare il limite inferiore è una colorazione semplice.

4. Complessità degli Alberi di Towsner: Gli autori dimostrano (Proposizione 2.24) che per la specifica colorazione costruita da Blass, Hirst e Simpson, ogni sequenza di Towsner computa $\emptyset'$. Ciò suggerisce che, sebbene gli alberi di Towsner siano uno strumento potente, la loro esistenza per certe colorazioni computabili codifica intrinsecamente un potere computazionale significativo, sebbene ciò non escluda l'esistenza di altre prove o full-matches che non dipendono da tali alberi.

Significato
Il lavoro risolve la questione se il limite superiore $\emptyset^{(\omega)}$ sia stretto per le singole applicazioni del Teorema di Hindman. Provando che i coni non aritmetici possono essere evitati, gli autori mostrano che il teorema non richiede intrinsecamente la piena forza del salto $\omega$ per produrre una soluzione per input aritmetici. Questo affina la comprensione del contenuto computazionale del teorema, distinguendo tra la complessità richiesta per trovare una soluzione e la complessità richiesta per trovare una soluzione che computi specifici insiemi ad alto grado. Il lavoro collega anche le prove combinatorie (di Towsner) con le tecniche di forcing per ottenere un controllo preciso sui gradi di Turing delle soluzioni.