Fixpoints and Induction in Logic and Computer Science

 

Vorlesung im Sommersemester 2022

 
 

Termine

Vorlesung:

 

Tutorium:

 

 
 

Inhalt


This course is about the proof method of induction, and about the theory of fixpoints on ordered structures, complete lattices in particular. Topics covered are:

  • Induction on natural numbers, structural induction, well-founded induction
  • Tarski's fixpoint theorem for monotonic functions on complete lattices and variations on complete partial orders
  • Examples from games, probability theory (Markov chains and decision processes), program semantics and verification, automata theory and formal languages
  • Computation of fixpoints by iteration on finite lattices
  • Characterization of fixpoints on infinite lattices for continuous functions and arbitrary functions
  • Ordinal numbers, transfinite induction, well-ordering theorem
  • First-order logic with fixpoints
  • The role of induction in incompleteness theorem for Peano arithmetic

Voraussetzungen

It is assumed that students are familiar with basics in discrete mathematics, automata theory, computability, and mathematical logic, as taught in the corresponding bachelor courses in computer science at RWTH Aachen.

 

Organisation

Termine

Dozent

Christof Löding

 

Prüfung

Es ist eine mündliche Prüfung geplant. Abhängig von der Zahl der teilnehmenden Studierenden kann es auch eine Klausur werden.

 

Externe Links