Functional completeness and primitive positive decomposition of relations on finite domains

Sintesi Tecnica: Completezza Funzionale e Decomposizione Primitiva Positiva di Relazioni su Domini Finiti

Enunciato del Problema
Il saggio affronta il problema della decomposizione di relazioni ad alta arità in relazioni di arità inferiore, specificamente relazioni binarie, utilizzando formule primitive positive (ppf). Una formula primitiva positiva consiste in congiunzioni e quantificatori esistenziali applicati a predicati. Questo problema, noto come Tesi della Riduzione Relazionale (RRT), postula che le relazioni $n$-arie ($n \ge 2$) possano essere ridotte a relazioni binarie, sebbene non tutte le relazioni binarie si riducano a unarie.

Mentre l'analogo funzionale (Tesi della Riduzione Funzionale, FRT)—ovvero che le funzioni a $n$ ingressi si riducono a funzioni a 2 ingressi—è ben stabilito (tramite il lavoro di Post sulla logica multivalore e le funzioni di Sheffer), il caso relazionale su domini finiti è stato meno chiaro. Risultati precedenti erano sparsi, non costruttivi o basati sull'estensione del dominio (astrazione ipostatica), il che non è fattibile su domini finiti senza aggiungere elementi. Inoltre, è noto che la RRT fallisce sui domini Booleani (dove esistono relazioni ternarie irriducibili), ma le ragioni strutturali di questo fallimento e le condizioni per il successo su domini finiti generali richiedevano una spiegazione unificata ed elementare.

Metodologia
L'autore impiega un approccio costruttivo che collega la completezza funzionale alla decomposizione relazionale interpretando le relazioni come "funzioni parzialmente definite multivalore" (relativi). La metodologia procede in tre fasi principali:

1. Riduzione Relativa (da Relazioni a Ternarie):
   Il saggio tratta una relazione $n$-aria $R$ come un relativo con un argomento di uscita distinto. Essa decompone $R$ in una multifunzione e una relazione di dominio. Utilizzando i selettori di valore (funzioni che scelgono un valore dall'immagine della multifunzione), l'autore riduce la multifunzione a una funzione ordinaria $f(t, x_1, \dots, x_{n-1})$. Sfruttando la nota riduzione funzionale delle funzioni a $n$ ingressi in funzioni a 2 ingressi (tramite le forme normali disgiuntive canoniche di Post nelle logiche multivalore), il saggio dimostra che ogni relazione può essere decomposta in relazioni ternarie (grafici di funzioni a 2 ingressi) e relazioni di arità inferiore.

2. Esistenzializzazione delle Disgiunzioni (da Ternarie a Binarie):
   Per ridurre le relazioni ternarie a quelle binarie, il saggio introduce una costruzione per relazioni cofinite (relazioni il cui complemento è finito). Questo metodo è duale all'astrazione ipostatica. Invece di codificare le tuple in nuovi elementi, esso converte le disgiunzioni inerenti alla Forma Normale Congiuntiva Complementare (CCNF) di una relazione cofinita in quantificazioni esistenziali. Ciò viene ottenuto introducendo una variabile di indicizzazione e definendo specifici predicati binari che emulano la disgiunzione di "coliterali" unari. Questo passaggio è valido solo quando l'arità $n$ non supera la dimensione del dominio $|D|$, permettendo un'iniezione degli indici nel dominio.

3. Riduzione del Legame e Tesi di Peirce:
   Il saggio analizza la relazione tra composizione primitiva positiva e il "legame" originale di Peirce (composizione ristretta che coinvolge prodotti relativi e identificazione di variabili). Dimostra che per arità $n \ge 4$, la riducibilità pp e la riducibilità per legame sono equivalenti, a condizione che siano ammesse le "teridentità" ($I_3$). Tuttavia, per le relazioni ternarie, la riducibilità per legame è strettamente più debole della riducibilità pp.

Contributi Chiave e Risultati

• Teorema 2 (Riduzione Relativa): Su qualsiasi dominio, ogni relazione $n$-aria si decompone in una composizione di una funzione $f: D^n \to D$ e una relazione di dominio. Fondamentalmente, se esiste un insieme funzionalmente completo di funzioni a 2 ingressi, ogni relazione può essere decomposta nei grafici delle funzioni di tale insieme. Ciò implica che su qualsiasi dominio finito, ogni relazione $n$-aria ($n \ge 4$) è riducibile a relazioni ternarie.
• Corollario 1 (Relazioni di Sheffer): Su qualsiasi dominio finito, esistono relazioni ternarie (grafici di funzioni di Sheffer) che da sole formano un sistema primitivamente positivo completo. Questo stabilisce l'esistenza di "relazioni di Sheffer" per domini non booleani.
• Teorema 3 (Riduzione Binaria delle Relazioni Cofinite): Per domini con $|D| \ge 3$, qualsiasi relazione $n$-aria cofinita (dove $3 \le n \le |D|$) si riduce a relazioni binarie. Questa costruzione si basa sulla conversione delle disgiunzioni di coliterali in quantificazioni esistenziali su predicati binari.
• Teorema 4 (Irriducibilità sui Domini Booleani): Il saggio fornisce una prova elementare che la relazione ternaria $\neg I_3$ (il complemento dell'identità ternaria) è irriducibile a relazioni binarie sui domini booleani. Ciò viene dimostrato mostrando che $\neg I_3$ non è "bijuntiva" (non può essere espressa come una 2CNF) e poiché la composizione pp preserva la bijuntività, essa non può essere ridotta a relazioni binarie (che sono tutte bijuntive).
• Teoremi 5 & 6 (Legame vs. Riducibilità pp): Il saggio chiarisce che per $n \ge 4$, la riducibilità pp è equivalente alla riducibilità per legame (usando le teridentità). Tuttavia, per le relazioni ternarie, la riducibilità per legame è strettamente più debole; specificamente, $I_3$ è legamente irriducibile su qualsiasi dominio con almeno due elementi.

Significato e Rivendicazioni
Il saggio sostiene di fornire una "prova uniforme" della tesi di riduzione di Peirce sui domini finiti, stabilendo una connessione diretta ed elementare tra la tesi di riduzione funzionale (FRT) e la tesi di riduzione relazionale (RRT).

• Unificazione: Risolve il distacco tra completezza funzionale e relazionale mostrando che i grafici dei sistemi funzionalmente completi formano sistemi relazionali pp-completi.
• Costruttività: A differenza delle prove precedenti non costruttive che si basavano su connessioni di Galois o estensioni del dominio, questa costruzione è computazionalmente efficace e si basa su metodi ben sviluppati di decomposizione funzionale (logiche di Post).
• Spiegazione del Fallimento: La costruzione elucida il perché la RRT fallisce sui domini booleani: l'impossibilità di convertire disgiunzioni di ordine superiore in quantificazioni esistenziali a causa di un numero insufficiente di elementi del dominio (specificamente, la mancanza di un'iniezione per gli indici quando $n > |D|$).
• Nuovi Concetti: Introduce il concetto di "relazioni di Sheffer" e fornisce una nuova prospettiva sull' "astrazione ipostatica" come processo duale alla "esistenzializzazione delle disgiunzioni".

L'autore nota con modestia che, sebbene la costruzione spieghi la riducibilità delle relazioni a quelle ternarie e (per i casi cofiniti) binarie, essa non fornisce un analogo generale dei criteri di Post o Slupecki per la completezza relazionale su domini finiti arbitrari, né caratterizza completamente i cocloni massimali. Il saggio lascia aperta la questione se esistano relazioni di Sheffer binarie su domini non booleani.