204SM - LOGICA 2021
Section outline
-
(03/03/2022 h.11/13, Aula 3 Edificio C5) Completamento dell'esposizione sui sistemi di logica formale. Cenni introduttivi sul 10.o problema di Hilbert
-
(Con messa a fuoco particolare sul ruolo che rivestí Julia Robinson nella risoluzione, negativa, del problema proposto da Hilbert a Parigi nell'anno 1900)
-
-
(08/03/2022 h.9/11, Aula C Edificio B) Una logica algebrica booleana adeguata alla formalizzazione di qualsiasi teoria assiomatica degli insiemi
-
Si tratta di una rielaborazione tardo-novecentesca di un sistema deduttivo ideato verso la fine del 1800 da Peirce&Schröder, al quale si avvicinano gli odierni linguaggi dei sistemi database relazionali.
Questi lucidi iniziano con un paio di esempi che dovrebbero risultare comprensibili in termini intuitivi; poi vengono presentati:
- lessico
- sintassi
- semantica
- apparato deduttivo
-
Di questa dispensa, al termine della lezione dell'8 marzo, saranno stati coperti su per giú, il paragrafo 1 e i paragrafi 6 (con i suoi sottoparagrafi)
-
-
Dapprima in termini intuitivi, poi con riferimento alla teoria dei numeri, stabiliamo che:
- esistono insiemi elencabili il cui complemento non è elencabile;
- esistono insiemi diofantei il cui complemento non è diofanteo.
Dal secondo di questi risultati, insieme al teorema DPRM (dalle iniziali dei cognomi di Martin D. Davis, Hilary Putnam, Julia Robinson, Yuri V. Matiyasevich) discenderà l'insolubilità algoritmica del 10o problema di Hilbert.
-
Di questa dispensa potete saltare il paragrafo 2.3 e la seconda appendice. Della terza appendice vi serve solo il richiamo dell'enunciato del teorema cinese dei resti.
-
-
...(esercizio per voi!) il lemma di Lindenbaum può venir dimostrato in tutta generalità.
-
-
Viene presentato un linguaggio di programmazione "a registri", Turing-completo. Poi viene esposta una traduzione dei programmi scritti in tale linguaggio di programmazione in sistemi di equazioni diofantee esponenziali: i parametri che compaiono in tali equazioni descrivono il grafo della funzione computata dal programma tradotto; il sistema di equazioni è single-fold (vale a dire, non è sottodeterminato: per quei valori dei parametri per i quali ha soluzione, ne ha soltanto una).
-
(12 aprile h.9/11, aula C edificio B) Semantica della logica predicativa del prim'ordine. Calcolo predicativo del prim'ordine
-
- teoria elementare dei gruppi
- aritmetica di Peano (fine XIX secolo)
- una micro-teoria degli insiemi (Vaught, 1962)
-
(21 aprile h.11/13, aula 3 edificio C5) Completamento della dimostrazione del teorema DPR, nella dimostrazione di Jones-Matiyasevich
È stata inoltre discussa un'applicazione del teorema DPR alla formulazione in un'aritmetica del prim'ordine della congettura di Goldbach
-
Il materiale di questa lezione (presentazioni in formato PDF) è già stato caricato sotto la lezione del 12 aprile.
-
Il materiale di questa lezione (presentazioni in formato PDF) è già stato caricato sotto la lezione del 12 aprile.
-
Come base di lavoro, viene utilizzata la traccia di un recente appello di Logica
-
Un importante esempio: definibilità degli interi nell'aritmetica dei razionali (che dipende da un teorema di Hasse del 1923)
Definibilità dei numeri naturali nell'aritmetica degli interi (questo risultato ci è già noto attraverso i teoremi dei 4 e dei 3 quadrati, ma qui viene ottenuto solo mediante l'equazione di Pell).
Vari esercizi per voi.
-
La presentazione si basa ancora una volta sui lucidi riguardanti il calcolo predicativo del prim'ordine che si trovano fra il materiale del 12 aprile 2022
-
(19 maggio, h.11/13, aula 3 edificio C5) Come passare da una specifica diofantea polinomiale della relazione "essere la n-esima y risolutiva dell'equazione di Pell a discriminante a^2-1" a una specifica diofantea polinomiale dell'esponenziazione "b^n=c"
Rifarsi ai lucidi della lezione del 28 aprile
-
Questa dispensa riporta in un'appendice (scritta in inglese) la dimostrazione della correttezza delle "equazioni di raccordo" proposte da Davis
-
-
-
Il testo della traccia d'esame qui esaminata si trova nel materiale della prima lezione (quella dell'1 marzo) ; oltre a risolvere gli esercizi di tale traccia, ne vengono proposti e discussi anche altri.
-