Moritz Müller, teaching

Moritz Müller



This page is no longer maintained.


Teaching




WS2016 Lecture: Introduction to theoretical computer science


Tuesday 12:20-13:50, Wednesday 16:15-17:45, KGRC lecture room 101

The course offers an introduction to computational complexity theory around the P versus NP problem. It is an introductory course in the master programme Mathematical Logic and Theoretical Informatics. Some elementary knowledge in mathematical logic is assumed. For example, familiarity with the contents of the course Basic concepts of mathematical logic from summer 2016 is sufficient.

The course follows the lecture notes pdf

Course evaluation pdf

Literature


WS2016 Lecture: Topics in Computability


Tuesday 15:30-17:30, KGRC lecture room 101

Scott and Solovay observed that Cohen's method of forcing can be interpreted as a method to construct Boolean valued models. Scott proved the independence of CH from a higher order theory of the reals by interpreting first-order variables of the language over random reals, i.e. real valued random variables. The course starts with a review of Scott's construction and then treats Krajicek's recent book where such forcing with random variables is developed as a method to construct Boolean valued models for weak theories of arithmetic.

Advanced course in the master programme Mathematical Logic and Theoretical Informatics.

1. Scott's forcing extensions of the real ordered field
2. Subultrapowers and general versions of Los' Theorem
3. Basics about nonstandard models of arithmetic
4. Krajicek's forcing against weak arithmetics

Course evaluation pdf

Literature


SS2016 Lecture: Model theory


Tuesday 17:30-19:00, KGRC lecture room 101.

The course develops model theory with the goal to prove Morley's theorem. It follows the book of Tent and Ziegler referenced below.

Advanced course in the master programme Mathematical Logic and Theoretical Informatics, assumes knowledge of the contents of the course Introduction to mathematical logic of Vera Fischer in WS2015.

Course evaluation pdf.

The following gives an regularly updated overview of the material covered. The parentheses refer to the book of Tent and Ziegler, and only roughly sketch the contents.

0. Prologgeneral motivation, examples vector spaces and algebraically closed fields.
1. Preliminaries elementary diagrams, elementary maps (pp.1-17).
2. Types realizations, images under elementary maps (L2.2.7, D2.2.8, C2.2.9, L4.2.5).
3. Saturation Tarski chain lemma, existence of kappa-saturated extensions, isomorphism from saturation (T2.1.4, D5.2.7, proof of L5.2.9, L5.2.8).
4. Quantifier elimination QE criterion and application to algebraically closed fields, infinite vector spaces (T3.2.5, T3.3.3, T3.3.11).
5. Indiscernibles existence of indiscernibles, models generated by indiscernibles (D5.1.1, L5.1.3, L5.1.6, C5.1.9).
6. Omega-stability omega-stability and total transcendence, example algebraically closed fields, categoricity and saturation (Sec 5.2).
7. Prime extensions existence and atomicity of prime extensions, Lachlan's Lemma, Morley downwards (T5.3.3, C5.3.7, T5.4.1, C5.4.2).
8. Vaughtian pairs omega-homogeneity, conjugacy and type-equality, Beth's Definability Theorem, Vaughtian pairs and elimination of infinity quantifiers,
Vaught's Two Cardinal Theorem, categoricity and Vaughtian pairs (D5.5.1, C5.5.5, D5.5.6, L5.5.7, D4.3.6, L5.5.3, T5.5.2, C5.5.4).
9. Matroids Existence and equicardinality of bases, dimension formula (LC.1.3,LC.1.6,LC.1.8).
10. Algebraicity algebraic closure, non-algebraic type extensions, elementary partial maps extend to algebraic closure (Sec 5.6).
11. Strong minimality matroids on strongly minimal sets, algebraic closure in algebraically closed fields, models of strongly minimal theories (Sec 5.7).
12. Morley's Thoerem Baldwin-Lachlan characterization of uncountable categoricity, Morley's Theorem (T5.8.1,C5.8.2).

Literature

SS2016 Lecture: Grundbegriffe der mathematischen Logik


Montags von 9:45 bis 11:15 Uhr im HS 11, Oskar-Morgenstern-Platz 1, 2. Stock.

Die Vorlesung bietet eine erste Einführung in die mathematische Logik: Syntax und Semantik der Prädikatenlogik, formaler Beweisbegriff, Gödelscher Vollständigkeitssatz, Grundzüge der Berechenbarkeitstheorie, erster Gödelscher Unvollständigkeitssatz. Die Vorlesung folgt dem unten angegebenen Buch von Martin Ziegler.

Vera Fischer gibt die Vorlesung begleitende Übungen.

Vorlesungsevaluation pdf.

Prüfungsergebnisse pdf

1. Vorlesung 07.03: Aussagenlogik. Skript pdf.
2. Vorlesung 14.03: Syntax und Semantik der Prädikatenlogik Seiten 2-9 (in Zieglers Buch), bis Koinzidenzlemma (Satz 2.1) ohne Beweis.
3. Vorlesung 04.04: S.9-13, Beweis Koinzidenzlemma (Satz 2.1), Substitutionslemma (Lemma 2.2), Allgemeingültigkeit, Zweites Koinzidenzlemma (siehe Lemma S.13).
4. Vorlesung 11.04: S.13-19, Tautologien, Hilbertkalkül, Korrektheitssatz (Richtung von links nach rechts im Vollständigkeitssatz S.17).
5. Vorlesung 18.04: Schritte 1 und 2 des Beweises von Satz 4.3 (S.19,20), Korollare Vollständigkeitssatz allgemeine Form und Kompaktheitssatz (Folgerungen 4.4 und 4.5, S.24).
6. Vorlesung 25.04: Beweis Satz 4.3 (S.21-23), Löwenheim-Skolem abwärts (Folgerung 4.5) und aufwärts (pdf.).
7. Vorlesung 02.05: Registermaschinen und Flussdiagramme (S.67,68,70,71).
8. Vorlesung 09.05: Rekursive und primitiv rekursive Funktionen (S.69), Beipiele (Lemma 13.1), rekursive Funktionen sind berechenbar (Satz 12.1).
9. Vorlesung 23.05: rekursive und primitiv rekursive Relationen (S.74,75), Kodierung von Folgen (Lemma 13.6), Gödelisierung von Maschinen (S.77)
10. Vorlesung 30.05: rekursiv gleich berechenbar (Beweis Satz 12.1), Kleene Prädikat, Kleene Normalform (S.77-79), rekursiv aufzählbare Mengen (S.80,81).
11. Vorlesung 06.06: arithmetische Mengen, Gödelsche Beta-Funktion, rekursive Funktionen sind arithmetisch.
12. Vorlesung 13.06: Gödelisierung prädikatenlogischer Syntax, effektiv axiomatisierbare und entscheidbare Theorien, Repräsentierbarkeit.
13. Vorlesung 20.06: Tarski's Satz über die Undefinierbarkeit der Wahrheit, Erster Gödelscher Unvollständigkeitssatz.

Skript ab Vorlesung 11: pdf

Literatur

WS2015 Lecture: Introduction to theoretical computer science


Tuesday 15:15-17:45, KGRC lecture room 101.

Lecture notes: pdf

Course evaluation: pdf



WS2015 Proseminar: Introduction to mathematical logic


Friday 11:05-12:35, KGRC lecture room 101.

Joint course with Stefan Hoeffelner, discusses exercises to the lecture Introduction to mathematical logic of Vera Fischer.

Series 1: pdf    (propositional logic, inductive structures, propositional compactness theorem)
Series 2: pdf    (embeddings and existential sentences, Cantor's theorem, prenex normal forms, provability)
Series 3: pdf    (Henkin term structures, examples compactness theorem)
Series 4: pdf    (Herbrand's theorem, well-orders, theory of algebraically closed fields, elementary substructures)
Series 5: pdf    (unions over directed systems, finitely generated substructures, polynomial maps over the complex numbers, algebraic diagrams)
Series 6: pdf    (infinitary formulas and compactness, Beth's definability theorem)
Series 7: pdf    (two proofs of the ultrafilter theorem, an ultraproduct of finite groups)
Series 8: pdf    (random graph, nonstandard analysis, space of types)
Series 9: pdf    (bounded formulas, bounded induction, Parikh's theorem)
Series 10: pdf    (definitorial extensions, incompleteness theorems of Gödel and Rosser)
Series 11: pdf   (ordinals, transitive closure, class form of foundation)
Series 12: pdf   (Hartogs aleph versus aleph, fixed points of normal functions, irreducible topological maps, Dedekind-infinity)
Series 13: pdf   (nonstandard models of ZFC, Tarski on (AC), cofinality, inaccessible cardinals)



SS2015 Lecture: Computability and complexity


Tuesday 16:00 - 17:30, KGRC lecture room 101 (Währinger Straße 25, 2nd floor).

The set of polynomial time computable function is classically defined as operating with finite binary strings or natural numbers. What does it mean for a function on arbitrary sets to be polynomial time computable?
In 1965 Cobham characterized the set of classical polynomial time computable functions as the closure of a set of certain initial functions under composition and a certain restricted from of recursion.
On arbitrary sets we define the class of so-called Cobham Recursive Set Functions as the closure of a certain set of initial functions under composition and an analogously restricted form of epsilon-recursion.
The course offers an introduction to the corresponding theory. For example, we ask for a fragment of Kripke-Platek set theory whose provably total functions are precisely CRSF.

The course is an advanced course in the master programme Mathematical Logic and Theoretical Informatics. It assumes basic knowledge in set theory. Knowledge in complexity theory is useful but not necessary.

Preprint here.

Lecture Notes for June 2015. These are regularly updated after each lecture and reflect the current state of the course: here.

Course evaluation: pdf



SS2015 Lecture: Grundbegriffe der mathematischen Logik


Mittwochs von 9:45 bis 11:15 Uhr im HS 2, Oskar-Morgenstern-Platz 1.

Prüfungsergebnisse pdf.

Vorlesungsevaluation: pdf



WS2014 Lecture: Introduction to theoretical computer science


Thursday 10:00 - 12:30. KGRC Lecture Room 101.

Lecture notes: pdf


WS2014 Proseminar: Einführung in die mathematische Logik


Montag 17:30 - 19:00, KGRC Raum 101.

Das Proseminar behandelt Übungsaufgaben zur Vorlesung Introduction to mathematical logic von Lyubomyr Zdomskyy.

Blatt 1 pdf       
Blatt 2 pdf       
Blatt 3 pdf       
Blatt 4 pdf       
Blatt 5 pdf       
Blatt 6 pdf       
Blatt 7 pdf       
Blatt 8 pdf       
Blatt 9 pdf
Blatt 10 pdf
Blatt 11 pdf       
Blatt 12 pdf       



SS2014 Lecture: Computability and complexity


Monday 16:30-18:00, KGRC Room 101 (Währinger Straße 25, 2nd floor).

The course offers an introduction to the theory of optimal algorithms, optimal proof systems and the NP versus coNP question: contents.

A student's handwritten lecture notes: pdf      (last update 12.06.2014)

Literature Course evaluation: pdf



SS2014 Vorlesung: Grundbegriffe der mathematischen Logik


Mittwochs 15.00-17.00 Uhr, Hörsaal 13, Oskar-Morgenstern-Platz 1, 2.Stock.

Vorlesungsevaluation: pdf



WS2013 Lecture: Introduction to theoretical computer science


Friday 16:00-18:30, KGRC Room 101 (Währinger Straße 25, 2nd floor).

Lecture notes pdf

Course evaluation: pdf



WS2013 Proseminar: Einführung in die mathematische Logik


Freitag 14:00-15:30, KGRC Raum 101 (Währinger Straße 25, 2ter Stock).

Das Proseminar ist eine gemeinsame Veranstaltung mit Stefan Hoffelner und behandelt Übungsbeispiele zur Vorlesung Einführung in die mathematische Logik von Jakob Kellner.

Übungsblatt 1     pdf        (Flussdiagramme, partielle Rekursivität)
Übungsblatt 2     pdf        (Beweisbarkeit, Substrukturen, Homomorphismen)
Übungsblatt 3     pdf        (Termstrukturen, elementare Substrukturen, Kompaktheitssatz, Nichtstandardanalysis)
Übungsblatt 4     pdf        (Satz von Herbrand, pränexe Normalform, Sigma1-Formeln)
Übungsblatt 5     pdf        (Sigma0-Induktion, Satz von Parikh, Sigma1-definierbare Funktionen)
Übungsblatt 6     pdf        (Unvollständigkeitssätze von Gödel und Rosser)
Übungsblatt 7     pdf        (erste Übungen Mengenlehre)
Übungsblatt 8     pdf        (Fundierung, Ackermann Interpretation)
Übungsblatt 9     pdf        (Königs Lemma, ordinale Arithmetik, Hartogsches Aleph, Klassenform des Fundierungsaxioms)
Übungsblatt 10   pdf        (nichtstandard natürliche Zahlen, Cantorsche Normalform, Mostowski Kollaps für Klassen, Rang)
Übungsblatt 11   pdf        (Schröder-Bernstein, Fixpunkte normaler Funktionen, Aleph versus Hartogsches Aleph)
Übungsblatt 12   pdf        (Auswahlaxiom, Satz von Tarski, Konfinalität)



SS2013 Lecture: Introduction to theoretical computer science


Tuesday 17:00-19:30, KGRC Room 101 (Währinger Straße 25, 2nd floor), starts March 12.

Lecture notes pdf



WS2012 Lecture: Forcing with random variables


Wednesday 10:45-12:15, KGRC Room 101 (Währinger Straße 25, 2nd floor).

Scott and Solovay observed that Cohen's method of forcing can be interpreted as a method to construct Boolean valued models.
Scott proved the independence of CH from a higher order theory of the reals by interpreting first-order variables of the language over random reals, i.e. real valued random variables.
The course starts with a review of Scott's construction and then treats Krajicek's recent book where such forcing with random variables is developed as a method to construct Boolean valued models for weak theories of arithmetic.

The course adresses master students in mathematical logic.

Contents: pdf

Literature Course evaluation: pdf



SS2012 Lecture: Introduction to theoretical computer science


Tuesday 15:15-17:45, KGRC Room 101 (Währinger Straße 25, 2nd floor).

Lecture notes: pdf

Course evaluation: pdf



SS2012 Übungen: Grundbegriffe der mathematischen Logik


Montag 17:00-18:00, Hörsaal 3, UZA 2.

Übungsblatt 1   pdf
Übungsblatt 2   pdf       
Übungsblatt 3   pdf
Übungsblatt 4   pdf
Übungsblatt 5   pdf       
Übungsblatt 6   pdf
Übungsblatt 7   pdf
Übungsblatt 8   pdf
Übungsblatt 9   pdf
Übungsblatt 10 pdf