Che cos’è la logica del primo ordine? La logica del primo ordine (o logica dei predicati del primo ordine, LPO) è un sistema formale che estende la logica proposizionale introducendo:

• quantificatori: universale (∀, “per ogni”) ed esistenziale (∃, “esiste”);
• predicati e relazioni: espressioni come P(x), R(x,y) che attribuiscono proprietà o relazioni a oggetti;
• variabili individuali: x, y, z che rappresentano elementi di un dominio di discorso;
• funzioni: che mappano oggetti su altri oggetti;
• costanti individuali: nomi di oggetti specifici.

Si chiama “del primo ordine” perché i quantificatori si applicano solo a variabili individuali (oggetti del dominio), non a predicati o insiemi di oggetti — questo la distingue dalla logica del secondo ordine, dove si può quantificare anche su proprietà o relazioni (“per ogni proprietà P…”).

La sintassi è costituita da un linguaggio formale con regole precise di formazione delle formule (ben formate, wff), mentre la semantica è definita tramite strutture (o modelli): un dominio non vuoto più un’interpretazione di predicati, funzioni e costanti. Vediamo il contributo di Gödel.

Kurt Gödel (1906-1978) ha prodotto sulla logica del primo ordine due risultati di portata storica, spesso confusi tra loro, ma profondamente diversi.

1. Il Teorema di Completezza (1929-1930, tesi di dottorato).

Nella sua tesi di dottorato all’Università di Vienna (1929, pubblicata nel 1930), Gödel dimostrò il Teorema di Completezza della logica del primo ordine: se una formula è logicamente valida (vera in tutti i modelli), allora è dimostrabile all’interno di un sistema deduttivo assiomatico per la logica del primo ordine. In termini equivalenti: ogni insieme di formule sintatticamente coerente (non contraddittorio) ha un modello (è semanticamente soddisfacibile). Questo risultato stabilisce una perfetta corrispondenza tra:

• sintassi: ciò che è dimostrabile tramite regole di inferenza (⊢);
• semantica: ciò che è vero in ogni interpretazione possibile (⊨).

In simboli: ⊨φ se e solo se ⊢φ. Questo è un risultato positivo e rassicurante: la logica del primo ordine è “ben comportata”. Ogni verità logica del primo ordine è, in linea di principio, raggiungibile con un procedimento deduttivo meccanico (anche se il procedimento di ricerca della dimostrazione non è necessariamente decidibile in tempo finito garantito — la LPO è infatti solo semi-decidibile).

2. I Teoremi di Incompletezza (1931).

Appena un anno dopo, con l’articolo “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” (1931), Gödel dimostrò un risultato apparentemente contrario in spirito, ma riguardante non la logica del primo ordine in sé, quanto i sistemi formali che la utilizzano per assiomatizzare l’aritmetica (come i Principia Mathematica di Russell e Whitehead, o la teoria degli insiemi di Zermelo-Fraenkel).

Primo teorema di incompletezza: qualsiasi sistema formale coerente, espresso in logica del primo ordine, sufficientemente potente da codificare l’aritmetica di base (i numeri naturali con addizione e moltiplicazione), contiene enunciati che sono veri, ma non dimostrabili all’interno del sistema stesso.

Secondo teorema di incompletezza: un tale sistema, se coerente, non può dimostrare la propria coerenza usando solo i propri assiomi. Come si conciliano i due risultati? Non c’è contraddizione, ma una distinzione cruciale:

	Completezza	Incompletezza
Riguarda	La logica del primo ordine pura (le sue regole di inferenza)	Sistemi specifici costruiti sopra la logica del primo ordine (aritmetica, teoria degli insiemi)
Cosa dice	Ogni verità logica è dimostrabile	Non ogni verità aritmetica è dimostrabile in un sistema dato
Natura	Proprietà del linguaggio logico stesso	Proprietà dei sistemi che aggiungono assiomi extra-logici (come gli assiomi di Peano)

In altre parole: la logica del primo ordine come strumento deduttivo puro è completa (ogni tautologia logica è dimostrabile). Ma appena la si usa per costruire teorie matematiche specifiche con assiomi che parlano di numeri, insiemi, ecc., emergono limiti intrinseci — non della logica, ma della possibilità di catturare tutta la verità matematica in un unico sistema assiomatico coerente e ricorsivamente enumerabile. Perché questi risultati furono rivoluzionari? Prima di Gödel, il programma di Hilbert puntava a fondare tutta la matematica su un sistema formale completo, coerente e decidibile. I risultati di Gödel:

• confermarono che la logica del primo ordine stessa è ben fondata (completezza);
• ma dimostrarono che nessun sistema assiomatico sufficientemente ricco (come l’aritmetica di Peano) può essere sia completo che dimostrabilmente coerente al proprio interno.

Questo segnò la fine delle ambizioni più forti del formalismo hilbertiano e apri la strada alla moderna teoria della computabilità (Church, Turing) e alla metamatematica contemporanea.

Va menzionato anche il contributo di Gödel al problema della decidibilità: insieme ai lavori di Church e Turing, si stabilì che la logica del primo ordine è indecidibile nel caso generale (problema di Entscheidung) — non esiste un algoritmo che, per ogni formula, determini in tempo finito se essa sia valida o meno — pur restando semi-decidibile (se una formula è valida, esiste una procedura che lo dimostra in tempo finito; se non lo è, la procedura potrebbe non terminare mai).