Laboratory of Mathematical Logic at PDMI

Пятница, 31 октября, комната 106. Начало в 19:00.

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

Тема: Продолжение доклада о недоказуемости.

Abstract

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

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

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

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

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