Laboratory of Mathematical Logic at PDMI

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

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

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

Abstract

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

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

Фиксируем функцию $F(n)$, принимающую ненулевые значения бесконечное число раз. Назовем функцию $f(x_0, x_1,\ldots x_k)$ F-регрессивной, если для всех $x_0

Назовем множество $H$ мин-одноцветным для $f$, если $f(x_0, x_1,\ldots x_k)=f(x_0, y_1,\ldots y_k)$ для всех $x_0

Введем комбинаторный принцип $A^k_F$: для всякого $n$ найдется $N$ такое что для всякой $F$-регрессивной функции $f$, определенной на $\mathbb{N}^k$, найдется мин-одноцветное подмножество $H$, такое, что $|H|>n$ и $|H|>F(\min H)$.

Будет дано полное доказательство того, что $A^k_{\log^n}$ недоказуемо в $ISigma_k$ для всех $n$, где $log^n(x)=\underset{n}{\underbrace{\log(\log(\ldots(\log x))))}}$.