Unary quantifiers on finite models (Q1361404): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Hans-Jürgen Vogel / rank | |||
Property / reviewed by | |||
Property / reviewed by: Hans-Jürgen Vogel / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:04, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Unary quantifiers on finite models |
scientific article |
Statements
Unary quantifiers on finite models (English)
0 references
28 January 1998
0 references
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.
0 references
definability
0 references
Ehrenfeucht-Fraïssé game
0 references
finite model
0 references
generalized quantifier
0 references
monotone quantifiers
0 references
boundedly oscillated quantifier
0 references
unary quantifiers
0 references