Name
Abstract | ||
|---|---|---|
We say that a first order formula Phi distinguishes a structure M over a vocabulary L from another structure M ' over the same vocabulary if Phi is true on M but false on M '. A formula Phi defines an L-structure M if Phi distinguishes M from any other non-isomorphic L-structure M '. A formula Phi identifies an n-element L-structure M if Phi distinguishes M from any other non-isomorphic n-element L-structure M '. We prove that every n-element structure M is identifiable by a formula with quantifier rank less than (1-1/2k)n + k(2) - k + 4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schonfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure At is identifiable by a formula in the Bernays-Schonfinkel class with less than (1 - 1/2k(2)+2)n + k quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than n - root n + k(2) + k quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total n - O(root n) quantifiers are necessary. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.2178/jsl/1120224721 | JOURNAL OF SYMBOLIC LOGIC |
Keywords | DocType | Volume |
quantifiers are necessary. | Journal | 70 |
Issue | ISSN | Citations |
2 | 0022-4812 | 6 |
PageRank | References | Authors |
0.86 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Pikhurko | 1 | 318 | 47.03 |
| Oleg Verbitsky | 2 | 191 | 27.50 |