Конструктивное доказательство

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

В математике конструктивное доказательство — это метод доказательства , который демонстрирует существование математического объекта путем создания или предоставления метода для создания объекта. Это отличается от неконструктивного доказательства (также известного как доказательство существования или чистая теорема существования ), которое доказывает существование определенного вида объекта без предоставления примера. Чтобы избежать путаницы с более сильной концепцией, которая следует далее, такое конструктивное доказательство иногда называют эффективным доказательством .

Конструктивное доказательство может также ссылаться на более сильную концепцию доказательства, которая действительна в конструктивной математике . Конструктивизм — это математическая философия, которая отвергает все методы доказательства, предполагающие существование объектов, которые явно не построены. Это исключает, в частности, использование закона исключенного третьего , аксиомы бесконечности и аксиомы выбора , а также влечет за собой иное значение для некоторых терминов (например, термин «или» имеет более сильное значение в конструктивной математике, чем в классической). ^[1]

Некоторые неконструктивные доказательства показывают, что если определенное предложение ложно, то возникает противоречие; следовательно, предложение должно быть истинным ( доказательство от противного ). Однако принцип взрыва ( ex falso quodlibet ) был принят в некоторых разновидностях конструктивной математики, включая интуиционизм .

Конструктивные доказательства можно рассматривать как определение сертифицированных математических алгоритмов : эта идея исследуется в интерпретации конструктивной логики Брауэра–Гейтинга–Колмогорова , соответствии Карри–Ховарда между доказательствами и программами и таких логических системах, как интуиционистская теория типов Пера Мартина-Лёфа и исчисление конструкций Тьерри Коканда и Жерара Юэ .

Исторический пример

До конца 19 века все математические доказательства были по сути конструктивными. Первые неконструктивные конструкции появились с теорией бесконечных множеств Георга Кантора и формальным определением действительных чисел .

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

Nullstellensatz можно сформулировать следующим образом: если — многочлены от n неизвестных с комплексными коэффициентами, не имеющие общих комплексных нулей , то существуют многочлены такие, что ${\displaystyle f_{1},\ldots ,f_{k}}$ ${\displaystyle g_{1},\ldots ,g_{k}}$

${\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}=1.}$

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

Двадцать пять лет спустя Грета Германн предоставила алгоритм для вычисления , который не является конструктивным доказательством в сильном смысле, поскольку она использовала результат Гильберта. Она доказала, что если они существуют, то их можно найти со степенями меньше . ^[3] ${\displaystyle g_{1},\ldots ,g_{k},}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle 2^{2^{n}}}$

Это дает алгоритм, поскольку задача сводится к решению системы линейных уравнений , рассматривая в качестве неизвестных конечное число коэффициентов ${\displaystyle g_{i}.}$

Примеры

Неконструктивные доказательства

Сначала рассмотрим теорему о том, что существует бесконечное множество простых чисел . Доказательство Евклида конструктивно. Но общепринятый способ упрощения доказательства Евклида постулирует, что, вопреки утверждению в теореме, существует только конечное число простых чисел, и в этом случае существует наибольшее из них, обозначаемое n . Затем рассмотрим число n ! + 1 (1 + произведение первых n чисел). Либо это число является простым, либо все его простые множители больше n . Не устанавливая конкретного простого числа, это доказывает, что существует число, которое больше n , вопреки исходному постулату.

Теперь рассмотрим теорему «существуют иррациональные числа и такие, что является рациональным ». Эту теорему можно доказать, используя как конструктивное доказательство, так и неконструктивное доказательство. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a^{b}}$

Следующее доказательство 1953 года, предложенное Довом Джарденом, широко использовалось как пример неконструктивного доказательства по крайней мере с 1970 года: ^{[4] [5]}

КУРИОСА
339. Простое доказательство того, что степень иррационального числа в иррациональной степени может быть рациональной. является либо рациональным, либо иррациональным. Если оно рационально, наше утверждение доказано. Если оно иррационально, наше утверждение доказано.      Дов Джарден Иерусалим
${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ ${\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2}$

Немного подробнее:

• Вспомним, что иррационально , а 2 рационально. Рассмотрим число . Либо оно рационально, либо оно иррационально. ${\displaystyle {\sqrt {2}}}$ ${\displaystyle q={\sqrt {2}}^{\sqrt {2}}}$
• Если рационально, то теорема верна, причем и оба являются . ${\displaystyle q}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\sqrt {2}}}$
• Если иррационально, то теорема верна, причем , так как ${\displaystyle q}$ ${\displaystyle a}$ ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ ${\displaystyle b}$ ${\displaystyle {\sqrt {2}}}$

${\displaystyle \left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{({\sqrt {2}}\cdot {\sqrt {2}})}={\sqrt {2}}^{2}=2.}$

По своей сути это доказательство неконструктивно, поскольку оно опирается на утверждение «Или q рационально, или оно иррационально» — пример закона исключенного третьего , который недействителен в конструктивном доказательстве. Неконструктивное доказательство не конструирует пример a и b ; оно просто дает ряд возможностей (в данном случае две взаимоисключающие возможности) и показывает, что одна из них — но не показывает, какая именно — должна давать желаемый пример.

Как оказалось, является иррациональным из-за теоремы Гельфонда–Шнайдера , но этот факт не имеет никакого значения для корректности неконструктивного доказательства. ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$

Конструктивные доказательства

Конструктивное доказательство теоремы о том, что степень иррационального числа в иррациональной степени может быть рациональной, дает реальный пример, такой как :

${\displaystyle a={\sqrt {2}}\,,\quad b=\log _{2}9\,,\quad a^{b}=3\,.}$

Квадратный корень из 2 иррационален, а 3 рационален. также иррационален: если бы он был равен , то по свойствам логарифмов 9 n ^было бы равно 2 ^m , но первое число нечетное, а второе четное. ${\displaystyle \log _{2}9}$ ${\displaystyle m \over n}$

Более существенным примером является теорема о минорах графа . Следствием этой теоремы является то, что граф может быть нарисован на торе тогда и только тогда, когда ни один из его миноров не принадлежит некоторому конечному множеству « запрещенных миноров ». Однако доказательство существования этого конечного множества не является конструктивным, а запрещенные миноры фактически не указаны. ^[6] Они до сих пор неизвестны.

Контрпримеры Брауэра

В конструктивной математике утверждение может быть опровергнуто путем приведения контрпримера , как в классической математике. Однако также возможно привести контрпример Брауэра, чтобы показать, что утверждение неконструктивно. ^[7] Этот вид контрпримера показывает, что утверждение подразумевает некоторый принцип, который, как известно, неконструктивен. Если можно конструктивно доказать, что утверждение подразумевает некоторый принцип, который не является конструктивно доказуемым, то само утверждение не может быть конструктивно доказуемым.

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

Брауэр также предоставил «слабые» контрпримеры. ^[8] Такие контрпримеры, однако, не опровергают утверждение; они только показывают, что в настоящее время не известно конструктивного доказательства утверждения. Один слабый контрпример начинается с рассмотрения некоторой нерешенной проблемы математики, такой как гипотеза Гольдбаха , которая спрашивает, является ли каждое четное натуральное число, большее 4, суммой двух простых чисел. Определим последовательность a ( n ) рациональных чисел следующим образом: ^[9]

${\displaystyle a(n)={\begin{cases}(1/2)^{n}&{\mbox{if every even natural number in the interval }}[4,n]{\mbox{ is the sum of two primes}},\\(1/2)^{k}&{\mbox{if }}k{\mbox{ is the least even natural number in the interval }}[4,n]{\mbox{ which is not the sum of two primes}}\end{cases}}}$

Для каждого n значение a ( n ) может быть определено исчерпывающим поиском, и поэтому a является хорошо определенной последовательностью, конструктивно. Более того, поскольку a является последовательностью Коши с фиксированной скоростью сходимости, a сходится к некоторому действительному числу α, согласно обычной трактовке действительных чисел в конструктивной математике.

Несколько фактов о действительном числе α можно доказать конструктивно. Однако, исходя из разного значения слов в конструктивной математике, если есть конструктивное доказательство того, что «α = 0 или α ≠ 0», то это будет означать, что есть конструктивное доказательство гипотезы Гольдбаха (в первом случае) или конструктивное доказательство того, что гипотеза Гольдбаха ложна (во втором случае). Поскольку такое доказательство неизвестно, цитируемое утверждение также не должно иметь известного конструктивного доказательства. Однако вполне возможно, что гипотеза Гольдбаха может иметь конструктивное доказательство (поскольку мы в настоящее время не знаем, имеет ли оно его), и в этом случае цитируемое утверждение также будет иметь конструктивное доказательство, хотя и неизвестное в настоящее время. Основное практическое применение слабых контрпримеров — определение «трудности» проблемы. Например, только что показанный контрпример показывает, что цитируемое утверждение «по крайней мере так же трудно доказать», как и гипотезу Гольдбаха. Слабые контрпримеры такого рода часто связаны с ограниченным принципом всеведения .

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

• Конструктивизм (философия математики)
• Эрретт Бишоп — автор книги «Основы конструктивного анализа».
• Теорема существования § Результаты «чистого» существования
• Неконструктивные доказательства существования алгоритма
• Вероятностный метод

Ссылки

1. Бриджес, Дуглас; Палмгрен, Эрик (2018), «Конструктивная математика», в Zalta, Edward N. (ред.), The Stanford Encyclopedia of Philosophy (лето 2018 г.), Metaphysics Research Lab, Stanford University , получено 25 октября 2019 г.
2. Макларти, Колин (15 апреля 2008 г.). Круги нарушены: взаимодействие математики и повествования — Глава 4. Гильберт о теологии и ее недовольстве. Миф о происхождении современной математики . Доксиадес, Апостолос К., 1953-, Мазур, Барри. Принстон: Princeton University Press. doi : 10.1515/9781400842681.105. ISBN 9781400842681. OCLC  775873004. S2CID  170826113.
3. Германн, Грета (1926). «Die Frage der endlich vielen Schritte in der Theorie der Polynomideale: Unter Benutzung nachgelassener Sätze von K. Hentzelt». Mathematische Annalen (на немецком языке). 95 (1): 736–788. дои : 10.1007/BF01206635. ISSN  0025-5831. S2CID  115897210.
4. Дж. Роджер Хиндли , «Доказательство корня 2 как пример неконструктивности», неопубликованная статья, сентябрь 2014 г., полный текст. Архивировано 23 октября 2014 г. на Wayback Machine.
5. Дов Жарден, «Простое доказательство того, что степень иррационального числа в иррациональной степени может быть рациональной», Curiosa No. 339 в Scripta Mathematica 19 :229 (1953)
6. Fellows, Michael R.; Langston, Michael A. (1988-06-01). "Неконструктивные инструменты для доказательства разрешимости за полиномиальное время" (PDF) . Journal of the ACM . 35 (3): 727–739. doi :10.1145/44483.44491. S2CID  16587284.
7. Манделькерн, Марк (1989). «Брауэровские контрпримеры». Mathematics Magazine . 62 (1): 3–27. doi :10.2307/2689939. ISSN  0025-570X. JSTOR  2689939.
8. AS Troelstra, Принципы интуиционизма , Lecture Notes in Mathematics 95, 1969, стр. 102
9. Марк ван Аттен, 2015, «Слабые контрпримеры», Стэнфордская энциклопедия математики

Дальнейшее чтение

• J. Franklin и A. Daoud (2011) Доказательство в математике: Введение . Kew Books, ISBN 0-646-54509-4 , гл. 4 
• Харди, Г. Х. и Райт, Э. М. (1979) Введение в теорию чисел (пятое издание). Oxford University Press. ISBN 0-19-853171-0 
• Анн Сьерп Трульстра и Дирк ван Дален (1988) «Конструктивизм в математике: Том 1» Elsevier Science. ISBN 978-0-444-70506-8 

Внешние ссылки

• Слабые контрпримеры Марка ван Аттена, Стэнфордская энциклопедия философии