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

В математика, а конструктивное доказательство это метод доказательство что демонстрирует существование математический объект путем создания или предоставления метода для создания объекта. Это в отличие от неконструктивное доказательство (также известный как доказательство существования или чистая теорема существования), который доказывает существование определенного типа объекта без предоставления примера.^[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 {, если каждое четное натуральное число в интервале}} [4, n] { mbox {является суммой из двух простых чисел}}, (1/2) ^ {k} & { mbox {if}} k { mbox {- наименьшее четное натуральное число в интервале}} [4, n] { mbox { что не является суммой двух простых чисел}} end {cases}}}$

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

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

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

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

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

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

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

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