RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2010 Volume 51, Number 3, Pages 575–583 (Mi smj2108)

This article is cited in 1 paper

Definability in the structure of words with the inclusion relation

O. V. Kudinova, V. L. Selivanovb, L. V. Yartsevab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b A. P. Ershov Institute of Informatics Systems Sib. Br. RAS, Novosibirsk

Abstract: 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.

Keywords: subword, infix order, definability, automorphism, least fixed point, first-order theory, bi-interpretability.

UDC: 510.53+512.562

Received: 01.03.2010


 English version:
Siberian Mathematical Journal, 2010, 51:3, 456–462

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024