Moritz Müller, teaching

Moritz Müller

moritz.mueller@univie.ac.at

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

Arora, Barak, Computational Complexity - A Modern Approach, Cambridge University Press, 2009.
Goldreich, Introduction to Complexity Theory - Lecture Notes for a Two-Semester course. (here)
Papadimitriou, Computational Complexity, Addison Wesley, 1994.

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

Saturation of free ultrapowers pdf
Beame, A Switching Lemma Primer, Technical Report UW-CSE-95-07-01, University of Washington, 1994. (here)
Hajek, Pudlak, Metamathematics of First-order Arithmetic, Perspectives in Mathematical Logic, Volume 3, Springer, 1998. (here)
Krajicek, Forcing with Random Variables and Proof Complexity, The London Mathematical Society Lecture Note Series 382, Cambridge, 2011. (here)
Scott, A Proof of the Independence of the Continuum Hypothesis, Theory of Computing Systems 1(2):89-111, 1967. (here)

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. Prolog	general 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

K. Tent and M. Ziegler, A course in model theory, Lecture Notes in Logic, Cambridge University Press, ASL 2012.
M. Ziegler, Modelltheorie I, here
K. Tent and M. Ziegler, Baldwin-Lachlan-Theorem, here

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

Martin Ziegler, Mathematische Logik, Reihe Mathematik Kompakt, Birkhäuser Verlag, 2010.
Martin Ziegler, Mathematische Logik, Vorlesungsskript SS00 (hier)
Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas: Einführung in die mathematische Logik, Spektrum Verlag, 5. Auflage, 2007.

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

A. Bogdanov, K. Talwar, A. Wan, Hard instances for satisfiability and quasi-one-way functions. Proceedings Innovations in Computer Science (ICS'10): 290-300, 2010.
Y. Chen, J. Flum, On optimal inverters, The Bulletin of Symbolic Logic 20(1): 1-23, 2014.
Y. Chen, J. Flum, M. Müller, Hard instances of algorithms and proof systems. ACM Transactions on Computation Theory 6(2): Article No. 7, 2014.
Y. Chen, J. Flum, M. Müller, Consistency, optimality and incompleteness, Annals of Pure and Applied Logic, 164(12), 1224-1235, 2013.
D. Gutfreund, R. Shaltiel, A. Ta-Shma's, If NP languages are hard on the worst-case, then it is easy to find their hard instances''. 20th Conference on Computational Complexity (CCC'05): 243-257, 2005.
E. A. Hirsch, Optimal acceptors and optimal proof systems. 7th Theory and Applications of Models of Computation (TAMC'10): 28-39, 2010.
J. Krajicek, A note on SAT algorithms and proof complexity, Information Processing Letters 112: 490-493 2012
J. Messner, On the simulation order of proof systems. Doctoral Dissertation, University of Ulm, 2001.
N. Vereshchagin, An improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances''. 8th Computer Science Symposium in Russia (CSR'13), LNCS 7913: 203-211, 2013.

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

Beame, A Switching Lemma Primer, Technical Report UW-CSE-95-07-01, University of Washington, 1994. (here)
Hajek, Pudlak, Metamathematics of First-order Arithmetic, Perspectives in Mathematical Logic, Volume 3, Springer, 1998. (here)
Krajicek, Forcing with Random Variables and Proof Complexity, The London Mathematical Society Lecture Note Series 382, Cambridge, 2011. (here)
Scott, A Proof of the Independence of the Continuum Hypothesis, Theory of Computing Systems 1(2):89-111, 1967. (here)

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