Введение

Категория математических доказательств

В математике теорема о невозможности — это теорема, демонстрирующая, что та или иная проблема или общий класс проблем не имеет решения. Они также известны как доказательства невозможности, отрицательные доказательства или отрицательные результаты. Теоремы о невозможности часто разрешают десятилетия или столетия работы, потраченные на поиск решения, доказывая его отсутствие. Доказать невозможность чего-либо обычно сложнее, чем доказать обратное, поскольку часто требуется разработать доказательство, которое работает в общем случае, а не просто показать конкретный пример. Теоремы о невозможности обычно выражаются в логике как отрицательные экзистенциальные или универсальные утверждения. Иррациональность квадратного корня из 2 — одно из старейших доказательств невозможности. Оно показывает, что квадратный корень из 2 нельзя представить в виде отношения двух целых чисел. Другим важным доказательством невозможности стало доказательство Фердинанда фон Линдемана в 1882 году, которое показало, что задача квадратуры круга неразрешима, поскольку число π является трансцендентным (то есть неалгебраическим), и лишь подмножество алгебраических чисел может быть построено с помощью циркуля и линейки. Две другие классические задачи — трисекция произвольного угла и удвоение куба — также были доказаны как неразрешимые в XIX веке, и все эти задачи стимулировали исследования в области более сложных математических структур. Некоторые из наиболее важных доказательств невозможности, полученных в XX веке, были связаны с неразрешимостью, которая показала, что существуют проблемы, которые в общем случае не могут быть решены никаким алгоритмом, одной из наиболее известных из которых является проблема останова. Теоремы о неполноте Гёделя были другими примерами, выявившими фундаментальные ограничения доказуемости формальных систем. В теории вычислительной сложности такие методы, как релятивизация (добавление оракула), позволяют получать «слабые» доказательства невозможности, поскольку методы доказательства, не подверженные влиянию релятивизации, не могут решить проблему P против NP. Другой метод — доказательство полноты для класса сложности, которое предоставляет доказательства сложности задач, показывая, что их решение так же трудно, как и решение любой другой задачи в этом классе. В частности, задача, являющаяся полной для класса, неразрешима, если хотя бы одна задача в этом классе неразрешима.

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

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

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

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

Контрпример

Очевидный способ опровергнуть гипотезу о невозможности — это привести единственный контрпример. Например, Эйлер предположил, что для получения в сумме очередной n-й степени необходимо как минимум n различных n-х степеней. Эта гипотеза была опровергнута в 1966 году с помощью контрпримера, демонстрирующего, что для получения очередной пятой степени достаточно сложить всего четыре различных пятых степени: 275 + 845 + 1105 + 1335 = 1445. Доказательство контрпримером является формой конструктивного доказательства, поскольку в нем демонстрируется объект, опровергающий исходное утверждение.

Теорема Стрелы: Рациональное ранжирование по выбору голосования

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

Теорема Гиббарда: недиктаторские стратегические игры

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

Принцип откровения: Нечестные решения

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

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

Доказательство Пифагора, относящееся к примерно 500 г. до н.э., оказало глубокое влияние на математику. Оно демонстрирует, что квадратный корень из 2 нельзя представить в виде отношения двух целых чисел. Это доказательство разделило "числа" на два непересекающихся множества — рациональные и иррациональные числа. В диалоге Платона «Теэтет» есть известное место, где утверждается, что Феодор (учитель Платона) доказал иррациональность, рассматривая все отдельные случаи вплоть до корня из 17 квадратных футов. Более общее доказательство показывает, что корень m-й степени из целого числа N является иррациональным, если только N не является m-й степенью целого числа n. Иными словами, невозможно выразить корень m-й степени из целого числа N в виде отношения a/b двух целых чисел a и b, не имеющих общих простых делителей, за исключением случаев, когда b = 1.

Построение равностороннего n-гона

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

Дедукция постулата Евклида о параллелях

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

Невозможность триплей Фермата

Последняя теорема Ферма была сформулирована Пьером де Ферма в 1600-х годах и утверждает об отсутствии решений в положительных целых числах уравнения. Сам Ферма привел доказательство для случая n = 4, используя метод бесконечного спуска, и впоследствии были доказаны другие частные случаи, однако общий случай был доказан лишь в 1994 году Эндрю Уайлсом.

Целые решения диофантических уравнений: десятая задача Гильберта

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

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

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

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

Природные науки

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