Теорема Гёделя об ускорении
В математике можно значительно сократить , теорема Гёделя об ускорении , доказанная Гёделем ( 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 А ( н ) . Это утверждение является частным случаем теоремы Краскала и имеет краткое доказательство в арифметике второго порядка .
Если взять арифметику Пеано вместе с отрицанием приведенного выше утверждения, можно получить противоречивую теорию, самое короткое известное противоречие которой эквивалентно длине.
См. также
[ редактировать ]Ссылки
[ редактировать ]- Басс, Сэмюэл Р. (1994), «О теоремах Гёделя о длине доказательств. I. Число строк и ускорение арифметики», Журнал символической логики , 59 (3): 737–756, doi : 10.2307/2275906 , ISSN 0022-4812 , JSTOR 2275906 , МР 1295967 , S2CID 914043
- Басс, Сэмюэл Р. (1995), «О теоремах Гёделя о длине доказательств. II. Нижние оценки для распознавания доказуемости k-символов», в Клот, Питер; Реммель, Джеффри (ред.), Выполнимая математика, II (Итака, Нью-Йорк, 1992) , Progr. Вычислить. наук. Прил. Логика, том. 13, Бостон, Массачусетс: Birkhäuser Boston, стр. 57–90, ISBN. 978-0-8176-3675-3 , МР 1322274
- Гёдель, Курт (1936), «О длине доказательств» , Результаты математического коллоквиума (на немецком языке), 7 : 23–24, ISBN 9780195039641 , Перепечатано с английским переводом в первом томе собрания его сочинений.
- Смориньский, К. (1982), «Разновидности древесного опыта», Math. Intelligencer , 4 (4): 182–189, doi : 10.1007/bf03023553 , MR 0685558