Семинар 27 октября 2003 года

Понедельник, 27 октября, комната 412. Начало в 15:30.

Докладчик: А. Бовыкин.

Тема: Как доказать, что что-то недоказуемо про натуральные числа.

Abstract

В первой (простой) части доклада будет показано, как получать функции аккермановского роста с помощью теоретико-модельных конструкций.

Во второй части будет предъявлено семейство комбинаторных принципов, истинность которых недоказуема в Арифметике Пеано.

Фиксируем функцию

, принимающую ненулевые значения бесконечное число раз. Назовем функцию

F-регрессивной, если для всех

,

.

Назовем множество

мин-одноцветным для

, если

для всех

и

.

Введем комбинаторный принцип

: для всякого

найдется

такое что для всякой

-регрессивной функции

, определенной на

, найдется мин-одноцветное подмножество

, такое, что

и

.

Будет дано полное доказательство того, что

недоказуемо в

для всех

, где

.