PROGRAMMA COMMENTATO (continua) (dall'11 novembre) LOGICA MATEMATICA (AA 2015-16) Paolo Lipparini Ricordo che questi commenti, e i riferimenti ai libri di Mendelson [M] e Chang Keisler [CK] fanno parte del programma (esclusi gli esercizi, di solito); gli altri riferimenti non fanno parte del programma, a meno che non sia esplicitamente indicato altrimenti. (11 nov) Ancora su *R. La somma di due infinitesimi e' un infinitesimo. Un elemento di *R e' un infinitesimo non nullo se e solo se il suo inverso e' infinito. Elementi infinitamente vicini; l'essere infinitamente vicino e' una relazione di equivalenza. Ogni elemento finito di *R e' infinitamente vicino ad uno ed un solo reale standard [note consegnate a lezione]. (12 nov) Condizioni equivalenti in termini non standard delle nozioni di limite, continuita', continuita' uniforme di una funzione reale [note consegnate a lezione]. Cenni ai numeri surreali (introdotti mediante i tagli di Cuesta Dutari, facoltativo, dettagli in N. Alling, Foundations of analysis over surreal number fields, 1987, Sezione 4.02). Approfondimenti: Conway, J . H . (1976), On Numbers and Games. Knuth, D.E. (1974), Surreal Numbers. H. Gonshor, An introduction to the theory of surreal numbers, 1986. P. Ehrlich, The absolute arithmetic continuum and the unification of all numbers great and small, Bull. Symbolic Logic, 18 (2012). (17 nov) Cenni all'interpretazione non standard della "delta di Dirac" (facoltativo) [Approfondimento: A. Robinson, Non standard analysis, Sezione 5.3]. Estensioni conservative di una teoria (nel caso piu' semplice: se T e T' sono teorie nei linguaggi L ed L', con L contentuto in L', si dice che T' e' un'estensione conservativa di T se i teoremi di T' *** nel linguaggio L *** coincidono con i teoremi di T. Le definizioni si possono interpretare come estensioni conservative. Esempi in: S. Simpson, Subsystem of Second Order Arithmetic) Diagramma Diag(A) di un modello A. Ogni modello di Diag(A) contiene un sottomodello isomorfo ad A [CK, Proposizione 2.1.8 e definizioni precedenti]. Una teoria e' chiusa per sottomodelli se e solo se e' equivalente ad una teoria universale [CK, 3.2.2, la dimostrazione in CK usa il lemma 3.2.1 che e' piu' generale di quanto serva in questo caso particolare]. (18 nov) Cenni alla distinzione fra classi ed insiemi; cenni a teorie degli insiemi che usano "classe" come nozione primitiva. [M, prime tre pagine del Capitolo 4]. Non e' vero che se una classe K di modelli (per lo stesso linguaggio L) e' chiusa per sottomodelli, allora K e' la classe dei modelli di una teoria del primo ordine (esempio: la classe dei modelli finiti per L). Sia fissato un linguaggio L. Se T e' una teoria del primo ordine, indichiamo con Mod(T) la classe dei modelli di T. Teorema di Birkhoff (esteso a linguaggi con relazioni): una classe K di modelli e' chiusa rispetto a sottomodelli, immagini omomorfe e prodotti diretti se e solo se K = Mod(T), per qualche teoria T tale che ogni enunciato di T e' la chiusura universale di una formula atomica (non dimostrato, [CK, Esercizio 6.2.13]. Ma vedi anche la lezione del 4 dicembre). (N.B.: la differenza col teorema dimostrato nella lezione precedente [cioe' CK, 3.2.2] e' che, in quel caso, si assume gia' che K sia la classe dei modelli di qualche teoria; in questo caso, di K si assume solo la chiusura rispetto a quelle costruzioni) Teorema di Lowenheim-Skolem verso il basso (dimostrazione nelle prossime lezioni). Corollario: se una teoria nel linguaggio L ha un modello, allora ha modelli di ogni cardinalita' infinita maggiore o uguale a |L|. Paradosso di Skolem (se esiste un modello M della teoria degli insiemi, allora esiste un modello numerabile N; ma, all'interno di questo modello N si puo' dimostrare l'esistenza di insiemi non numerabili - dal punto di vista di N - anche se, dal punto di vista di M, questi insiemi sono numerabili) [note consegnate a lezione]. (19 nov)(3 ore) Sottostrutture elementari e criterio di Tarski Vaught. Teorema di Lowenheim-Skolem verso il basso (nella forma forte che comporta la costruzione di una sottostruttura elementare contenente un sottoinsieme dato) [note consegnate a lezione]. (24 nov) Esempio di dimostrazione del Teorema di Lowenhem Skolem verso il basso in un caso particolare. https://www.mat.uniroma2.it/~lipparin/stud/AA1516/ls.JPG (fa parte del programma). Filtri su un insieme. Esempi: filtro dei cofiniti, banale, improprio, filtri principali. Prodotti infiniti di modelli; prodotti ridotti modulo un filtro F. Esempi: il prodotto ridotto di una famiglia di gruppi (o insiemi parzialmente ordinati) e' ancora un gruppo (un insieme parzialmente ordinato). Un prodotto ridotto di ordini totali non sempre e' un ordine totale. Una definizione di ultrafiltro; enunciato del Teorema di Los [CK, Sezione 4.1, fino a 4.1.11 compreso, ma escluso Teorema 4.1.8; dimostrazioni e ulteriori dettagli nelle prossime lezioni]. (25 nov) Esempio: l'insieme degli intorni di un punto in uno spazio topologico e' un filtro. Filtro generato da una famiglia di sottoinsiemi; tale filtro e' proprio se e solo se la famiglia gode della proprieta' dell'intersezione finita. Un filtro F proprio su I e' massimale se e solo se, per ogni sotoinsieme X di I, X sta in F oppure il complemento di X sta in F. (26 nov) (3 ore) Esempio: sia I un insieme non vuoto, F un filtro su I e x un nuovo elemento non in I. Su S=I U {x} si puo' definire una topologia nel seguente modo: gli aperti sono - l'insieme vuoto; - tutti i sottoinsiemi di I; - tutti i sottoinsiemi Z di S tali che Z intersezione I sta in F. Quindi tutti i filtri possono essere ottenuti per via topologica. Ogni filtro proprio si puo' estendere ad un ultrafiltro (usando il Lemma di Zorn). Quindi esistono ultrafiltri non principali. Inoltre, ogni famiglia con la proprieta' dell'intersezione finita puo' essere estesa ad un filtro, quindi puo' essere estesa ad un ultrafiltro. [CK, 4.1] Ancora sulla definizione di prodotto ridotto di una famiglia di modelli modulo un filtro F. Verifica che le operazioni (le interpretazioni dei simboli di funzione) passano al quoziente [CK, 4.1]. In senso algebrico (cioe' limitatamente alle operazioni) un prodotto ridotto puo' essere visto come quoziente del prodotto diretto. Il prodotto diretto e' (isomorfo al) prodotto ridotto modulo il filtro banale {I}. (1 dic) Buoni ordini. Esempi. Induzione transfinita su buoni ordini. Principio del buon ordinamento (per ogni insieme X esiste una relazione di ordine totale su X che e' un buon ordinamento). Cenni agli ordinali come rappresentanti di "classi di equivalenza" di buoni ordini isomorfi. Assioma dell'infinito. Dimostrazione che un filtro proprio su I puo' essere esteso ad un ultrafiltro usando l'ipotesi che P(I) sia bene ordinabile (facoltativo). Brevissimi cenni sui giochi infiniti e assioma di determinatezza (dato un gioco a due persone su N con un infinita' numerabile di mosse, esiste una strategia vincente per uno dei due giocatori) (facoltativo) Approfondimenti: Sezioni 27 - 28 in A. Kanamori, M. Magidor, The evolution of large cardinals axioms in set theory. In: Higher Set Theory. Proc. Conf., Math. Forschungsinst., Oberwolfach, 1977. Lecture Notes in Math. Vol. 669 (G. H. Muller and D. S. Scott, a cura di),pp. 99 - 275 (Springer, Berlin, 1978) M. Foreman, A. Kanamori (a cura di), Handbook of Set Theory, 2010. Sulle forme equivalenti dell'Assioma di Scelta, e sulle sue conseguenze, si possono consultare: H. Rubin, J.E. Rubin, Equivalents of the Axiom of Choice, II, 1985. P. Howard, J. E. Rubin, Consequences of the Axiom of Choice, 1998. (2 dic) (3 ore) Introduzione informale agli ordinali. Esempi di costruzioni mediante iterazioni transfinite: la catena risolubile discendente per gruppi. Se G e' un gruppo, G' e' il sottogruppo generato da g*h*gh, con g, h in G, e dove g* indica l'inverso di g. Per induzione transfinita, per ogni ordinale a si puo' definire: G(0)=G, G(a+1)=(G(a))' se a ordinale limite, G(a)= intersezione di tutti i G(b), con b