Cool Logic

Daniil Frumin and Guillaume Massas (ILLC)

The one and only diagonal argument.

May 20th at 17:30, in Science Park 107, F1.15

In this talk we would like to present the Lawvere’s fixed point theorem, which is a generalisation of the Cantor-Russell-Turing-Gödel argument in a sufficiently nice category. We will show how it implies straight forwardly Cantor’s theorem and Russell’s paradox, various versions of the Liar paradox. With a bit of work we will deduce Tarski’s result about the undefinability of truth and Gödel’s incompleteness theorem, as well as results from computability theory, such as the undecidability of the halting problem and the existence of fixed point combinators in λ-calculus.