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

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

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

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

Конструктивные доказательства можно рассматривать как определение сертифицированных математических алгоритмов : эта идея исследуется в интерпретации Брауэр-гейтингова-Колмогоровой о конструктивных логиках , то Карри-Говард соответствие между доказательствами и программами, а также такими логическими системами , как Per Martin-LOF «s интуиционистским типа теория и Тьерри Кокан и Жерара Huet «s исчисление конструкций .

Исторический пример [ править ]

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

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

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

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

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

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

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

Примеры [ править ]

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

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

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

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

CURIOSA
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 ⁿ было бы равно 2 ^m , но первое нечетное, а второе четное.${\ displaystyle \ log _ {2} 9}$${\ displaystyle m \ over n}$

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

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

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

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

Брауэр также привел «слабые» контрпримеры. ^{[9] Однако} такие контрпримеры не опровергают утверждение; они только показывают, что в настоящее время не известно конструктивного доказательства этого утверждения. Слабым контрпример начинает принимать некоторые нерешенные проблемы математики, такие как гипотеза Гольдбаха , которая просит каждый даже натуральное число больше , чем 4 , является ли сумма двух простых чисел. Определите последовательность рациональных чисел a ( n ) следующим образом: ^[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}}}$

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

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