Properties of Almost All Graphs and Generalized Quantifiers

Issue title: Bridging Logic and Computer Science: to Johann A. Makowsky for his 60th birthday

Article type: Research Article

Authors: Dawar, Anuj | Grädel, Erich

Affiliations: University of Cambridge, Cambridge CB3 0FD, England. E-mail: [email protected] | RWTH Aachen University, D-52056 Aachen, Germany. E-mail: [email protected]

Abstract: We study 0-1 laws for extensions of first-order logic by Lindström quantifiers. We state sufficient conditions on a quantifier Q expressing a graph property, for the logic FO[Q] – the extension of first-order logic by means of the quantifier Q – to have a 0-1 law. We use these conditions to show, in particular, that FO[Rig], where Rig is the quantifier expressing rigidity, has a 0-1 law. We also show that extensions of first-order logic with quantifiers for Hamiltonicity, regularity and self-complementarity of graphs do not have a 0-1 law. Blass and Harary pose the question whether there is a logic which is powerful enough to express Hamiltonicity or rigidity and which has a 0-1 law. It is a consequence of our results that there is no such regular logic (in the sense of abstract model theory) in the case of Hamiltonicity, but there is one in the case of rigidity. We also consider sequences of vectorized quantifiers, and show that the extensions of first-order logic obtained by adding such sequences generated by quantifiers that are closed under substructures have 0-1 laws. The positive results also extend to the infinitary logic with finitely many variables.

DOI: 10.3233/FI-2010-232

Journal: Fundamenta Informaticae, vol. 98, no. 4, pp. 351-372, 2010