Questo lavoro di tesi è incentrato sulla traducibilità di enunciati della logica del primo ordine in uguaglianze dell'algebra delle relazioni diadiche e vuole esplorare i limiti che si oppongono a questa opera di traduzione.
La logica predicativa del primo ordine, sviluppata nei Principia Mathematica di Whitehead-Russell, si è affermata a causa della sua grande espressività e dell'uso amichevole, mentre l'altro formalismo, dovuto a C. Peirce e che giunse a stabilità con il lavoro di Schroeder, cfr. [15], è caduto per lungo tempo in dimenticanza nel campo della logica. Ma l'influsso dell'algebra mappale è riconoscibile negli attuali linguaggi per database relazionali e in un gran numero di linguaggi di rappresentazione, chiamati linguaggi tassonomici o logiche di descrizione.
Il formalismo del calcolo mappale sta suscitando nuovo interesse nell'ambito della ricerca poiché ha il vantaggio, rispetto alla logica predicativa, di essere privo di quantificatori, di variabili e di connettivi logici. Proprio questa sua semplicità è la caratteristica che più interessa, poiché il processo deduttivo nella logica mappale diventa simile a quello di svolgere semplificazioni algebriche, senza dover nemmeno istanziare variabili.
E ci attrae anche l'idea che esso possa fornire un mezzo di calcolo almeno equivalente a quello della logica del primo ordine.
Attualmente ci sono degli algoritmi che eseguono la traduzione tra i due formalismi, ma lo fanno in maniera conservativa, cioè laddove è possibile.
Infatti, non tutti le espressioni costruibili in L, la logica del primo ordine, hanno un equivalente in L´ , simbolo con cui viene indicata l'algebra mappale: i due formalismi non sono equipollenti. Per la ricerca di una, seppur parziale, equipollenza tra L ed L´ , viene introdotto il formalismo L+, ottenuto estendendo L con una ulteriore definizione di formula atomica; sia L che L´ sono sottoformalismi di L+, ma L gli è equipollente, mentre L´ no. Quindi, è ora con L+ che verrà confrontato L´ .
Relativamente all'equipollenza espressiva, da lungo tempo è noto che ci sono enunciati di L+ che non hanno un equivalente in L´ ; il risultato è dovuto ad A. Korselt. Anche l'equipollenza relativa al potere dimostrativo ha un risultato negativo. Inoltre, L´ è incompleto rispetto alla sua semantica: l'insieme degli enunciati in esso derivabili è un sottoinsieme degli enunciati che sono veri in L´ ; quindi risulta più povero rispetto agli altri due formalismi sia come potere espressivo che come potere dimostrativo. Quello che si vuole capire è se ci sia un ambito in cui L´ possa competere, in termini di esprimibilità, con L.
Osservando gli enunciati di L che trovavano un equivalente in L´ , si è constatato che essi contenevano al più tre variabili distinte, cfr [2]. Quindi è sembrato plausibile che un sottoformalismo di L equipollente ad L´ potesse essere costruito a partire da L ponendo l'unica restrizione sul numero delle variabili, appunto tre. Tale formalismo, L3, risulta essere effettivamente equipollente ad L´ , per cui il problema dell'esprimibilità in L´ si riconduce a quello dell'esprimibilità in L3.
Nel suo articolo del 1941, cfr. [9], Tarski pose la seguente domanda: "C'è un criterio che possa consentire di decidere in ogni caso particolare se un enunciato è esprimibile nel calcolo relazionale?". Nella sua tesi di PhD, Kwatinetz risponde negativamente a questa domanda, cfr. [2], dimostrando prima che Eq ( Se ( Lk ) ), cioè l'insieme di enunciati di L che hanno un equivalente in Lk, non è ricorsivo per alcun k Î N \ { 0} , e, come corollario di questo risultato, che Eq ( L´ ) non è ricorsivo, coincidendo con Eq ( Se ( L3 ) ). Quest'ultimo risultato è dovuto a Tarski. Successivamente, Kwatinetz propone una tecnica per effettuare dimostrazioni di non k-rappresentabilità, che trae origine nella teoria dei giochi di Ehrenfucht-Fraissé. Essa si basa essenzialmente sui due seguenti teoremi:
Teorema 5.2. Sia k Î N \ { 0} e siano  ed Á due interpretazioni del linguaggio L che soddisfano le seguenti condizioni:
(i) Â , Á Î Homg ( k ),
(ii) Â ed Á sono diagramma equivalenti in k + 1 variabili.
Allora " q Î Se ( Lk+1 ), Â | = q Û Á | = q .
Teorema 5.3. Sia q Î Se ( L ) e k Î N \ { 0} . Affinché q Î Eq ( Se ( Lk ) ), cioè q sia k-rappresentabile, è necessario e sufficiente che, per ogni  ed Á ,
coppia di interpretazioni del linguaggio L k-equivalenti, Â | = q Þ Á | = q .
Il teorema 5.3 mette in relazione la k-rappresentabilità di un enunciato del linguaggio L, l'enunciato q Î Se ( L ), con l'esistenza di due interpretazioni del linguaggio, k-equivalenti, tali che se la prima modella q anche la seconda lo modella. Questo teorema viene utilizzato costruendo due interpretazioni k-equivalenti, ma tali che la prima modella l'enunciato e la seconda no; in questo modo si conclude la non k-rappresentabilità di q .
La questione della k-equivalenza delle interpretazioni, cioè il fatto che esse modellino entrambe lo stesso sottoinsieme di enunciati in k variabili, viene risolta con il teorema 5.2. La k-equivalenza si esprime con la seguente relazione:
Th ( Á ) Ç Se ( Lk ) = Th ( Â ) Ç Se ( Lk ).
Attraverso il teorema 5.2, si dimostra che l'insieme degli enunciati modellati dalle due interpretazioni, limitatamente a quelli in k variabili, è lo stesso. Con questo risultato, anche gli insiemi individuati dalla precedente relazione sono uguali.
Le difficoltà principali di questa tecnica dimostrativa sono contenute proprio nella dimostrazione delle ipotesi del teorema 5.2. Infatti, quando il numero di predicati e di variabili diventa elevato, già tre per le variabili, c'è una esplosione combinatoria dei casi da esaminare difficile da gestire.
Utilizzando questa tecnica, in questa tesi si sono costruite dimostrazioni di non k-rappresentabilità per alcuni enunciati della logica del primo ordine; per uno di essi tale risultato non era stato dimostrato.
Sono stati affrontati tre casi: il primo è la non L2-rappresentabilità dell'enunciato che assiomatizza la teoria delle relazioni di equivalenza; il secondo riguarda la non L3-rappresentabilità dell'enunciato che esprime la proprietà dell'unione insiemistica; il terzo la non L3-rappresentabilità della proprietà dell'aggiunta di un elemento ad un insieme.
Il primo esempio è stato affrontato per comprendere il comportamento base della tecnica, data la sua semplicità; il coinvolgimento di due sole variabili e di un solo predicato, oltre quello di uguaglianza, rende la verifica delle ipotesi di 2-equivalenza abbastanza semplice, oltre alla possibilità di costruire semplicemente due interpretazioni che godano di tale proprietà.
Del secondo è già noto che esso non è esprimibile in tre variabili, tale dimostrazione viene data da Kwatinetz, cfr. [2]; poiché viene effettuata mostrando che l'enunciato si riconduce ad un altro per cui la non 3-rappresentabilità è stata precedentemente provata, e non ricorrendo esplicitamente alla tecnica, è sembrato interessante costruirne una per esempio. Per l'ultimo non c'è un risultato in questo senso.
Kwatinetz presenta una dimostrazione per l'assioma dell'aggiunta, ma questa sembra essere inadeguata allo scopo; in particolare, i domini delle due interpretazioni che egli sceglie non sono tali da consentire l'annidamento di insiemi ottenibile con tale proprietà. Inoltre, nel Tarski-Givant, cfr. [1], la 3-rappresentabilità dell'assioma viene ancora considerata come dubbia.
Infine, nel capitolo 4 vengono proposti esempi di traduzioni effettuabili nell'algebra mappale: gli assiomi della geometria elementare e un gruppo di postulati della logica temporale. Il primo caso è interessante perché presenta il problema di trattare relazioni non binarie e, inoltre, formule che contengono più di tre variabili.
Il problema viene risolto ricorrendo all'uso delle quasi proiezioni coniugate che consentono, una volta accorpate due variabili in un unico nuovo oggetto, di riottenerne entrambe le componenti. Poter utilizzare le quasi proiezioni coniugate evita di doversi preoccupare del fatto se una formula con più di tre variabili sia logicamente equivalente ad una con tre.
Il secondo esempio introduce quantificazioni anche sui predicati: si tratta di formule del secondo ordine. Anche in questo caso la traduzione è possibile a patto di considerare il predicato quantificato come un segnaposto all'interno della espressione mappale ottenuta, una variabile da poter rimpiazzare con un qualsiasi predicato binario.