Programma del corso con bibliografia
Appunti su calcolabilita' e teoremi di Godel aggiornati al 31 Dic. 2008. Rivisti 10 Gen. 2008 (correzione piccolo refuso).
. Qui c'e' il grosso degli argomenti trattati a lezione, ad esclusione del teorema di completezza che si trova negli appunti sulla deduzione naturale.
Importante: In data 31 Dic. 2008 ho modificato l'ultima parte, quella sulle interpretazioni e le teorie indecidibili, aggiungendo il teorema che ogni teoria decidibile ha una estensione decidibile completa. Per ristampare solo questa parte cliccare qui.
Per la parte precedente ho fatto solo piccolissime correzioni di refusi a p. 14 (z al posto di y), p. 20 (definizione ricorsiva di Cat), p. 29 (mancava una variabile a riga 2 della dim. di 11.1), p. 30 (nella dim. di 12.1 ho aggiunto "quindi f e' calcolabile"), p. 55 (punto 2 dell'osservazione 16.24).
Appunti sulla deduzione naturale, versione 10 Gen. 2008.
Non e' esattamente il sistema dimostrativo che ho usato a lezione ma
e' quasi uguale e non dovrebbe esservi difficolta' nel passare dall'uno all'altro. Questi appunti contengono la dimostrazione del teorema di completezza. Le differenza principali con il metodo trattato a lezione sono due.
1) Nella deduzione naturale una dimostrazione non e' una successione di formule ma e' una successione di "giudizi". Un giudizio e' una coppia (Ipotesi, formula), in cui al secondo posto c'e' una formula, e al primo posto c'e' un insieme di formule che esplicitano le ipotesi da cui dipende la validita' della data formula.
2) Nel sistema della deduzione naturale le tautologie non si dimostrano gratuitamente in un passo (come nel sistema dato a lezione), ma vanno anch'esse dimostrate a partire da opportune regole. Questa differenza e' ovviamente irrilevante ai fini di dimostrare la ricorsiva enumerabilita' dei teoremi (visto che in ogni caso l'insieme della tautologie e' ricorsivo perche' c'e' l'algoritmo delle tavole di verita').
Appunti su teorie e modelli.
La prima parte si sovrappone in parte gli appunti sulla deduzione naturale. Nel capitolo 4 viene data una dimostrazione del teorema di compattezza che non passa per il teorema di completezza (non in programma). Il capitolo 5 contiene la dimostrazione dei teoremi di Lowenheim Skolem. I capitoli successivi al quinto vertono su questioni non in programma.
NON IN PROGRAMMA: Alcuni appunti sugli insiemi e sui numeri cardinali e ordinali si possono trovare al link: Appunti sulla teoria degli insiemi..
Cose importanti da studiare per l'esame.
1) Il contenuto degli appunti su calcolabilita' e teoremi di G"odel.
2) La semantica di Tarski e il teorema di completezza per un sistema dimostrativo a vostra scelta. Per questa parte tutto sommato puo' esservi comodo basarvi sugli appunti sulla deduzione naturale: anche se il sistema non e' identico a quello fatto a lezione per lo meno ci sono molti dettagli.
3) Per approfondimenti potete consultare gli appunti sulle teorie e i modelli. La maggior parte delle cose non e' in programma o si sovrappone al contenuto degli appunti sulla deduzione naturale. Puo' pero' essere utile dare una occhiata al capitolo 5 dove ci sono i teoremi di Lowenheim-Skolem a cui abbiamo fatto riferimento a lezione.