Graduate Student Seminar, 4:30pm March 15, 2004; HH127


Pantelis Eleftheriou


"I am lying"


The basic ingredients of the proof of Godel's Incompleteness Theorem are self-reference and coding. We will spot places where the first appears throughout logic, beginning our route with Cantor's 'naive' set theory, his diagonal arguments and considerations of the infinite. Russell's paradox comes next, throwing doubts in Cantor's naiveness, and making imperative the need for a formal treatment of set theory. When the 'axiomatic set theory' was being proposed by Zermelo, Hilbert had already suggested his program of formalizing, if not all of mathematics, an as large part of it as possible, in some axiomatic theory, and then establishing its consistency by means of the theory itself. Godel's Incompleteness Theorem marks the end of Hilbert's dream. In order to sketch the proof of this theorem, we introduce notions from basic logic, among others that of a computable function, which is related with the coding part of the proof of Godel's theorem. Time permitting, we conclude with a recent approach that treats all self-referential 'paradoxes' in a uniform way.

This talk will not be very historically sensitive. With destination Godel's theorem, and self-reference our guide, we will trip through basic logic.

To volunteer to give a talk, or for any other questions regarding this schedule, contact Wesley Calvert