Доказательство невозможности

В математике — теорема невозможности это теорема , которая демонстрирует, что проблема или общий набор проблем не могут быть решены. Они также известны как доказательства невозможности , отрицательные доказательства или отрицательные результаты . Теоремы о невозможности часто решают десятилетия или столетия работы, потраченной на поиск решения, доказывая, что решения нет . Доказать, что что-то невозможно, обычно гораздо сложнее, чем противоположную задачу, поскольку зачастую необходимо разработать доказательство, работающее в целом, а не просто показать конкретный пример. о невозможности Теоремы обычно выражаются как отрицательные экзистенциальные предложения или универсальные предложения в логике.

Иррациональность квадратного корня из 2 — одно из старейших доказательств невозможности. Он показывает, что невозможно выразить квадратный корень из 2 как отношение двух целых чисел . Еще одним последовательным доказательством невозможности было доказательство Фердинанда фон Линдеманна в 1882 году, которое показало, что проблема квадратуры круга не может быть решена. потому что число π трансцендентно циркуля (т. е. неалгебраично) и что только подмножество алгебраических чисел можно построить с помощью и линейки . Две другие классические задачи — трисекция общего угла и удвоение куба — также оказались невозможными в XIX веке, и все эти задачи послужили поводом для исследования более сложных математических структур.

Некоторые из наиболее важных доказательств невозможности, найденных в 20 веке, были связаны с неразрешимостью , которые показали, что существуют проблемы, которые вообще не могут быть решены никаким алгоритмом , причем одним из наиболее известных из них является проблема остановки . Теоремы Гёделя о неполноте были еще одним примером, раскрывающим фундаментальные ограничения доказуемости формальных систем.

В теории сложности вычислений такие методы, как релятивизация (добавление оракула ) , допускают «слабые» доказательства невозможности, поскольку методы доказательства, на которые не влияет релятивизация, не могут решить проблему P и NP . Другой метод — доказательство полноты класса сложности , которое доказывает сложность задач, показывая, что их так же трудно решить, как и любую другую задачу в классе. В частности, полная задача является неразрешимой, если одна из задач ее класса разрешима.

Методы доказательства

См. также: Виды доказательств.

Противоречие

Одним из широко используемых видов доказательства невозможности является доказательство от противного . В этом типе доказательства показано, что если предполагается, что утверждение, такое как решение определенного класса уравнений, верно, то с помощью дедукции можно показать, что выполняются две взаимно противоречивые вещи, например, что число является одновременно четным. и нечетный или одновременно отрицательный и положительный. Поскольку противоречие вытекает из исходного предположения, это означает, что предполагаемая посылка должна быть невозможной.

Напротив, неконструктивное доказательство утверждения о невозможности будет продолжаться, показывая, что всех недействительность возможных контрпримеров логически противоречива: по крайней мере один из пунктов в списке возможных контрпримеров должен фактически быть действительным контрпримером к гипотезе о невозможности. . Например, гипотеза о том, что иррациональная степень, возведенная в иррациональную степень, не может быть рациональной, была опровергнута , показав, что один из двух возможных контрпримеров должен быть действительным контрпримером, без указания того, какой именно.

По происхождению

Основная статья: Доказательство бесконечным спуском

Другой тип доказательства от противного — это доказательство по спуску, которое сначала предполагает, что что-то возможно, например положительное целое число. решение класса уравнений и, следовательно, должно существовать наименьшее решение (по принципу нулевого порядка ). Затем из предполагаемого наименьшего решения можно найти меньшее решение, что противоречит предпосылке о том, что первое решение было наименьшим из возможных, тем самым показывая, что исходная предпосылка о существовании решения должна быть ложной.

Контрпример

Очевидный способ опровергнуть гипотезу о невозможности — привести единственный контрпример . Например, Эйлер предположил , что по крайней мере n различных n ^й мощности необходимо было суммировать еще до n ^й власть. Гипотеза была опровергнута в 1966 году с помощью контрпримера, включающего подсчет только четырех разных пятых степеней, дающих в сумме еще одну пятую степень:

27 ⁵ + 84 ⁵ + 110 ⁵ + 133 ⁵ = 144 ⁵ .

Доказательство контрпримером — это форма конструктивного доказательства , заключающаяся в том, что демонстрируется объект, опровергающий утверждение.

Экономика

ранжированное

В теории социального выбора теорема невозможности Эрроу показывает, что невозможно разработать систему голосования с ранжированным выбором , которая была бы одновременно недиктаторской и удовлетворяла бы основному требованию рационального поведения , называемому независимостью от нерелевантных альтернатив .

Гиббарда: недиктаторские

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

Теорема Гиббарда -Саттертуэйта представляет собой особый случай, показывающий, что ни одна детерминированная система голосования не может быть полностью неуязвимой для стратегического голосования при любых обстоятельствах, независимо от того, как голосуют другие.

нечестные

можно Принцип раскрытия рассматривать как теорему о невозможности, показывающую «противоположность» теоремы Гиббарда в разговорном смысле: любую игру или систему голосования можно сделать устойчивой к стратегии, включив стратегию в механизм . Таким образом, невозможно спроектировать механизм , решение которого будет лучше, чем может быть получено правдивым механизмом .

Геометрия

Рациональное выражение m корней

Доказательство Пифагора около 500 г. до н. э. оказало глубокое влияние на математику. Это показывает, что квадратный корень из 2 не может быть выражен как отношение двух целых чисел. Доказательство разделило «числа» на две непересекающиеся совокупности — рациональные числа и иррациональные числа .

знаменитый отрывок, есть » Платона В «Теэтете в котором говорится, что Теодор (учитель Платона) доказал иррациональность

${\sqrt {3}},{\sqrt {5}},...,$

взяв все отдельные случаи до корня из 17 квадратных футов... .

Более общее доказательство показывает, что корень m -й степени целого числа N иррационален, если только N не является степенью m целого числа n . невозможно выразить То есть корень m- й степени из целого числа N как отношение a ⁄ b двух целых чисел a и b , у которых нет общего простого делителя , за исключением случаев, когда b = 1.

Евклидовы конструкции

Греческая геометрия была основана на использовании циркуля и линейки (хотя линейка не является строго необходимой). Компас позволяет геометру строить точки, равноудаленные друг от друга, что в евклидовом пространстве эквивалентно неявному вычислению квадратных корней . Четыре знаменитых вопроса о том, как построить:

1. пара прямых , делящих заданный угол на три части ;
2. куб, объём которого в два раза превышает объём данного куба ;
3. квадрат , равный по площади площади данного круга;
4. с равносторонний многоугольник произвольным числом сторон.

На протяжении более 2000 лет предпринимались безуспешные попытки решить эти проблемы; наконец, в XIX веке было доказано, что желаемые построения математически невозможны без применения дополнительных инструментов, кроме циркуля.

Все это проблемы евклидовой конструкции , а евклидовы конструкции могут быть выполнены только в том случае, если они включают в себя только евклидовы числа (по определению последних). Иррациональные числа могут быть евклидовыми. Хорошим примером является квадратный корень из 2 (иррациональное число). Это просто длина гипотенузы прямоугольного треугольника с катетами, длина которых составляет одну единицу, и ее можно построить с помощью линейки и циркуля. Но спустя столетия после Евклида было доказано, что евклидовы числа не могут включать в себя какие-либо операции, кроме сложения, вычитания, умножения, деления и извлечения квадратных корней.

Как трисекция общего угла , так и удвоение куба требуют извлечения кубических корней , которые не являются конструируемыми числами .

$\pi$ не является евклидовым числом ... и поэтому невозможно построить евклидовыми методами длину, равную длине окружности единичного диаметра

Потому что $\pi$в 1882 году было доказано, что это трансцендентное число , но не евклидово число; Отсюда построение длины $\pi$ из единичного круга невозможно.

Построение равностороннего n -угольника

Теорема Гаусса -Ванцеля показала в 1837 году, что построение равностороннего n -угольника невозможно для большинства значений n .

Евклида о

Основная статья: Неевклидова геометрия

Постулат о параллельности Евклида из «Начал» эквивалентен утверждению , что если задана прямая линия и точка, не лежащая на этой линии, через эту точку можно провести только одну параллель, параллельную этой линии. В отличие от других постулатов, он считался менее самоочевидным. Нагель и Ньюман утверждают, что это может быть связано с тем, что постулат касается «бесконечно удаленных» регионов космоса; в частности, параллельные линии определяются как не пересекающиеся даже «на бесконечности», в отличие от асимптот . Это кажущееся отсутствие самоочевидности привело к вопросу о том, можно ли это доказать с помощью других аксиом и постулатов Евклида. Лишь в XIX веке невозможность вывода постулата о параллельности из других была продемонстрирована в работах Гаусса , Бояи , Лобачевского и Римана . Эти работы показали, что постулат параллельности может быть заменен альтернативами, приводящими к неевклидовой геометрии .

Нагель и Ньюман считают, что вопрос, поднятый постулатом о параллельности, «... возможно, наиболее значительным достижением в его долгосрочном влиянии на последующую математическую историю». В частности, они считают его результаты «имеющими величайшее интеллектуальное значение», поскольку они показали, что « доказательство можно привести невозможности доказать определенные положения (в данном случае постулат о параллельности) внутри данной системы [в данном случае». случае, первые четыре постулата Евклида].»

Теория чисел

Невозможность

Основная статья: Последняя теорема Ферма

Великая теорема Ферма , выдвинутая Пьером де Ферма в 1600-х годах, утверждает невозможность найти решения в натуральных числах для уравнения $x^{n}+y^{n}=z^{n}$ с $n>2$. Сам Ферма дал доказательство для случая n = 4, используя свою технику бесконечного спуска , впоследствии были доказаны и другие частные случаи, но общий случай не был доказан до 1994 года Эндрю Уайлсом .

Гильберта

Основные статьи: теорема Матиясевича и проблемы Гильберта

Вопрос «Имеет ли любое произвольное диофантово уравнение целое решение?» является неразрешимым . То есть ответить на вопрос на все случаи невозможно.

Франзен представляет десятую проблему Гильберта и теорему MRDP (теорема Матиясевича-Робинсона-Дэвиса-Патнэма), которая утверждает, что «не существует алгоритма, который мог бы решить, имеет ли диофантово уравнение какое-либо вообще решение». MRDP использует доказательство неразрешимости Тьюринга: «... набор разрешимых диофантовых уравнений является примером вычислимо перечислимого, но неразрешимого набора, а набор неразрешимых диофантовых уравнений не является вычислимо перечислимым».

Разрешимость

Парадокс Ричарда

Основная статья: Парадокс Ричарда

Этот глубокий парадокс, представленный Жюлем Ришаром в 1905 году, лег в основу работы Курта Гёделя. и Алан Тьюринг. Краткое определение можно найти в Principia Mathematica :

Парадокс Ричарда... заключается в следующем. Рассмотрим все десятичные дроби, которые можно определить с помощью конечного числа слов [слова — это символы; жирный шрифт добавлен для выделения] ; пусть E будет классом таких десятичных дробей. Тогда E имеет $\aleph _{0}$ [бесконечное количество] терминов; следовательно, его члены могут быть упорядочены как 1-й, 2-й, 3-й... Пусть X будет числом, определенным следующим образом [Уайтхед и Рассел теперь используют диагональный метод Кантора] .
Если n -я цифра в n -й десятичной дроби равна p , пусть n -я цифра в X равна p + 1 (или 0, если p = 9). Тогда X отличается от всех членов E , поскольку какое бы конечное значение n ни имело, n -я цифра в X отличается от n -й цифры в n -й десятичной дроби, составляющей E , и, следовательно, X есть отличается от n -го десятичного знака. Тем не менее мы определили X в конечном числе слов (т. е. в этом самом определении слова выше), и поэтому X должен быть членом E . Таким образом, X одновременно является и не является членом E.

- Principia Mathematica , 2-е издание 1927 г., стр. 61

Курт Гёдель считал свое доказательство «аналогией» парадокса Рихарда, который он назвал « антиномией Рихарда ». ( ) см. ниже .

Алан Тьюринг сконструировал этот парадокс с помощью машины и доказал, что эта машина не может ответить на простой вопрос: сможет ли эта машина определить, окажется ли какая-либо машина (включая ее самого) в ловушке непродуктивного « бесконечного цикла » (т. е. она не сможет продолжать работу) его вычисление диагонального числа).

Полная и непротиворечивая система аксиом

Основная статья: теоремы Гёделя о неполноте

Цитируя Нагеля и Ньюмана (стр. 68): «Работа Гёделя сложна. Прежде чем будут достигнуты основные результаты, необходимо усвоить сорок шесть предварительных определений вместе с несколькими важными предварительными теоремами». Фактически, Нагелю и Ньюману потребовалось 67-страничное введение к изложению доказательства. Но если читатель чувствует себя достаточно сильным, чтобы взяться за эту статью, Мартин Дэвис замечает, что «эта замечательная статья является не только интеллектуальной вехой, но и написана с ясностью и энергией, которые доставляют удовольствие читать» (Дэвис в «Неразрешимое», стр. 4). ).

Гёдель своими словами доказал:

«Разумно... сделать предположение, что... [] аксиомы [из Principia Mathematica и Peano ] ... достаточны для решения всех математических вопросов, которые могут быть формально выражены в данных системах. В дальнейшем это будет будет показано, что это не так, а, скорее, что... существуют относительно простые проблемы теории обычных целых чисел, которые не могут быть решены на основе аксиом» (Гёдель в «Неразрешимых», стр. 4).

Гёдель сравнил свое доказательство с «антиномией Ричарда» (« антиномия » — это противоречие или парадокс; подробнее см. Парадокс Ричарда ):

«Аналогия этого результата с антиномией Рихарда сразу очевидна; существует также тесная связь [14] с парадоксом лжеца (сноска Гёделя 14: Всякая эпистемологическая антиномия может быть использована для аналогичного доказательства неразрешимости)... Таким образом, мы иметь перед собой предложение, которое утверждает свою собственную недоказуемость [15].

Доказательство остановки

Основная статья: Доказательство Тьюринга

• На Entscheidungsproblem , проблему решения , впервые ответил Чёрч в апреле 1935 года и опередил Тьюринга более чем на год, поскольку статья Тьюринга была получена для публикации в мае 1936 года.
• Доказательство Тьюринга затруднено из-за количества необходимых определений и его тонкости. см . в разделе «Машина Тьюринга» и «Доказательство Тьюринга» . Подробности
• Первое доказательство Тьюринга (из трёх) следует схеме парадокса Ричарда: вычислительная машина Тьюринга — это алгоритм, представленный строкой из семи букв в «вычислительной машине». Его «вычисления» заключаются в проверке всех вычислительных машин (включая себя) на наличие «кругов» и формировании диагонального числа на основе вычислений некруглых или «успешных» вычислительных машин. Он делает это, начиная последовательно с 1, путем преобразования чисел (по основанию 8) в строки из семи букв для проверки. Когда он достигает своего собственного номера, он создает свою собственную строку букв. Он решает, что это буквенная строка успешной машины, но когда он пытается выполнить вычисления этой машины ( свои собственные ), он замыкается в круг и не может продолжить. Таким образом, мы пришли к парадоксу Ричарда. (Если вы сбиты с толку, обратитесь к доказательству Тьюринга для получения дополнительной информации).

Ряд подобных доказательств неразрешимости появился вскоре до и после доказательства Тьюринга:

1. Апрель 1935 года: Доказательство Алонсо Чёрча («Неразрешимая проблема элементарной теории чисел»). Его доказательство заключалось в том, чтобы «... предложить определение эффективной вычислимости... и показать на примере, что не каждая проблема этого класса разрешима» («Undecidable», стр. 90))
2. 1946: Проблема с почтовой корреспонденцией (см. Хопкрофт и Ульман п. 193 и далее, с. 407 для справки)
3. Апрель 1947: Доказательство Эмиля Поста ( Рекурсивная неразрешимость проблемы Туэ ) (Неразрешимое, стр. 293). С тех пор это стало известно как «Проблема слова Туэ» или «Проблема слова Туэ» ( Аксель Туэ предложил эту проблему в статье 1914 года (см. Ссылки на статью Поста в Undecidable, стр. 303)).
4. Теорема Райса : обобщенная формулировка второй теоремы Тьюринга (см. Хопкрофт и Ульман п. 185 и далее)
5. Теорема Грейбаха : неразрешимость в теории языка (см. Хопкрофт и Ульман п. 205ff и ссылка на стр. 401 там же: Грейбах [1963] «Неразрешимость проблемы неоднозначности для минимальных линейных грамматик», Information and Control 6:2, 117–125, также ссылка на стр. 402 там же: Грейбах [1968] «Заметка о неразрешимых свойствах формальных языков», Math Systems Theory 2:1, 1–6.)
6. Вопросы о мозаике Пенроуза .

Теория информации

Сжатие случайных строк

Основная статья: Теорема Чайтина о неполноте

Изложение, подходящее для неспециалистов, см. Бельтрами с. 108 и след. См. также главу 8 Франзена, стр. 137–148, и Дэвиса, стр. 263–266. Обсуждение Франзена значительно сложнее, чем обсуждение Бельтрами, и оно углубляется в Грегори Хайтина так называемую «вероятность остановки» . Старая трактовка Дэвиса подходит к этому вопросу с точки зрения машины Тьюринга . Чайтин написал ряд книг о своих усилиях и последующих философских и математических последствиях из них.

Строка называется (алгоритмически) случайной , если ее нельзя создать с помощью какой-либо более короткой компьютерной программы. Хотя большинство строк являются случайными , доказать это невозможно ни для одной конкретной строки, за исключением конечного числа коротких:

«Перефразированием результата Чайтина является то, что не может быть формального доказательства того, что достаточно длинная строка является случайной...»

Бельтрами отмечает, что «доказательство Чейтина связано с парадоксом, сформулированным оксфордским библиотекарем Дж. Берри в начале двадцатого века, который требует «наименьшего положительного целого числа, которое не может быть определено английским предложением длиной менее 1000 символов». Очевидно, что кратчайшее определение этого числа должно содержать не менее 1000 символов, однако предложение в кавычках, которое само по себе является определением предполагаемого числа, имеет длину менее 1000 символов!»

Естественные науки

Основная статья: Теорема о запрете

В естествознании теоремы о невозможности выводятся как математические результаты, доказанные в рамках устоявшихся научных теорий . Основанием для такого решительного признания является сочетание обширных доказательств того, что чего-то не происходит, в сочетании с лежащей в их основе теорией, очень успешной в предсказаниях, чьи предположения логически приводят к выводу, что что-то невозможно.

Двумя примерами широко признанных невозможностей в физике являются вечные двигатели , нарушающие закон сохранения энергии , и превышение скорости света , что нарушает положения специальной теории относительности . Другой — принцип неопределенности квантовой механики , который утверждает невозможность одновременного знания положения и импульса частицы. Существует также теорема Белла : никакая физическая теория локальных скрытых переменных не сможет воспроизвести все предсказания квантовой механики.

Хотя утверждение о невозможности в естествознании никогда не может быть абсолютно доказано, оно может быть опровергнуто наблюдением единственного контрпримера . Такой контрпример потребовал бы пересмотра предположений, лежащих в основе теории, подразумевающей невозможность.

См. также

• Список нерешенных проблем математики . Решения этих проблем все еще находятся в поиске. Напротив, вышеперечисленные проблемы, как известно , не имеют решения.
• Парадоксы теории множеств

Библиография

• Г.Х. Харди и Э.М. Райт , Введение в теорию чисел , пятое издание, Clarendon Press, Оксфорд, Англия, 1979 г., переиздано в 2000 г. с General Index (первое издание: 1938 г.). Доказательства трансцендентности е и пи нетривиальны, но математически грамотный читатель сможет с ними разобраться.
• Альфред Норт Уайтхед и Бертран Рассел , Principia Mathematica до *56, Кембридж в University Press, 1962, перепечатка 2-го издания 1927 года, первого издания 1913 года. Гл. 2.И. «Принцип порочного круга» с. 37ff и гл. 2.VIII. «Противоречия» с. 60ff.
• Тьюринг, AM (1936), «О вычислимых числах с применением к проблеме Entscheidungs», Труды Лондонского математического общества , 2, том. 42, нет. 1 (опубликовано в 1937 г.), стр. 230–65, doi : 10.1112/plms/s2-42.1.230 , S2CID   73712 (и Тьюринг, AM (1938), «О вычислимых числах с применением к проблеме Entscheidungs: исправление», Труды Лондонского математического общества , 2, том. 43, нет. 6 (опубликовано в 1937 г.), стр. 544–6, doi : 10.1112/plms/s2-43.6.544 ). онлайн-версия Это эпохальная статья, в которой Тьюринг определяет машины Тьюринга и показывает, что они (как и проблема Entscheidungs ) неразрешимы.
• Мартин Дэвис , Неразрешимое, Основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях , Raven Press, Нью-Йорк, 1965. Статья Тьюринга занимает третье место в этом томе. В число статей входят работы Гёделя, Чёрча, Россера, Клини и Поста.
• Глава Мартина Дэвиса «Что такое вычисление» в книге Линн Артур Стин « Математика сегодня» , 1978, Vintage Books Edition, Нью-Йорк, 1980. В его главе описываются машины Тьюринга в терминах более простой машины Пост-Тьюринга , затем продолжается описание машины Тьюринга. первое доказательство и вклад Чайтина.
• Эндрю Ходжес , Алан Тьюринг: Загадка , Саймон и Шустер, Нью-Йорк. См. главу «Дух истины», где представлена ​​история, ведущая к его доказательству, и его обсуждение.
• Ганс Райхенбах , «Элементы символической логики », Dover Publications Inc., Нью-Йорк, 1947. Ссылка, часто цитируемая другими авторами.
• Эрнест Нагель и Джеймс Ньюман , Доказательство Гёделя , издательство Нью-Йоркского университета, 1958.
• Эдвард Белтрами , Что такое случайность? Случайность и порядок в математике и жизни , Springer-Verlag New York, Inc., 1999.
• Торкель Францен , Теорема Гёделя, Неполное руководство по ее использованию и злоупотреблениям , AK Peters, Wellesley Mass, 2005. Недавний взгляд на теоремы Гёделя и злоупотребления ими. Не такое уж и простое чтение, как полагает автор. (Размытое) обсуждение Франзеном третьего доказательства Тьюринга полезно из-за его попыток прояснить терминологию. Предлагает обсуждение аргументов Фримена Дайсона, Стивена Хокинга, Роджера Пенроуза и Грегори Чайтина (среди прочих), в которых используются теоремы Гёделя, а также полезную критику некоторой философской и метафизической чуши, вдохновленной Гёделем, которую он нашел в сети.
• Павел Пудлак, Логические основы математики и сложность вычислений. Нежное введение , Springer 2013. (См. главу 4 «Доказательства невозможности».)