|
Сибирский математический журнал, 2010, том 51, номер 3, страницы 575–583
(Mi smj2108)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Определимость в структуре слов с отношением включения
О. В. Кудиновa, В. Л. Селивановb, Л. В. Ярцеваb a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Институт систем информатики им. А. П. Ершова
СО РАН, Новосибирск
Аннотация:
Разработана теория определимости (первого порядка) в структуре слов с отношением включения, аналогичная развитым ранее теориям для $h$-квазипорядка на конечных $k$-размеченных лесах и для структуры слов с инфиксным порядком. В частности, показано, что любой элемент определим (при условии, что слова длины 1 и 2 взяты как параметры) и что теория первого порядка этой структуры атомна и вычислимо изоморфна арифметике первого порядка. Охарактеризована группа автоморфизмов этой структуры и показано, что любой арифметический предикат, инвариантный относительно автоморфизмов, определим в этой структуре.
Ключевые слова:
подслово, инфиксный порядок, определимость, автоморфизм, наименьшая неподвижная точка, теория первого порядка, биинтерпретируемость.
Статья поступила: 01.03.2010
Образец цитирования:
О. В. Кудинов, В. Л. Селиванов, Л. В. Ярцева, “Определимость в структуре слов с отношением включения”, Сиб. матем. журн., 51:3 (2010), 575–583; Siberian Math. J., 51:3 (2010), 456–462
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj2108 https://www.mathnet.ru/rus/smj/v51/i3/p575
|
Статистика просмотров: |
Страница аннотации: | 249 | PDF полного текста: | 86 | Список литературы: | 45 | Первая страница: | 4 |
|