Теорема Гёделя о неполноте и вторая теорема Гёделя[~ 1] — две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой формальной системы, в которой можно определить основные арифметические понятия: натуральные числа, 0, 1, сложение и умножение.
Первая теорема утверждает, что если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула.
Вторая теорема утверждает, что если формальная арифметика непротиворечива, то в ней невыводима формула, содержательно утверждающая непротиворечивость этой арифметики.
Обе эти теоремы были доказаны Куртом Гёделем в 1930 году (опубликованы в 1931) и имеют непосредственное отношение ко второй проблеме из знаменитого списка Гильберта.
Ещё в начале XX века Давид Гильберт провозгласил цель аксиоматизировать всю математику, и для завершения этой задачи оставалось доказать непротиворечивость и логическую полноту арифметики натуральных чисел. 7 сентября 1930 года в Кёнигсберге проходил научный конгресс по основаниям математики, и на этом конгрессе 24-летний Курт Гёдель впервые обнародовал две фундаментальные теоремы о неполноте, показавшие, что программа Гильберта не может быть реализована: при любом выборе аксиом арифметики существуют теоремы, которые невозможно ни доказать, ни опровергнуть простыми (финитными) средствами, предусмотренными Гильбертом, а финитное доказательство непротиворечивости арифметики невозможно[6].
Это выступление не было заявлено заранее и произвело ошеломляющий эффект, Гёдель сразу стал всемирной знаменитостью, а программа Гильберта по формализации основ математики потребовала срочного пересмотра. 23 октября 1930 года результаты Гёделя были представлены Венской академии наук Хансом Ханом. Статья с обеими теоремами («О принципиально неразрешимых положениях в системе Principia Mathematica и родственных ей системах») была опубликована в научном ежемесячнике Monatshefte für Mathematik und Physik в 1931 году. Хотя доказательство второй теоремы Гёдель дал только в виде идеи, его результат был настолько ясен и неоспорим, что не вызвал сомнений ни у кого. Гильберт сразу признал ценность открытий Гёделя. Первые полные доказательства обеих теорем были опубликованы в книге Гильберта и Бернайса «Основания математики» в 1938 году. В предисловии ко второму тому авторы признали, что для достижения поставленной цели финитных методов недостаточно, и добавили в число логических средств трансфинитную индукцию. В 1936 году Герхард Генцен сумел доказать непротиворечивость аксиом арифметики первого порядка, однако логическая полнота так и осталась недостижимой[6].