Возможность определения порядковых номеров в различных подписях
Недавно я изучал, как «выглядят» определяемые подмножества счетных ординалов с точки зрения простой логики первого порядка (а не теории множеств), снабженной различными способами «доступа» к структуре ординалов.
Например, у нас может быть подпись, состоящая только из реляционного символа 2-арности. $S$ которую мы интерпретируем в структуре $\mathcal{A}$ с базовым набором $\omega_1$ как набор $(\alpha,\beta)$ такой, что $\beta$ является преемником $\alpha$. Затем мы можем задать вопросы о том, какие подмножества$\mathcal{A}$ определяются предложениями логики первого порядка с этой сигнатурой, где подмножество $S\subset\mathcal{A}$ считается определимым, если есть логическое предложение первого порядка $\phi(x)$ для которых множество удовлетворяющих заданий $x$ является $S$. В нашем примере мы можем определить набор всех счетных порядковых порядковых номеров-преемников с помощью формулы$\exists y:S(y,x)$.
Мы также можем задать такие вопросы, как "какой наименьший порядковый номер $\alpha$ такой, что $\alpha$ неопределимо в том смысле, что $\{\alpha\}$ является неопределимым "и т.п. Например, мне удалось убедить себя, что подписью $\{<\}$ с очевидной интерпретацией в $\omega_1$ как "отношение меньше", наименьший неопределенный порядковый номер $\omega^\omega$ (хотя формально я еще не изложил свой аргумент).
У меня вопрос: кто-нибудь изучал подобные вопросы? Известно ли, что наименьший определяемый порядковый номер для различных других подписей, например$\{ADD(x,y,z)\}$ что верно для всех $x,y,z$ так что $x+y=z$, или даже другие сигнатуры с умножением, возведением в степень, функциями Веблена или другими? Есть ли какие-нибудь известные обобщения этих идей? Любая помощь или сопутствующая литература будут оценены.
Ответы
У меня недостаточно репутации, чтобы добавить комментарий. Следующая статья может быть вам полезна. Он содержит результаты, расширяющие работы Тарского, Мостовского и Донера, а также очень хороший исторический обзор и ссылки.
Buchi, Siefkes - Полное расширение монадической теории счетных порядков второго порядка.
Слабая монадическая логика второго порядка появляется уже в оригинальной работе Эренфойхта. Даже если вас интересуют исключительно результаты первого порядка, (слабая) монадическая логика второго порядка может сыграть роль.
Например, теория порядкового сложения первого порядка совпадает с теорией порядкового сложения первого порядка внутри $\omega^{\omega^{\omega}}$ (по Ehrenfeuct), а $(\omega^{\omega^{\omega}},+)$ является редукцией обобщенной степени $(\omega,+)$ с экспонентой, являющейся слабой монадической версией второго порядка $(\omega^{\omega},<)$(Теорема Фефермана-Воота - правильный инструмент, чтобы понять это). Для более подробной информации есть Томас-Эренфойхт, Воот и разрешимость слабой монадической теории преемника , все детали здесь правильные, но я думаю, что в выводах есть некоторые проблемы.
Есть также более свежие работы на стороне автоматов, такие как Cachat - Tree Automata Make Ordinal Theory Easy. Я ничего не знаю о его содержании, но если вы хотите получить исчерпывающий обзор местности, это может быть отправной точкой.