Доказательство невозможности - Proof of impossibility

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

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

Проблема, возникшая в 16 веке, заключалась в создании общей формулы с использованием радикалов, выражающей решение любого полиномиального уравнения фиксированной степени k , где k ≥ 5. В 1820-х годах теорема Абеля – Руффини (также известная как теорема Абеля о невозможности) показал, что это невозможно, используя такие понятия, как разрешимые группы из теории Галуа - нового подполя абстрактной алгебры .

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

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

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

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

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

Доказательство по происхождению

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

Виды опровержения гипотез о невозможности

Есть два альтернативных метода опровержения гипотезы о невозможности чего-либо: контрпример ( конструктивное доказательство ) и логическое противоречие ( неконструктивное доказательство ).

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

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

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

Существование иррациональных чисел: доказательство пифагорейцев

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

Неизвестно, когда и кем была открыта «теорема Пифагора». Вряд ли это открытие могло быть сделано самим Пифагором, но оно определенно было сделано в его школе. Пифагор жил около 570–490 гг. До н. Э. Демокрит, родившийся около 470 г. до н.э., писал иррациональные линии и твердые тела  ...

-  Хит,

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

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

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

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

Теперь существует более общее доказательство того, что:

М х корней целого числа N является нерациональным, если N не являются м й степени целого числа п ».

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

Невозможные конструкции, которые искали древние греки

Три известных вопроса греческой геометрии заключались в следующем:

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

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

Четвертая проблема древних греков заключалась в том, чтобы построить равносторонний многоугольник с заданным числом сторон n , помимо базовых случаев n  = 3, 4, 5, которые они знали, как построить.

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

Трисекция угла и удвоение куба

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

Квадрат круга

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

Существует доказательство, демонстрирующее, что любое евклидово число является алгебраическим числом - числом, которое является решением некоторого полиномиального уравнения . Следовательно, поскольку в 1882 году было доказано, что оно является трансцендентным числом и, следовательно, по определению не является алгебраическим числом, оно не является евклидовым числом. Следовательно, построить длину из единичной окружности невозможно, и окружность нельзя возвести в квадрат. ${\ displaystyle \ pi}$${\ displaystyle \ pi}$

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

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

Параллельная аксиома Евклида

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

Возникает вопрос: может ли аксиома о том, что две параллельные прямые «... не будут встречаться даже« на бесконечности »» (сноска, там же), быть выведена из других аксиом геометрии Евклида? Только в работах XIX века «... Гаусса, Бойяи, Лобачевского и Римана была продемонстрирована невозможность вывести параллельную аксиому из других. Этот результат имел величайшее интеллектуальное значение ... может быть дано доказательство невозможности доказательства некоторых утверждений [в данном случае параллельного постулата] в рамках данной системы [в данном случае первых четырех постулатов Евклида] ». (стр.10)

Последняя теорема Ферма

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

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

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

Парадокс Ричарда ... заключается в следующем. Рассмотрим все десятичные дроби, которые можно определить с помощью конечного числа слов [«слова» - это символы; жирный шрифт добавлен для выделения] ; пусть E - класс таких десятичных знаков. Тогда E имеет [бесконечное количество] членов; следовательно, его элементы могут быть упорядочены как 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.${\ displaystyle \ aleph _ {0}}$

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

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

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

Можно ли доказать эту теорему на основе этих аксиом? Доказательство Гёделя

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

Так что же доказал Гёдель? По его собственным словам:

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

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

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

Замкнется ли эта вычислительная машина по «кругу»? Первое доказательство Тьюринга

• На проблему 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] «Неразрешимость проблемы неоднозначности для минимальных линейных грамматик», Информация и контроль 6: 2, 117–125 , также ссылка на стр. 402 там же: Greibach [1968] «Заметка о неразрешимых свойствах формальных языков», Math Systems Theory 2: 1, 1–6.)
6. Вопросы о плитках Пенроуза
7. Вопрос о решениях диофантовых уравнений и результирующий ответ в теореме MRDP; см. запись ниже.

Можно ли сжать эту строку? Доказательство Чайтина

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

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

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

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

Имеет ли это диофантово уравнение целочисленное решение? Десятая проблема Гильберта

На вопрос «Имеет ли произвольное« диофантово уравнение »целочисленное решение?» является неразрешимой .То есть, невозможно ответить на вопрос , для всех случаев.

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

В социальных науках

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

В экономике , Holmström это теорема является теоремой невозможности доказательства того, что ни одна системы стимулов для команды агентов не может удовлетворить все три желательных критериев.

В естествознании

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

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

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

Смотрите также

• Список нерешенных задач по математике  - Решения этих проблем еще ищутся. В отличие от этого , вышеуказанные проблемы известны , не имеют никакого решения.
• Теорема запрета , соответствующее физическое понятие.

Примечания и ссылки

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