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

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

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

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

Среди важнейших доказательств невозможности ХХ века были доказательства, связанные с неразрешимость, который показал, что существуют задачи, которые вообще не могут быть решены никаким алгоритмом, наиболее известным из которых является проблема остановки. К другим аналогичным выводам относятся выводы Теоремы Гёделя о неполноте, который обнаруживает некоторые фундаментальные ограничения доказуемости формальных систем.^[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— Хит,^{[нужна цитата ]}

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

Есть знаменитый отрывок в Платон с Theaetetus в котором говорится, что Теодорус (Учитель Платона) доказал иррациональность

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

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

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

В мкорень -й степени целого числа N иррационально, если только N это м-я степень целого числа п".^[8]

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

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

Три известных вопроса Греческая геометрия были как:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Апрель 1935 года: доказательство Церковь Алонсо («Неразрешимая проблема элементарной теории чисел»). Его доказательство заключалось в том, чтобы «... предложить определение эффективной вычислимости ... и показать на примере, что не все проблемы этого класса разрешимы» (Undecidable, стр. 90))
2. 1946: Проблема с почтовой корреспонденцией (см. Хопкрофт и Ульман^[14] п. 193ff, стр. 407 для справки)
3. Апрель 1947 года: доказательство Эмиль Пост (Рекурсивная неразрешимость проблемы Туэ.) (Неразрешимо, с. 293). С тех пор это стало известно как «проблема слова Туэ» или «проблема слова Туэ» (Аксель Туэ предложил эту проблему в статье 1914 года (см. Ссылки на статью Поста в Undecidable, стр. 303)).
4. Теорема Райса: обобщенная формулировка второй теоремы Тьюринга (см. Хопкрофт и Ульман^[14] п. 185ff)^[15]
5. Теорема Грейбаха: неразрешимость в теории языка (см. Хопкрофт и Ульман^[14] п. 205ff и ссылку на стр. 401 там же: Greibach [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).

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

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

В экономика, Теорема Хольмстрёма - это теорема о невозможности, доказывающая, что никакая система мотивации для команды агентов не может удовлетворять всем трем желательным критериям.

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

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

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

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

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

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

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

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