Vectorization hierarchies of some graph quantifiers

Citation
L. Hella et J. Nurmonen, Vectorization hierarchies of some graph quantifiers, ARCH MATH L, 39(3), 2000, pp. 183-207
Citations number
27
Categorie Soggetti
Mathematics
Journal title
ARCHIVE FOR MATHEMATICAL LOGIC
ISSN journal
09335846 → ACNP
Volume
39
Issue
3
Year of publication
2000
Pages
183 - 207
Database
ISI
SICI code
0933-5846(200004)39:3<183:VHOSGQ>2.0.ZU;2-8
Abstract
We give a sufficient condition for the inexpressibility of the k-th extende d vectorization of a generalized quantifier Q in FO(Q(k)), the extension of first-order logic by all k-ary quantifiers. The condition is based on a mo del construction which, given two FO(Q(1))-equivalent models with certain a dditional structure, yields a pair of FO(Q(k))-equivalent models. We also c onsider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity and planarity.