Definability of polyadic lifts of generalized quantifiers (Q1361405): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q1177860 |
||
Property / reviewed by | |||
Property / reviewed by: Hans-Jürgen Vogel / rank | |||
Revision as of 16:27, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Definability of polyadic lifts of generalized quantifiers |
scientific article |
Statements
Definability of polyadic lifts of generalized quantifiers (English)
0 references
28 January 1998
0 references
Associating a quantifier \(Q_f\) (by letting \(Q_f x\varphi\) mean there are at least \(f(n)\) elements \(x\) satisfying \(\varphi\), where \(n\) is the size of the universe) with a function \(f:\omega \to\omega\) one obtains a general form of a monotone quantifier of type \(\langle 1\rangle\). The authors define branching, Ramseyfication, and resumption as polyadic lifts of quantifiers as above and give definability characterizations over finite models for such polyadic quantifiers. Let \({\mathcal L}\) be a logic and let \({\mathbf Q}\) be a class of quantifiers. Then \({\mathcal L}({\mathbf Q})\) denotes the logic obtained from \({\mathcal L}\) by adding all quantifiers of \({\mathbf Q}\). The quantifier \(Q\) is definable in \({\mathcal L}({\mathbf Q})\), if the sentence \(Qx_1, \dots, x_n(P_1 (x_1), \dots, P_n (x_n))\) is logically equivalent to some \({\mathcal L}({\mathbf Q})\)-sentence in those predicate symbols. Moreover, in the first section a brief linguistic excursion for background and motivitation is included. In the second section the authors consider monotone quantifiers. If the function \(f\) is bonded, then for any \(k\geq 2\), the branching as well as the Ramseyfication of \(k\) monotone quantifiers \(Q_f\) are definable in \({\mathcal L}_{\omega \omega} (Q_f)\). The same assertion is true for the relativization \(Q_f^{\text{rel}}\) of \(Q_f\). Using a suitable Ehrenfeucht-Fraïssé game, the authors prove in sections 3, 4, and 5 a characterization of definability of branching, Ramseyfication, and resumption, respectively. The three proofs are quite different. In the concluding section 6 some open questions are raised.
0 references
generalized quantifier
0 references
monotone quantifier
0 references
branching
0 references
Ramseyfication
0 references
resumption
0 references
polyadic lifts
0 references
definability
0 references
finite models
0 references
polyadic quantifiers
0 references
relativization
0 references
Ehrenfeucht-Fraïssé game
0 references