Definability of polyadic lifts of generalized quantifiers (Q1361405)

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.