Cool Logic

Sam van Gool (RU Nijmegen and LIAFA Paris)

A Topological Proof of Gödel's Completeness Theorem for First-Order Logic

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

This will be a talk about an old proof of an even older theorem. I will try to explain why it is still worth talking about today.

Logic has traditionally been approached from two angles: one of these is syntactic (proof-theoretic) in nature, the other is of a semantic (model-theoretic) kind. Gödel established in 1929 that the syntactic and semantic approach for first-order logic are intimately connected: his celebrated Completeness Theorem says that a first-order sentence is provable if and only if it is true in all models. The proof that is usually taught in logic courses (or at least in the logic courses that I attended) makes use of Henkin models and witnesses.

However, in the fifties of the previous century, H. Rasiowa and R. Sikorski gave a different proof of Gödel's Completeness Theorem, using methods of a topological nature. Their proof ultimately relies on the Baire Category Theorem, which is mainly known in mathematics for its powerful applications in real and functional analysis. Therefore, the application of Baire's theorem to prove this fundamental result in logic is a surprising and interesting one. Also, these methods subsequently enabled the same authors to establish a new completeness theorem for the intuitionistic version of first-order logic.

The main aim of this talk will be to convey the beauty (cool-ness?) of this topological method introduced by Rasiowa and Sikorski. In order to make this talk accessible to all logic students, I will not assume much prior knowledge of topology. In particular, I will try to explain - at least at an intuitive level - the contents of both Stone's representation theorem and the Baire category theorem.