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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Чуть подробнее:

• Напомним, что ${\displaystyle {\sqrt {2}}}$ иррационально, а 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 рационально или иррационально "- пример закон исключенного среднего, что неверно в рамках конструктивного доказательства. Неконструктивное доказательство не строит пример а и б; он просто дает ряд возможностей (в данном случае две взаимоисключающие возможности) и показывает, что одна из них - но не показывает который один - должен дать желаемый пример.

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

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

А конструктивный Доказательство вышеупомянутой теоремы об иррациональных степенях иррациональных чисел дало бы реальный пример, такой как:

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

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

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

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

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

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

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

${\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}}}$

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

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

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

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

использованная литература

1. "Окончательный словарь высшего математического жаргона - конструктивное доказательство". Математическое хранилище. 2019-08-01. Получено 2019-10-25.
2. Бриджес, Дуглас; Палмгрен, Эрик (2018), «Конструктивная математика», в Залте, Эдвард Н. (ред.), Стэнфордская энциклопедия философии (Лето 2018 г.), Исследовательская лаборатория метафизики Стэнфордского университета., получено 2019-10-25
3. Макларти, Колин (15 апреля 2008 г.). Нарушенные круги: взаимодействие математики и повествования - Глава 4. Гильберт о теологии и ее недовольстве Миф о происхождении современной математики. Доксиадес, Апостолос К., 1953-, Мазур, Барри. Принстон: Издательство Принстонского университета. Дои:10.1515/9781400842681.105. ISBN  9781400842681. OCLC  775873004. S2CID  170826113.
4. Германн, Грете (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.
5. Дж. Роджер Хиндли, «Доказательство корня-2 как пример неконструктивности», неопубликованная статья, сентябрь 2014 г., полный текст В архиве 2014-10-23 на Wayback Machine
6. Дов Жарден, «Простое доказательство того, что степень иррационального числа к иррациональной экспоненте может быть рациональной», Куриоза № 339 в Scripta Mathematica 19:229 (1953)
7. Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1988-06-01). «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время» (PDF). Журнал ACM. 35 (3): 727–739. Дои:10.1145/44483.44491.
8. Манделькерн, Марк (1989). «Брауэровские контрпримеры». Математический журнал. 62 (1): 3–27. Дои:10.2307/2689939. ISSN  0025-570X. JSTOR  2689939.
9. A. S. Troelstra, Принципы интуиционизма, Конспект лекций по математике 95, 1969, стр. 102
10. Марк ван Аттен, 2015 г. "Слабые контрпримеры ", Стэнфордская энциклопедия математики

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

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

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

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