Unary quantifiers on finite models (Q1361404)

A simple unary or monadic quantifier is a class of certain structures closed under isomorphisms. All models under consideration are assumed to be finite. A quantifier \(Q\) is said to be definable in terms of a set \textbf{Q} of quantifiers if \(Q\) is the class of models of a sentence of the extension \(FO({\mathbf Q})\) of a first-order logic \(FO\) by the set \({\mathbf Q}\). The family of all logics of the form \(FO({\mathbf Q}\)), where \({\mathbf Q}\) is a set of monotone quantifiers, plays an important role and will be denoted by \textbf{Mon}. The concept of a boundedly oscillated quantifier is a weakening of the concept of monotonicity. Then the following results are proved. A quantifier is definable in terms of monotone quantifiers if and only if it is boundedly oscillating. Let \({\mathbf Q}\) be a finite set of bounded monotone quantifiers. Let \(Q'\) be a monotone quantifier. Then \(Q'\) is definable in \(FO({\mathbf Q})\) if and only if \(Q'\) is bounded and the canonical coloring \(\beta_{\mathbf Q}\) of \({\mathbf N}\) eventually refines \(\beta_{Q'}\). Let \(Q_f\) be a monotone quantifier satisfying \[ \lim_{n \to\infty} f(n)= \lim_{n\to \infty} \bigl(n-f(n) \bigr)= \infty \] and \[ \lim_{n \to\infty} \bigl(f(n)- \lfloor n/2 \rfloor \bigr)= \infty \quad \text{or} \quad \lim_{n\to \infty} \bigl(\lfloor n/2 \rfloor- f(n)\bigr) =\infty. \] Then a monotone quantifier \(Q_g\) is definable in \(FO(Q_f)\) iff \(Q_g\) is first-order definable or there is a constant \(a\in{\mathbf Z}\) and a number \(m\in{\mathbf N}\) fulfilling \[ \forall n\geq m\bigl(g(n) =f(n) +a\bigr) \quad \text{or} \quad \forall n\geq m\bigl(g(n) =n-f(n) +a\bigr). \] In the last section a generalization of the preceding results to non-monotone and non-simple unary quantifiers is given.