3 Logica matematica e analisi nonstandard 3 A Trattati generali 3 AE Esposizioni elementari 3 F Filosofia della matematica, Logica filosofica 3 M Monografie 3 P Raccolte 3 XA Filosofia e critica 3 XB Logica matematica generale 3 XC Teoria dei modelli 3 XD Teoria della ricorsivit, lambda-calcolo 3 XE Logica della teoria degli insiemi 3 XF Dimostrabilit e matematica costruttiva 3 XG Logica algebrica 3 XH Analisi nonstandard Esercizi: Cos' un numero naturale? Cos' un insieme? Cos' un'affermazione? Cos' una dimostrazione? Cos' un insieme infinito? Cosa vuol dire "esiste"? Che differenza c' tra un assioma e una definizione? L'ultima domanda facile, ma importante proprio per lo studente. Come in tutti i problemi, anche qui aiuta molto chiarire subito quali sono gli ingredienti della questione. Non avrete tempo di studiare questi problemi nelle opere di Leopold Kronecker (1823-1891), Richard Dedekind (1831-1916), Gottlob Frege (1848-1925), Charles Peirce (1839-1914), Bertrand Russell, Alfred Whitehead, Giuseppe Peano (1858-1932), Ernst Zermelo (1871-1953), David Hilbert, Henri Poincar, Luitzen Brouwer (1881-1966), Kurt Gdel, Alfred Tarski (nato nel 1902), Alonso Church, Alan Turing (1912-1954), anche perch non ha senso imparare a memoria che "Hilbert disse ..., Poincar credette ..., secondo Frege ... " ed molto meglio cercare di arrivare da soli a soluzioni, che poi possono essere confrontate con quelle degli altri. Tenete poi presente che anche i grandi possono sbagliare. G. BAROZZI/S. MATARASSO: Analisi 1. Zanichelli. J. BARWISE (c.): Handbook of mathematical logic. North-Holland 1977. A. CHURCH: Introduction to mathematical logic. Princeton UP 1956. R. EDWARDS: A formal background to mathematics. H. HERMES: Introduction to mathematical logic. Springer 1973. J. MALITZ: Introduction to mathematical logic. Springer 1979. E. MENDELSON: Introduzione alla logica matematica. Boringhieri. Yu. MANIN: A course in mathematical logic. Springer 1977. E. NAGEL/J. NEWMAN: Gdel's proof. Nella raccolta di Kline, citata nella prima lezione, pag. 221-230. J. SHOENFIELD: Mathematical logic. Addison-Wesley 1967. Il reparto di logica uno dei pi forniti della nostra biblioteca, bench sia aggiornato soltanto fino al 1973 circa. La logica matematica una disciplina un p ai margini della matematica, poco amata dagli altri matematici, coltivata con passione dai suoi fedeli. Il libro di Barozzi/Matarasso stato incluso qui perch presenta un'introduzione alla logica matematica pi che sufficiente nella matematica comune, in un linguaggio meno tecnico di quello usato nei testi specialistici di logica. Chi ha pi pazienza e tempo, trover non troppo difficile l'ottimo testo di Hermes. Questo un libro che potrebbe essere studiato con molto guadagno dopo la laurea da chi andato a insegnare. Speriamo che iniziative come questo seminario possano portare a un maggiore utilizzo della biblioteca del dipartimento da parte dei laureati in matematica, soprattutto degli insegnanti: senza leggere tante cose, un insegnante dovrebbe abituarsi a studiare un libro all'anno, in dettaglio, come ai tempi in cui preparava gli esami, magari con un piano di studio, e cose non troppo elementari, ma piuttosto un libro di analisi funzionale, o di topologia, di calcolo combinatorio, di algebra commutativa, di geometria differenziale, di analisi numerica, e cos via. Il libro di Shoenfield uno dei migliori e contiene anche un'introduzione alla teoria dei modelli. Mi sembra che esista un'edizione italiana, nella Boringhieri, probabilmente molto cara. La logica , dall'antichit, una delle discipline centrali della filosofia. Mentre per il filosofo per la questione su cui soprattutto indaga nello studio del pensiero logico la provenienza, il contenuto profondo, l'uso che si pu fare del ragionare umano nella spiegazione delle cose, nella logica matematica si studiano soltanto gli aspetti formali, le regole a cui devono obbedire le teorie deduttive. Una teoria nel senso della logica matematica quindi semplicemente una collezione di cosiddette affermazioni, che per in verit non affermano niente, ma sono, nella maggioranza dei casi, semplicemente stringhe di simboli il cui unico significato la loro posizione deduttiva all'interno di tutta la teoria. La logica matematica moderna essenzialmente opera di George Boole (1815-1864), Gottlob Frege (1848-1945), Giuseppe Peano (1858-1932), Alfred Whitehead (1861-1947) e Bertrand Russell (1872-1970). Forse si dovrebbe aggiungere Immanuel Kant (1724-1804), che, con ambizioni naturalmente molto pi ampie, nella costruzione della sua filosofia usa metodi formali molto simili a quelli della logica matematica e della matematica assiomatica, e anche se in ci praticamente non fa uso di formule, il pensiero sottostante a questa filosofia trascendentale, che un matematico potrebbe chiamare filosofia assiomatica, quasi lo stesso. Il metodo assiomatico nella matematica fu propugnato soprattutto da Hilbert, e l'idea principale questa: "Un orso un pesce con 4 zampe. Tutti i pesci hanno 2 teste. Quindi un orso ha 2 teste e 4 zampe." Per un matematico in questo discorso non c' niente di strano, perch abituato a valutare i ragionamenti soltanto secondo la loro correttezza formale, e il significato comune di orso, pesce, zampa o testa non va considerato in matematica. Questo modo di pensare distingue il matematico dal fisico o dal fisico matematico, in misura tale da poter creare incomprensioni e tensioni: In fisica i termini "corrente", "corpo rigido", "moto", ecc., conservano sempre qualcosa del loro significato intuitivo, che per il matematico non deve assolutamente entrare nelle deduzioni, mentre il fisico matematico ne tiene conto in ogni momento e non disposto a limitarsi a ragionamenti puramente formali. Per questa ragione i fisici matematici odiano l'algebra e la teoria dei numeri, e il matematico si dispera quando trova una mezza dozzina di "errori gravi" su ogni pagina di ogni libro di meccanica. Una teoria si dice consistente o libera da contraddizioni, se in essa non possibile dedurre un'affermazione e il contrario di questa affermazione. Un'affermazione A indipendente da una teoria consistente T, se la teoria che si ottiene aggiungendo A a T ancora consistente, e se anche la teoria che si ottiene aggiungendo a T il contrario di A consistente. Se una teoria non consistente, ogni affermazione considerata indipendente da essa. Kurt Gdel (1906-1978), austriaco, emigrato negli Stati Uniti nel 1939, dimostr nel 1930 che, se una teoria almeno cos interessante come la teoria dei numeri naturali, allora, anche se la teoria consistente, non possibile dimostrare la consistenza all'interno di questa stessa teoria. J. BARWISE (c.): Handbook of mathematical logic. North-Holland 1978. J. BARWISE/S. FEFERMAN (c.): Model-theoretic logic. Springer 1985. J. BELL/A. SLOMSON: Models and ultraproducts. North-Holland 1969. C. CHANG/H. KEISLER: Model theory. North-Holland 1973. Un modello di una teoria T un'interpretazione di T in cui tutti gli assiomi di T sono soddisfatti. Ad esempio i numeri reali sono un modello della teoria dei gruppi abeliani. Nel linguaggio comune si direbbe quindi che un modello un "esempio" di T. La definizione precisa del concetto di interpretazione piuttosto complicata, anche se l'idea semplice: (Z, -) un'interpretazione della teoria dei semigruppi, ma non un modello, perch la sottrazione non associativa. La teoria dei modelli si occupa del passaggio da una teoria formale alle strutture astratte che questa teoria descrive. Ad esempio: Abbiamo da un lato gli assiomi di gruppo, e la teoria generata da questi assiomi (in ogni gruppo vale la legge di cancellazione, che non un'assioma della teoria dei gruppi, ma fa parte di questa teoria), dall'altro lato i gruppi stessi, cio i modelli della teoria. Come sono legati teoria e modelli? Non sono la stessa cosa: Possiamo ad esempio produrre una quantit di teoremi sui gruppi, senza aver mai visto un esempio di gruppo, persino senza sapere se ne esistono. Anche se di una teoria avessimo dimostrato che libera di contraddizioni, non detto che per essa esistano dei modelli. Spesso di una teoria si conoscono modelli semplici o parziali, dai quali si possono ottenere nuovi modelli mediante formazione di ultraprodotti. In questi si usano gli ultrafiltri, che verranno definiti in topologia. Definiamo per esempio, cos' un ultraprodotto di gruppi. Assumiamo di avere una famiglia di gruppi Gk, dove k percorre un insieme di indici K. D sia un ultrafiltro su K e G il prodotto cartesiano insiemistico dei gruppi Gk. Consideriamo due elementi g ed h di G. Diremo che g ed h sono equivalenti, se l'insieme dei k in K, per cui gk = hk, appartiene a D. Diremo in questo caso anche che gk = hk per quasi tutti i k. Questo "quasi tutti" dipende dall'ultrafiltro D. Otteniamo cos una relazione di equivalenza ~ su G, e adesso si dimostra facilmente che G/~ in modo naturale un gruppo, che si chiama l'ultraprodotto dei gruppi dati. Nello stesso modo si costruiscono ultraprodotti per altre strutture, ad es. per corpi, spazi vettoriali, algebre, ecc. Quando i Gk sono tutti uguali, si parla anche di un'ultrapotenza. L'ultrapotenza del corpo R dei numeri reali rispetto all'insieme di indici K = N (numeri naturali) e un ultrafiltro D non principale su N un corpo, detto corpo dei numeri iperreali, e fornisce l'ambiente per una semplice versione dell'analisi non standard. In questo caso gli elementi g sono semplicemente successioni di numeri reali, e la classe di equivalenza della successione (1,1/2,1/3,1/4,...) un numero iperreale (un filamento di R nella terminologia che introdurremo dopo) pi piccolo di ogni numero reale, ma maggiore di zero. Abbiamo quindi scoperto oggetti infinitesimali. Provate a fare i conti neccessari, quando avremo fatto gli ultrafiltri. Meno di una pagina di semplici verifiche! La teoria dei modelli interessante ed ha importanti applicazioni in matematica, ma difficile per il matematico che raramente trova tempo per studiarla in profondit. Il Barwise/Feferman un grosso volume di 900 pagine molto avanzato scritto da una ventina di autori. Lo citiamo soprattutto per il prezzo: costa 450.000 Lire. Diciamo che per una teoria vale il teorema di completezza, se una proposizione vera in tutti i modelli di questa teoria se e solo se la proposizione pu essere derivata all'interno della teoria. Diciamo che per una logica vale il teorema di compattezza, se una teoria formulata in questa logica possiede un modello se e solo se ogni sottoteoria finita (ad es. "ogni sottoinsieme finito di assiomi") possiede un modello. Trovare e caratterizzare le logiche e le teorie per cui valgono questi teoremi uno dei compiti della teoria dei modelli, e il trattato di Barwise/Feferman dedicato quasi interamente a questa problematica. Questo non giustifica il prezzo, ma mostra l'importanza della teoria. E' indubbio che la logica potrebbe contribuire punti di vista e tecniche estremamente utili in molti campi della matematica, ma attualmente la barriera linguistica tra logici e matematici quasi insuperabile. La teoria dei modelli si sta rivelando un utile strumento concettuale nella geometria algebrica reale. In questa teoria si studiano insiemi semialgebrici, cio sottoinsiemi dell'Rn determinati da equazioni e disequazioni polinomiali e tutti gli insiemi che si ottengono da questi insiemi applicando ripetutamente le operazioni insiemistiche di intersezione, unione e complemento. Gli insiemi semialgebrici formano quindi un'algebra di Boole, e lo studio di essi richiede spesso costruzioni simili a quelle della logica formale. La geometria algebrica reale una teoria relativamente giovane, non facile, con applicazioni in robotica (cfr. la Nota 9.12 del corso di topologia), ed esposta nel trattato di Bochnak/Coste/Roy. M. DAVIS: Computability and unsolvability. McGraw-Hill 1958. M. DAVIS/E. WEYUKER: Computability, complexity, and languages. Academic Press 1983. J. FENSTAD: General recursion theory. Springer 1980. H. ROGERS: Theory of recursive functions and effective computability. McGraw-Hill 1967. A. YASUHARA: Recursive function theory and logic. Academic Press 1971. Alonzo Church, nato nel 1903, un logico famoso e la tesi di Church conosciuta anche da chi non esperto di logica: Essa un assioma della teoria della complessit degli algoritmi e dice che ogni funzione che pu essere descritta da un algoritmo finito, o equivalentemente ogni funzione per cui si pu scrivere un programma per un calcolatore, una funzione ricorsiva. Una funzione ricorsiva all'incirca ci che uno si aspetta, cio una funzione di uno o pi argomenti, che devono essere numeri naturali, con valori nei numeri naturali, tale che i suoi valori per un certo argomento sono determinati dai valori che la funzione assume per argomenti pi piccoli. Bisogna poi considerare anche funzioni non sempre definite, che corrispondono a quelle eccezioni negli algoritmi in cui l'algoritmo non termina, e a questo punto le definizioni corrette e tutta la teoria diventono piuttosto intricate. I dettagli si trovano nei libri di Yasuhara, Davis, Rogers. La teoria della complessit oggi uno dei campi centrali della logica matematica ed ha applicazioni non solo in informatica, ma anche in geometria algebrica reale, nell'analisi numerica, in teoria dei numeri, nell'ottimizzazione combinatoria. Da questi esempi estremi si vede come ogni suddivisione della matematica in territori illusoria. La ricerca matematica moderna interdisciplinare. Gli appassionati di logica si affezioneranno al libro di Davis, che contiene un'introduzione alla teoria delle funzioni ricorsive, alla logica matematica, e in un'appendice alla soluzione che Yu. Matijasevich diede nel 1970 al decimo problema di Hilbert: Matijasevich dimostr che non esiste un algoritmo che permette di decidere per un polinomio qualsiasi f con coefficienti interi, se esistono interi a1,...,an tali che f(a1,...,an) = 0. H. ABELSON/G. SUSMAN: Structure and interpretation of computer programs. MIT Press 1985. H. BARENDREGT: The lambda-calculus. North-Holland 1984. A. CHURCH: The calculi of lambda-conversion. Princeton UP 1985. Church anche l'inventore del lambda-calcolo, che nella notazione VARxf(x) che noi usiamo, potrebbe essere anche chiamato il VAR-calcolo, cio la teoria formale del simbolo VAR. La cosa sorprendentemente complicata, perch nel lambda-calcolo non si parte da funzioni definite su insiemi gi ben determinati, ma si costruisce il concetto di funzione a partire dalle sole propriet formali del simbolo VAR o lambda. Il problema principale diventa quindi quali sostituzioni si devono permettere, quando due funzioni sono da considerare equivalenti, come si possono introdurre ricorsioni. Si chiama lambda-calcolo, perch Church scrive lx.f(x) invece di VARxf(x). Il lambda-calcolo viene usato nell'Intelligenza artificiale, ed la base teorica del linguaggio di programmazione Lisp. Il libro di Abelson/Susman un'introduzione alla programmazione molto buona che utilizza il Lisp. Notizie sulla storia travagliata e sulle applicazione del lambda-calcolo si trovano nella grande monografia di Barendregt. S. ALBEVERIO e.a.: Nonstandard methods in stochastic analysis and mathematical physics. Academic Press 1986. M. DAVIS: Applied non standard analysis. Wiley 1977. P. HALMOS: Has progress in mathematics slowed down? American Math. Monthley 97 (1990), 561-588 (vedere pag. 569-570). A. LIGHTSTONE/A. ROBINSON: Non-archimedean fields and asymptotic expansions. North-Holland 1975. E. NELSON: Internal set theory: A new approach to nonstandard analysis. Bull. AMS 83 (1977), 1165-1198. E. NELSON: Radically elementary probability theory. Princeton UP 1987. A. ROBINSON: Non-standard analysis. North-Holland 1966. K. STROYAN/W. LUXEMBURG: Introduction to the theory of infinitesimals. Academic Press 1976. L'analisi non standard fu creata da Abraham Robinson (1918-1974). Per le motivazioni storiche e le applicazioni rimandiamo ai libri indicati. In questa teoria si assume che ad ogni insieme X sia associato un insieme pi grande X(), detto il tessuto di X, i cui elementi si chiamano filamenti o elementi ideali di X. Quindi ogni elemento di X anche un filamento di X, ma oltre agli elementi di X esistono, quando X non finito, anche altri punti nel tessuto di X. La costruzione di questi tessuti sia compatibile con tutte le operazioni insiemistiche finitarie, quindi il tessuto del prodotto cartesiano di due insiemi sia il prodotto cartesiano dei loro tessuti, lo stesso per intersezione, unione, complemento, ecc. In particolare assumiamo che ad ogni applicazione tra due insiemi sia associata in modo naturale un'applicazione tra i loro tessuti, cosicch possiamo dire che la funzione trasforma i filamenti del primo insieme in filamenti del secondo. Se un filamento di X appartiene al tessuto di un sottoinsieme A di X, diremo anche che quel filamento aderisce ad A. Fin qui si potrebbe porre X() = X per ogni insieme X. Ma adesso si aggiunge un ulteriore assioma, il cui effetto quello di una compattificazione della teoria degli insiemi: Per ogni insieme X ed ogni filtro F su X esiste un filamento di X che aderisce a tutti gli elementi di F. Le applicazioni pi affascinanti si hanno in topologia generale: Diciamo che un filamento vicino a un punto x di uno spazio topologico X, se il filamento aderisce ad ogni intorno di x. Allora si dimostra che una funzione f tra spazi topologici continua in x se e solo se trasforma filamenti vicini ad x in filamenti vicini ad f(x). X compatto se e solo se ogni filamento di X vicino a un punto di X. X T4 se e solo se, quando A e B sono chiusi disgiunti di X, nessun filamento di X aderisce allo stesso tempo a tutti gli aperti che contengono A e a tutti gli aperti che contengono B. I concetti topologici usati verranno spiegati nel corso. Chi ci crede, pu provare a leggere il libricino di Edward Nelson, nato nel 1932, che d un'introduzione al calcolo delle probabilit e ai processi stocastici, tutta basata sull'analisi nonstandard.