Быстрорастущие функции и недоказуемые комбинаторные утверждения

В математической логике важную роль играют результаты о недоказуемости просто формулируемых комбинаторных утверждений в теориях, аксиоматизирующих значительные части математики. В докладе будет приведен новый пример утверждения комбинаторного характера, недоказуемого средствами предикативного анализа (и в системе ${\rm ATR}_0$ арифметики второго порядка). Этот пример является естественным обобщением “принципа Червя”, известного для арифметики Пеано, но значительно сильнее последнего. Он приводит к вычислимым функциям, порядок роста которых определяется ординалом $\Gamma_0$ Фефермана–Шютте.