Abstract
We prove that connectivity of finite graphs is not expressible in the extension of first-order logic by any set of unary generalized quantifiers. On the other hand, we show that connectivity is definable by the simplest partially ordered connective D 1,1. As a consequence, D 1,1 is not definable in terms of unary quantifiers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
J. Barwise, Some applications of Henkin quantifiers, Israel Journal of Mathematics 25 (1976), pp. 47–63.
A. Blassand Y. Gurevich, Henkin quantifiers and complete problems, Annals of Pure and Applied Logic 32 (1986), pp. 1–16.
H. Enderton, Finite partially ordered quantifiers, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 16 (1970) pp. 393397.
R. Fagin, Monadic generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21 (1975), pp. 89–96.
L. Hella, Definability hierarchies of generalized quantifiers, Annals of Pure and Applied Logic 43 (1989), pp. 235–271.
L. Henkin, Some remarks on infinitely long formulas, in: Infinitistic Methods, Warsaw, 1961, pp. 167–183.
M. Krynickiand A. Lachlan, On the semantics of the Henkin quantifier, Journal of Symbolic Logic 44 (1979), pp. 184–200.
G. Sanduand J. Vaananen, Partially ordered connectives, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 38 (1992), pp. 361–372.
W. Walkoe Finite partially-ordered quantifiers Journal of Symbolic Logic 35 (1970) pp. 535–555.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Hella, L., Sandu, G. (1995). Partially Ordered Connectives and Finite Graphs. In: Krynicki, M., Mostowski, M., Szczerba, L.W. (eds) Quantifiers: Logics, Models and Computation. Synthese Library, vol 249. Springer, Dordrecht. https://doi.org/10.1007/978-94-017-0524-0_4
Download citation
DOI: https://doi.org/10.1007/978-94-017-0524-0_4
Publisher Name: Springer, Dordrecht
Print ISBN: 978-90-481-4540-9
Online ISBN: 978-94-017-0524-0
eBook Packages: Springer Book Archive