OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation
Journal of Logic and Computation
Volume 12, Issue 2, April 2002: pp. 243253
Monadic Logic of Order over Naturals has no Finite Base
Danièle Beauquier^{1} and Alexander Rabinovich^{2}
^{1}Laboratory of Algorithmics, Complexity and Logic, Department of Informatics, University Paris12, France. Email: beauquier@univparis12.fr
^{2}Department of Computer Science, TelAviv University, Israel. Email: rabino@math.tau.ac.il
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 Y and X since Y is expressively complete for the firstorder 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 [mgr]calculus.
Keywords: Temporal logics; monadic logics
Table of Contents
FullText PDF (150 KB)
