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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

ЛЮБОПЫТНЫЙ
339. Простое доказательство того, что степень иррационального числа, возведенная в иррациональную степень, может быть рациональной.
${\sqrt {2}}^{\sqrt {2}}$ является либо рациональным, либо иррациональным. Если оно рационально, то наше утверждение доказано. Если это иррационально, $({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2$ подтверждает наше утверждение.
Дов Жарден Иерусалим

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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», то это будет означать, что существует конструктивное доказательство гипотезы Гольдбаха (в первом случае) или конструктивное доказательство ложности гипотезы Гольдбаха (в последнем случае). Поскольку такое доказательство неизвестно, цитируемое утверждение также не должно иметь известного конструктивного доказательства. Однако вполне возможно, что гипотеза Гольдбаха может иметь конструктивное доказательство (поскольку в настоящее время мы не знаем, есть ли оно), и в этом случае цитируемое утверждение также будет иметь конструктивное доказательство, хотя и неизвестное в настоящее время. Основное практическое применение слабых контрпримеров — определение «сложности» проблемы. Например, только что показанный контрпример показывает, что цитируемое утверждение «по крайней мере так же трудно доказать», как и гипотезу Гольдбаха. Слабые контрпримеры такого рода часто связаны с ограниченный принцип всеведения .

См. также

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

Ссылки

^ Бриджес, Дуглас; Палмгрен, Эрик (2018), «Конструктивная математика» , в Залте, Эдвард Н. (редактор), Стэнфордская энциклопедия философии (изд. летом 2018 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 25 октября 2019 г.
^ Макларти, Колин (15 апреля 2008 г.). Тревожные круги: взаимодействие математики и повествования — Глава 4. Гильберт о теологии и ее недовольстве. Миф о происхождении современной математики . Доксиадес, Апостолос К., 1953-, Мазур, Барри. Принстон: Издательство Принстонского университета. дои : 10.1515/9781400842681.105 . ISBN 9781400842681 . OCLC 775873004 . S2CID 170826113 .
^ Герман, Грета (1926). «Вопрос о конечном числе шагов в теории полиномиальных идеалов: использование посмертных теорем К. Генцельта». Математические анналы (на немецком языке). 95 (1): 736–788. дои : 10.1007/BF01206635 . ISSN 0025-5831 . S2CID 115897210 .
^ Дж. Роджер Хиндли , «Доказательство корня-2 как пример неконструктивности», неопубликованная статья, сентябрь 2014 г., полный текст. Архивировано 23 октября 2014 г. в Wayback Machine.
^ Дов Жарден, «Простое доказательство того, что степень иррационального числа в иррациональном показателе может быть рациональной», Curiosa № 339 в Scripta Mathematica 19 :229 (1953)
^ Товарищи, Майкл Р.; Лэнгстон, Майкл А. (1 июня 1988 г.). «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время» (PDF) . Журнал АКМ . 35 (3): 727–739. дои : 10.1145/44483.44491 . S2CID 16587284 .
^ Манделькерн, Марк (1989). «Брауэровские контрпримеры». Журнал «Математика» . 62 (1): 3–27. дои : 10.2307/2689939 . ISSN 0025-570X . JSTOR 2689939 .
^ А.С. Трульстра, Принципы интуиционизма , Конспекты лекций по математике 95, 1969, стр. 102
^ Марк ван Аттен, 2015, « Слабые контрпримеры », Стэнфордская математическая энциклопедия.

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

Дж. Франклин и А. Дауд (2011) Доказательство в математике: введение . Книги Кью, ISBN 0-646-54509-4 , гл. 4
Харди, Г.Х. и Райт, Э.М. (1979) Введение в теорию чисел (пятое издание). Издательство Оксфордского университета. ISBN 0-19-853171-0
Анн Сьерп Трульстра и Дирк ван Дален (1988) «Конструктивизм в математике: Том 1» Elsevier Science. ISBN 978-0-444-70506-8

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

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

[1] Бриджес, Дуглас; Палмгрен, Эрик (2018), «Конструктивная математика» , в Залте, Эдвард Н. (редактор), Стэнфордская энциклопедия философии (изд. летом 2018 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 25 октября 2019 г.

[2] Макларти, Колин (15 апреля 2008 г.). Тревожные круги: взаимодействие математики и повествования — Глава 4. Гильберт о теологии и ее недовольстве. Миф о происхождении современной математики . Доксиадес, Апостолос К., 1953-, Мазур, Барри. Принстон: Издательство Принстонского университета. дои : 10.1515/9781400842681.105 . ISBN 9781400842681 . OCLC 775873004 . S2CID 170826113 .

[3] Герман, Грета (1926). «Вопрос о конечном числе шагов в теории полиномиальных идеалов: использование посмертных теорем К. Генцельта». Математические анналы (на немецком языке). 95 (1): 736–788. дои : 10.1007/BF01206635 . ISSN 0025-5831 . S2CID 115897210 .

[4] Дж. Роджер Хиндли , «Доказательство корня-2 как пример неконструктивности», неопубликованная статья, сентябрь 2014 г., полный текст. Архивировано 23 октября 2014 г. в Wayback Machine.

[5] Дов Жарден, «Простое доказательство того, что степень иррационального числа в иррациональном показателе может быть рациональной», Curiosa № 339 в Scripta Mathematica 19 :229 (1953)

[6] Товарищи, Майкл Р.; Лэнгстон, Майкл А. (1 июня 1988 г.). «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время» (PDF) . Журнал АКМ . 35 (3): 727–739. дои : 10.1145/44483.44491 . S2CID 16587284 .

[7] Манделькерн, Марк (1989). «Брауэровские контрпримеры». Журнал «Математика» . 62 (1): 3–27. дои : 10.2307/2689939 . ISSN 0025-570X . JSTOR 2689939 .

[8] А.С. Трульстра, Принципы интуиционизма , Конспекты лекций по математике 95, 1969, стр. 102

[9] Марк ван Аттен, 2015, « Слабые контрпримеры », Стэнфордская математическая энциклопедия.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]