Кудинов О. В., Селиванов В. Л., Ярцева Л. В.
Определимость в структуре слов с отношением включения

Разработана теория определимости (первого порядка) в структуре слов с отношением включения, аналогичная развитым ранее теориям для h-квазипорядка на конечных k-размеченных лесах и для структуры слов с инфиксным порядком. В частности, показано, что любой элемент определим (при условии, что слова длины 1 и 2 взяты как параметры) и что теория первого порядка этой структуры атомна и вычислимо изоморфна арифметике первого порядка. Охарактеризована группа автоморфизмов этой структуры и показано, что любой арифметический предикат, инвариантный относительно автоморфизмов, определим в этой структуре.

Kudinov O. V., Selivanov V. L., Yartseva L. V.
Definability in the structure of words with the inclusion relation

We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the h-quasiorder of finite k-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 or 2 are taken as parameters), the first-order theory of the structure is atomic and computably isomorphic to the first-order arithmetic. We also characterize the automorphism group of the structure and show that every predicate invariant under the automorphisms of the structure is definable in the structure.

Полный текст статьи / Full texts:

• PDF file (420 KB)
• PostScript file (790 KB)