A combinatorial version of the Svenonius theorem on definabilityстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 17 мая 2016 г.
Аннотация:The Svenonius theorem describes the (first-order) definability in a structure in terms of permutations preserving the relations of elementary extensions of the structure. In the present article, we prove a version of this theorem using permutations of sequences over the original structure (these are permutations of sequences of tuples of the structure elements as well). We say that such a permutation ϕ almost preserves a relation if for every sequence of its arguments the value of the relation on an n-th element of the sequence and on its image under ϕ coincide for almost all numbers n. We prove that a relation is definable in a structure iff the relation is almost preserved by all permutations almost preserving the relations of the structure. This version limits consideration to the original structure only and does not refer to any logical notion, such as ‘elementary equivalence’.