Logica La teoria della realizzabilita' classica e l'assioma dell'ultrafiltro Davide Barbarossa 20-07-2018 - 11:30 Largo San Leonardo Murialdo,1 - Pal.C - AULA 311
La teoria della realizzabilita' classica e' stata introdotta da J.-L. Krivine negli anni 2000 a seguito di una intuizione di T. Griffin, che ha tipato l'istruzione "callcc" in Scheme (simile alla istruzione "try-catch" in Java) con la regola dell'assurdo (nella forma di legge di Pierce). Questo ha portato a generalizzare la corrispondenza di Curry-Howard a tutta la logica classica, ed anche oltre: assiomatizzando la nozione di programma (lambda-termine) e di esecuzione (programma + pila di esecuzione), grazie alle "algebre di realizzabilita'", si riesce ad associare programmi a dimostrazioni (classiche) che usino assiomi supplementari - come ad esempio quelli della teoria degli insiemi. Questi programmi, chiamati "realizzatori" della formula dimostrata, ne forniscono una "giustificazione" che e' una semantica intermedia tra quella Tarskiana (vero/falso) e quella data dalle dimostrazioni. In questo incontro ci concentreremo sull'assioma dell'ultrafiltro ("esiste un ultrafiltro non triviale sull'algebra di Boole delle parti di N") nel quadro della aritmetica al secondo ordine. |