Unary quantifiers on finite models
type: Item
instance of: scholarly article
title: Unary quantifiers on finite models
zbMATH Open document ID: 0880.03014
DOI: 10.1023/A:1008209019899
author: Jouko Väänänen
published in: Journal of Logic, Language and Information
publication date: 1998-01-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03C80
Mathematics Subject Classification ID: 03C40
zbMATH DE Number: 1038919
zbMATH Keywords: definability
zbMATH Keywords: Ehrenfeucht-Fraïssé game
zbMATH Keywords: finite model
zbMATH Keywords: generalized quantifier
zbMATH Keywords: monotone quantifiers
zbMATH Keywords: boundedly oscillated quantifier
zbMATH Keywords: unary quantifiers
reviewed by: Hans-Jürgen Vogel
MaRDI profile type: Publication
full work available at URL: a:1008209019899
OpenAlex ID: W1489148631
description: scientific article; zbMATH DE number 1038919