Vectorization hierarchies of some graph quantifiers (Q1568709)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vectorization hierarchies of some graph quantifiers |
scientific article |
Statements
Vectorization hierarchies of some graph quantifiers (English)
0 references
13 March 2001
0 references
If \(Q\) is a generalized quantifier and \(k\geq 1\), denote by \(Q^k\) the \(k\)th vectorization of \(Q\). The vectorization hierarchy of \(Q\) is unbounded if there are arbitrarily large natural numbers \(k\) such that \(Q^k\) is not expressible in the extension \(\text{FO} (\{Q^l|l<k\})\) of first-order logic FO. Conditions on \(Q\) are presented that guarantee that the vectorization hierarchy is unbounded. Applications to concrete quantifiers are given.
0 references
Ehrenfeucht-Fraissé games
0 references
finite model-theory
0 references
generalized quantifier
0 references
vectorization hierarchy
0 references