Научно-образовательный центр при МИАН

Список спецкурсов на весенний семестр 2005/2006

Теория доказательств и формальная арифметика (1/2 года)

д.ф.-м.н. Лев Дмитриевич Беклемишев

Программа спецкурса

1. Элементарная арифметика и арифметика Пеано PA. Расширения с помощью определений. Элементарные функции. Арифметическая иерархия.
2. Вычислимость и сигма-определимость в арифметике. Первая теорема Геделя о неполноте.
3. Формула доказуемости, лемма о неподвижной точке, вторая теорема Геделя о неполноте.
4. Схемы рефлексии. Логика доказуемости.
5. Доказуемо тотальные вычислимые функции. Теорема Эрбрана и метод сколемизации. Характеризация доказуемо тотальных вычислимых функций в элементарной арифметике.
6. Генценовское исчисление, теорема об устранении сечения для логики предикатов. Индукция для перечислимых отношений и примитивно рекурсивные функции (теорема Парсонса).
7. Иерархии фрагментов PA. Ограниченные схемы и правила индукции.
8. Понятие k-непротиворечивости и k-доказуемости. Алгебры доказуемости. Свойство редукции для алгебр доказуемости. Доказательство непротиворечивости арифметики Пеано с помощью трансфинитной индукции.
9. Вполне упорядоченные множества и ординалы. Теорема о канторовской нормальной форме. Иерархии быстрорастущих функций. Характеризации доказуемо тотальных вычислимых функций в PA.
10. Независимые комбинаторные утверждения для арифметики Пеано: принцип Гудстейна, игра Геракл-Гидра, принцип Червя.
11. Теории второго порядка. Предикативный анализ.