Monadic Logic of Order over Naturals has no Finite Base
Danièle Beauquier · Journal of Logic and Computation · 2002
A major result concerning Temporal Logics (T L) is Kamp's theorem which states that the temporal logic over the pair of modalities X until YandXsinceY is expressively complete for the first‐order fragment of monadic logic of order over the natural numbers. We show that there is no finite set of modalities B such that the temporal logic over B and monadic logic of order have the same expressive power over the natural numbers. As a consequence of our proof, we obtain that there is no finite base temporal logic which is expressively complete for the μ‐calculus.