Università Roma Tre

Verso la teoria dei modelli: alcune conseguenze del teorema di compattezza

Dimostrazione del teorema di compattezza per linguaggi di cardinalità qualsiasi. Linguaggi con uguaglianza. Il teorema di compattezza per i linguaggi con uguaglianza. Correttezza e completezza per i linguaggi con uguaglianza. Il teorema di L"owenheim-Skolem per i linguaggi con uguaglianza (numerabili). Limiti espressivi del linguaggio del primo ordine. Equivalenza elementare, sottostrutture, sottostrutture elementari. Isomorfismo ed equivalenza elementare. La nozione di sottostruttura. Sottostrutture elementari e diagrammi. I teoremi di preservazione. Generalizzazioni del teorema di L"owenheim-Skolem. Completezza di una teoria.

Logica ed Aritmetica: l'incompletezza

Decidibilità e risultati fondamentali di teoria della ricorsività: funzioni ricorsive primitive e funzioni elementari, la funzione di Ackermann e le funzioni (parziali) ricorsive, gerarchia aritmetica e rappresentazione (in N) delle funzioni ricorsive, aritmetizzazione della sintassi, teoremi fondamentali della teoria della ricorsività, decidibilità, semi-decidibilità, indecidibilità.

L'aritmetica di Peano: gli assiomi di Peano, i modelli dell'aritmetica di Peano (al primo ordine), le funzioni rappresentabili nell'aritmetica di Peano (al primo ordine), incompletezza ed indecidibilità.

V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primo
ordine. Springer, (2014).

V.M. Abrusci, L. Tortora de Falco, L'Incompletezza. Dispense fornite dal docente.