Диагонализация в арифметике и теория истины по Крипке. Семинар 4

Зафиксируем какую-нибудь эффективную нумерацию $\#$ всех предложений в языке элементарной арифметики. Восходящая к Курту Гёделю лемма о диагонализации гласит: для каждой арифметической формулы $F(x)$ можно найти (арифметическое) предложение $G$ такое, что эквивалентность $F(\#G)$ и $G$ выводима из конечного набора простых аксиом, называемого «минимальной» арифметикой.
Из леммы о диагонализации легко следует теорема Альфреда Тарского о неопределимости истины: множество всех (номеров) предложений, истинных в стандартной модели арифметики, не определимо в самой этой модели. То же самое верно и для обогащений стандартной модели. Стало быть, если мы хотим добавить к языку арифметики или другому достаточно богатому языку истинностный предикат $T$ (применимый к любым предложениям в расширенном языке), то $T$ должен принимать как минимум три значения: «истинно», «ложно» и «неопределено», где последнее, в частности, соответствует парадоксу лжеца и ему подобным утверждениям.
Наиболее известный трёхзначный подход к формальной теории истины был предложен Солом Крипке. Здесь роль допустимых (трёхзначных) интерпретаций истинностного предиката $T$ играют наименьшие неподвижные точки специальных монотонных операторов. Математически данный подход вдохновлён методами абстрактной теории вычислимости и теории моделей, однако исходные постановки задач связаны с семантическими проблемами в естественных языках.
Желательно знакомство с базовыми понятиями математической логики и теории множеств. В целом я постараюсь сделать курс максимально понятным (даже если человек ранее не слышал, например, слова «ординал»). Основные идеи будут изложены общедоступным языком.

План
1. «Минимальная» арифметика и представимость в ней. Лемма о диагонализации в арифметике.
2. Теорема Тарского о неопределимости истины (в арифметике) и её обобщения. Теорема Кнастера—Тарского о монотонных функциях на полных решётках.
3. Абстрактные индуктивные определения. Операторы скачка по Крипке и их замыкающие ординалы.
4. Конструктивные ординалы и их нотации по Клини. Ранги истинных формул. Сложность истины по Крипке.

Дополнительная литература
1. G.S. Boolos, J.P. Burgess, R.C. Jeffrey. Computability and Logic. 5th Edition. Cambridge University Press, 2007.
2. G.E. Sacks. Higher Recursion Theory. Springer, 1990.
3. S.O. Speranski. Notes on the computational aspects of Kripke’s theory of truth. Studia Logica 105(2), 407–429, 2017.