RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2010, том 51, номер 3, страницы 575–583 (Mi smj2108)

Эта публикация цитируется в 1 статье

Определимость в структуре слов с отношением включения

О. В. Кудиновa, В. Л. Селивановb, Л. В. Ярцеваb

a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Институт систем информатики им. А. П. Ершова СО РАН, Новосибирск

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

Ключевые слова: подслово, инфиксный порядок, определимость, автоморфизм, наименьшая неподвижная точка, теория первого порядка, биинтерпретируемость.

УДК: 510.53+512.562

Статья поступила: 01.03.2010


 Англоязычная версия: Siberian Mathematical Journal, 2010, 51:3, 456–462

Реферативные базы данных:


© МИАН, 2024