Deze cursus bestaat uit vier delen.
Het eerste deel, verzamelingen, sluit direct aan op de cursus Wat is Wiskunde?. We verdiepen onze kennis van de naïeve (= niet-axiomatische) verzamelingenleer. De onderwerpen zijn: kardinaalgetallen, keuze-axioma, lemma van Zorn, welordeningen en transfiniete recursie. In een appendix worden enkele equivalenties met het keuze-axioma bewezen.
Deel twee, modellen, definieert een stramien waarbinnen veel wiskundige theorieën kunnen worden opgeschreven: een taal in de predicaatlogica, en modellen voor zo'n taal. Verder: de Compactheidsstelling, kwantor-eliminatie voor algebraïsch afgesloten lichamen, en de stellingen van Löwenheim en Skolem.
In het derde deel wordt precies gedefinieerd wat we onder een (formeel) bewijs verstaan. We bewijzen Gödel's Volledigheidsstelling die zegt dat er voor een uitspraak een bewijs is, precies dan als die uitspraak geldt in alle modellen.
Deel vier tenslotte, geeft het formele axiomasysteem van de verzamelingenleer, dat door de meeste wiskundigen als grondslag van hun vak wordt gezien, en een korte inleiding in het werken met deze axioma's.
Literatuur: de syllabus "Sets, Models and Proofs" (I. Moerdijk en J. van Oosten)
Voorkennis: eerste twee jaar wiskunde
De modeltheorie bestudeert eigenschappen van een theorie T aan de hand van de klasse van modellen van T. Eigenschappen als: T heeft een verzameling axioma's van een bepaalde (eenvoudige) vorm, of: T heeft kwantor-eliminatie, blijken geformuleerd te kunnen worden als afsluitingseigenschappen van de klasse modellen van T.
Enkele constructies passeren de revue: colimieten van gerichte systemen, en ultraproducten. We staan uitvoerig stil bij kwantor-eliminatie en het iets zwakkere begrip model-compleetheid. Ook wordt de speciale theorie van aftelbare modellen behandeld. Aan het eind geven we een bewijs van Stone's dualiteitsstelling tussen Boole-algebra's en compacte, nuldimensionale Hausdorffruimten.
Als de tijd het toelaat wordt ook de bekende stelling van Tarski behandeld, die zegt dat de theorie van R als geordend lichaam, kwantor-eliminatie heeft.
Literatuur: de syllabus "Model Theory" (J. van Oosten). Goede boeken zijn die van Chang & Keisler, en Hodges (die allebei Model Theory heten); handzamer en moderner is het boekje van David Marker: Model theory: an Introduction
Voorkennis: College Grondslagen + eerste twee jaar wiskunde.
Wat is een algoritme? Wat is een berekening? Op deze vragen geeft de recursietheorie antwoord: het antwoord bestaat uit het mathematische model van een registermachine (een geïdealiseerde computer). Een functie f van N naar N heet berekenbaar als er een registermachine programma is, dat voor elk getal n, f(n) berekent. We bestuderen algemene eigenschappen van berekenbare functies, en operaties op berekenbare functies. Deze operaties kunnen ook weer `berekenbaar' zijn, enzovoort. De stelling van Kreisel-Lacombe-Shoenfield zegt, dat zulke berekenbare operaties altijd continu zijn met betrekking tot een natuurlijke topologie.
Toepassingen van de recursietheorie liggen nogal eens op het vlak van aantonen dat er voor een bepaald probleem geen algoritme met gewenste eigenschappen kan bestaan. Zo kon Matiyasevic in 1970 bewijzen dat er geen algoritme is dat voor een willekeurige veelterm P met gehele coëfficiënten (en een willekeurig aantal variabelen), uitmaakt of de vergelijking P=0 gehele oplossingen heeft.
Als de tijd het toelaat, schetsen we aan het eind het bewijs van de bekende Onvolledigheidsstellingen van Gödel. Populair gezegd komen die hierop neer, dat met normale wiskundige middelen niet kan worden aangetoond, dat de wiskunde vrij van tegenspraken is.
Literatuur: De syllabus "Recursietheorie" (J. van Oosten). Goede naslagwerken zijn "Theory of Recursive Functions and Effective Computability" van Hartley Rogers en "Classical Recursion Theory" van Odifreddi; een goede tekst is ook "Computability: an Introduction to Recursive Function Theory" van Nigel Cutland.
Voorkennis: het college Grondslagen + eerste twee jaar wiskunde
Hier is het tentamen van 29 april 2002, en een beknopte uitwerking.
Naar Jaap van Oosten.
Naar Jaap van Oosten's Onderwijspagina