School of Technology and Computer Science Seminars

Topological Proof of the Compactness Theorem of Propositional Logic

by Prerona Chatterjee (School of Technology and Computer Science, TIFR)

Friday, September 9, 2016 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
The compactness theorem states that there is a model for an infinite set S of propositional formulas, if and only if, there is a model for every finite subset of S. Compactness is one of the central notions of logic and has a wide variety of applications mainly in Model Theory.

Kurt Gödel proved the countable compactness theorem in 1930 using Mathematical Logic which was generalised to the uncountable case by Anatoly Maltsev in 1936.

We will look at a topological proof of compactness, initially given for propositional logic with a set of countably infinite propositional constants and then generalised to a set of propositional constants of any size using Tychonoff Theorem. Here we give the general proof.