В математике теорема Гёделя об ускорении , доказанная Гёделем ( 1936 ), показывает, что существуют теоремы, доказательства которых можно значительно сократить, работая с более мощными аксиоматическими системами.
Курт Гёдель показал, как найти явные примеры утверждений в формальных системах, которые доказуемы в этой системе, но чье кратчайшее доказательство невообразимо длинно. Например, утверждение:
- «Это утверждение не может быть доказано в арифметике Пеано с помощью меньшего количества символов гуголплекса »
доказуемо в арифметике Пеано (PA), но в кратчайшем доказательстве есть по крайней мере гуголплексные символы с помощью аргумента, аналогичного доказательству первой теоремы Гёделя о неполноте : если PA непротиворечиво, то оно не может доказать утверждение с помощью менее чем гуголплексных символов, поскольку существование такого доказательства само по себе было бы теоремой PA, противоречие. Но простое перечисление всех строк длины до гуголплекса и проверка того, что каждая такая строка не является доказательством (в PA) утверждения, дает доказательство утверждения (которое обязательно длиннее, чем символы гуголплекса).
Утверждение имеет короткое доказательство в более мощной системе: фактически доказательство, приведенное в предыдущем абзаце, является доказательством в системе арифметики Пеано плюс утверждение «Арифметика Пеано непротиворечива» (которое, согласно теореме о неполноте, не может быть доказано в арифметике Пеано).
В этом аргументе арифметика Пеано может быть заменена любой более мощной согласованной системой, а гуголплекс может быть заменен любым числом, которое можно кратко описать в системе.
Харви Фридман нашел несколько явных естественных примеров этого явления, дав некоторые явные утверждения в арифметике Пеано и других формальных системах, кратчайшие доказательства которых смехотворно длинные ( Smoryński 1982 ). Например, заявление
- "существует такое целое число n , что если существует последовательность корневых деревьев T 1 , T 2 , ..., T n такая, что T k имеет не более k +10 вершин, то некоторое дерево может быть гомеоморфно вложено в более поздний один"
доказуемо в арифметике Пеано, но кратчайшее доказательство имеет длину не менее A (1000), где A (0) = 1 и A ( n +1) = 2 A ( n ) . Утверждение является частным случаем теоремы Крускала и имеет краткое доказательство в арифметике второго порядка .
Если взять арифметику Пеано вместе с отрицанием вышеприведенного утверждения, то получится противоречивая теория, кратчайшее противоречие которой невообразимо [ требуется дальнейшее объяснение ] .
Смотрите также
Рекомендации
- Buss, Samuel R. (1994), "О теоремах Гёделя о длинах доказательств I. Количество линий и для ускорения арифметики." Журнал символической логики , 59 (3): 737-756, DOI : 10,2307 / 2275906 , ISSN 0022-4812 , JSTOR 2275906 , MR 1295967
- Басс, Самуэль Р. (1995), "О теоремах Гёделя о длине доказательств. II. Нижние оценки для распознавания доказуемости k символов", Clote, Peter; Реммель, Джеффри (ред.), Возможная математика, II (Итака, Нью-Йорк, 1992) , Progr. Comput. Sci. Прил. Logic, 13 , Бостон, Массачусетс: Birkhäuser Boston, стр. 57–90, ISBN 978-0-8176-3675-3, MR 1322274
- Гёдель, Курт (1936), «Über die Länge von Beweisen» , Ergebnisse eines Mathematischen Kolloquiums (на немецком языке), 7 : 23–24, ISBN 9780195039641Перепечатано с английским переводом в томе 1 его собрания сочинений.
- Сморынский, C. (1982), "Разновидности древесного опыта", Матем. Интеллидженсер , 4 (4): 182-189, DOI : 10.1007 / bf03023553 , МР 0685558