L’insegnamento di Teoremi sulla Logica 2 rientra nell’ambito delle attività formative caratterizzanti del Cds in Scienze Filosofiche. Alla fine del corso lo studente avrà acquisito una buona conoscenza della teoria della ricorsività ed avrà compreso i legami tra logica ed aritmetica attraverso lo studio delle dimostrazioni dei teoremi di incompletezza di Godel.
scheda docente
materiale didattico
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.
Programma
Logica ed Aritmetica: l'incompletezzaParte 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.
Testi Adottati
V. Michele Abrusci e Lorenzo Tortora de Falco, Logica. Vol. 2 Incompletezza, teoria assiomatica degli insiemi, Springer, 2018Modalità Erogazione
Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata.Modalità Valutazione
Esame orale, di durata variabile, in media tra 45 e 60 minuti.