Автоустойчивость автоматных представлений ординалов и линейных порядков низкого ранга

Abstract

В [10] показано, что автоматные линейные порядки имеют конечный FC-ранг. В этой работе дан положительный ответ на вопрос о существовании вычислимого изоморфизма между автоматными представлениями ординалов и линейных порядков FC-ранга не выше 2. Приведены примеры автоматных линейных порядков с достаточно сложной структурой. Доказывается теорема о том, что любой автоматный линейный порядок определим формулами первого порядка с дополнительным квантором ∃∞ в подходящем автоматном линейном порядке FC-ранга 1.