Axiomatization of ML and Cheq
GaĆ«lle Fontaine
Abstract:
In this thesis we investigate the connection between two intermediate logics:
Medvedev's logic and the logic of chequered subsets. The former has been
introduced by Medvedev in the sixties as a a logic of finite problems and the
later, by van Benthem, Bezhanishvili and Gehrke in 2003 as a spatial logic of
the chequered subsets of R^\infty. Litak (2004) conjectured that these two
logics are closely related; in particular, that Medvedev's logic is finitely
axiomatizable over thelogic of chequered subsets.
In this thesis we refute Litak's conjecture by showing that Medvedev's logic is
not finitely axiomatizable over the logic of chequered subsets. We also
reproduce the original proof of Maksimova, Shehtman and Skvorcov (1978) that
Medvedev's logic is not finitely axiomatizable and prove that the logic of
chequered subsets is not axiomatizable with four variables.