| 21 febbraio |
Richiami sul calcolo
proposizionale e predicativo del primo ordine
- Teoria degli insiemi:
• la teoria ingenua degli insiemi
• Il paradosso di Russell
• il principio di buona fondazione
• alcuni assiomi per una teoria degli insiemi
- il calcolo proposizionale come sintassi per le operazioni finitarie
(intersezione, disgiunzione e complemento) tra insiemi
- il calcolo predicativo come sintassi per le operazioni di unione e intersezione
arbitrarie uniformi tra insiemi
- i calcoli logici come strumenti per la dimostrazione della veritą classica
|
| 28 febbraio |
Risultati di base sul calcolo
proposizionale e predicativo - Teorema di validitą
- Teorema di completezza (senza dimostrazione) - Limiti dell'espressivitą del linguaggio
del primo ordine
• Teorema di compattezza
• non-esprimibilitą della finitezza, non-esprimibilitą di una teoria per i numeri
naturali
- Il problema della decidibilitą
• teorema di decidibilitą del calcolo proposizionale
• la questione della decidibilitą del calcolo predicativo
|
| 7 marzo |
Calcolabilita` effettiva
- codifica nei numeri naturali
- funzioni primitive ricorsive
- funzioni parziali ricorsive
- esempi di funzioni ricorsive
- funzioni ricorsive come programmi
- non tutte le funzioni sono calcolabili
• la questione della cardinalitą
• il problema dell'arresto
|
| 14 marzo |
Teorie per i numeri naturali e
loro proprietą
- La teoria Q e la teoria PA
- modelli standard e non-standard di Q e PA
- Codifica di Q e PA nei numeri naturali
• l'insieme dei teoremi
• l'insieme delle dimostrazioni
- la rappresentabilita` degli insiemi e delle funzioni ricorsive
|
| 21 marzo |
I teoremi di Goedel
- struttura della prova del primo teorema di Goedel (i.e. trovare un enunciato che affermi
"io non sono dimostrabile")
- il lemma di diagonalizzazione
- I Teorema di incompletezza di Goedel: non esiste una teoria consistente, completa ed
effettivamente assiomatizzabile dei numeri naturali
- Teorema di indecidibilitą del calcolo predicativo del primo ordine
- la dimostrazione dell'esistenza di dio
- Teorema di Loeb
- II teorema di incompletezza di Goedel: la non dimostrabilitą della consistenza
|
