Università Roma Tre

Logica ed Aritmetica: l'incompletezza

Parte 1: Decidibilità e risultati fondamentali di teoria della ricorsività. Funzioni ricorsive primitive e funzioni elementari: definizioni ed esempi, codifica elementare delle successioni finite di interi, caratterizzazione alternativa dell’insieme delle funzioni elementari. La funzione di Ackermann e le funzioni (parziali) ricorsive. Gerarchia aritmetica e rappresentazione (in N) delle funzioni ricorsive. Aritmetizzazione della sintassi: codifica dei termini e delle formula, la soddisfacibilità in N delle formule Delta è elementare, codifica dei sequenti e delle derivazioni. I teoremi fondamentali della teoria della ricorsività. Decidibilità, semi-decidibilità, indecidibilità.

Parte 2: L’aritmetica di Peano. Gli assiomi di Peano e gli assiomi di Peano al primo ordine. I modelli dell'aritmetica di Peano (al primo ordine). Le funzioni rappresentabili nell'aritmetica di Peano (al primo ordine). Incompletezza ed indecidibilità: teorema di indecidibilità di Church, punto fisso, primo teorema di incompletezza di Gödel, secondo teorema di incompletezza di Gödel, osservazioni conclusive sull’incompletezza, cenni su incompletezza e logica del secondo ordine.

V. Michele Abrusci e Lorenzo Tortora de Falco, Logica. Vol. 2 Incompletezza, teoria assiomatica degli insiemi, Springer, 2018