Home

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

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

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

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

Abstract

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

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

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

Введем комбинаторный принцип $ 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))))}} $.