• aritmetica di Peano
• beta di Godel
• Esponenziale
• induzione
• Interpretazione
• Logica
• Teoria degli Insiemi Finiti
• Zermelo-Fraenkel

L’obiettivo di questa Tesi è di enunciare e dimostrare un risultato di Logica del 1°
Ordine intuitivamente noto ma piuttosto complesso da formalizzare:
"L’Aritmetica di Peano è equivalente alla Teoria degli Insiemi Finiti nel
senso della bi-interpretabilità."
Per raggiungere questo obiettivo, abbiamo suddiviso il lavoro in diversi capitoli in
modo da ordinare le idee:
• Nel primo capitolo formalizziamo il problema, occupandoci di definire il concetto di bi-interpretabilità tra teorie: intuitivamente, due teorie del 1° Ordine sono
bi-interpretabili se hanno la stessa potenza dimostrativa, cioé se ogni risultato
dimostrabile in una delle due può essere riformulato in maniera equivalente e
dimostrato anche nell’altra, e viceversa.
• Nel secondo capitolo, il più corposo, analizziamo nel dettaglio i problemi che
emergono per definire una Teoria degli Insiemi Finiti, denotata con F IN ed
in particolare cercheremo l’Assiomatizzazione migliore possibile per i nostri
scopi: un primo tentativo è quello di definire la Teoria degli Insiemi Finiti come
la teoria ottenuta eliminando l’assioma dell’infinito dalla teoria degli insiemi
di Zermelo-Fraenkel con Scelta (ZFC) e sostituendolo con la sua negazione.
Questo tentativo sembra funzionare, visto che definendo il concetto di insieme
finito tramite gli ordinali è possibile mostrare che ogni elemento di questa teoria
è un insieme finito. Tuttavia, assiomatizzando in questo modo la teoria, non
si riesce a dimostrare una proprietà fondamentale che ci servirà per ottenere
l’equivalenza con P A:
la classe degli ordinali finiti è in bigezione con la classe degli insiemi,
Un modo per risolvere questo problema è ad esempio quello di aggiungere un
nuovo assioma, detto Assioma di ∈-Induzione. Grazie a questo nuovo assioma,
che risulta essere indipendente dagli altri, possiamo dedurre alcuni degli assiomi
di ZFC, come ad esempio le Parti, la Fondazione e la Scelta.
• Nel terzo capitolo otteniamo un primo risultato parziale ma molto importante:
usando l’interpretazione di Ackermann e la sua inversa, costruiamo esplicitamente una bi-interpretazione tra la teoria FIN e l’Aritmetica Esponenziale, un’estensione di PA dotata di un nuovo simbolo di funzione binaria per
l’esponenziazione e di due assiomi che lo definiscano.
Il motivo per cui abbiamo introdotto questa estensione provvisoria è legato al
fatto che le Interpretazione di Ackermann traduce il simbolo di appartenenza
insiemistico con una formula aritmetica che sfrutta la rappresentazione in binario, dunque usa in modo massiccio le potenze di 2; è quindi comprensibile che
avere anche questa operazione nel linguaggio aritmetico faciliterà notevolmente
le cose.
• Nel quarto ed ultimo capitolo mostriamo che l’Aritmetica Esponenziale introdotta nel capitolo precedente è in realtà un estensione conservativa dell’Aritmetica di Peano, dunque bi-interpretabile con essa, ottenendo il nostro risultato
principale per transitività.
Per arrivare a mostrare questo, ci occupiamo di definire una formula Aritmetica
z = exp(x, y) (facendo uso della funzione β di Godel ¨ e delle sequenze finite)
che riesca a rimpiazzare il simbolo per l’esponenziazione anche in PA, cioé tale
che verifichi le proprietà induttive
∀x exp(x, 0) = 1 e ∀x, y exp(x, S(y)) = exp(x, y) · x.