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

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

Примеры

Бесконечность множества простых чисел

Сначала рассмотрим теорему о том, что существует бесконечное множество простых чисел. Доказательство Евклида является конструктивным. Однако распространенное упрощение этого доказательства, которое ведётся методом от противного из предположения, что существует лишь конечное число простых, конструктивным не является.

Иррациональная степень иррационального

Теперь рассмотрим теорему

  • Существуют иррациональные числа a и b такие, что ab является рациональным.
Эта теорема может быть доказана конструктивно и неконструктивнo.
Неконструктивное доказательство  В следующем 1953 доказательства Дов Джардена широко используется как пример неконструктивного доказательства. Напомним, что 2 иррационален. Заметим, что 22 рационально либо иррационально. Если 22 рационально, то теорема верна, с a=2 и b=2. Если 22 иррационально, то теорема верна, с a=22 и b=2 поскольку (22)2=22=2 Это доказательство не является конструктивным, потому что оно опирается на утверждение, что любое число  рационально или иррационально. Это пример применения закона исключенного третьего, который не является допустимым в рамках конструктивного доказательства. Заметим, что неконструктивное доказательство не даёт пример a и b; оно лишь дает несколько возможностей (в данном случае двух) и показывает, что одно из них есть нужный пример, но не говорит, какой.

  • На самом деле, 22 иррационально по теореме Гельфонда — Шнайдера, но этот факт не имеет отношения к справедливости неконструктивного доказательства приведённого выше.

Конструктивное доказательство  Пусть
a=2,b=log29,тогдаab=3.
Оба числа иррациональны; a — квадратный корень из 2 и если b=mn, то 32n=2m, что невозможно.

Смотри также


  • Теорема Робертсона — Сеймура
  • Теорема существования
  • Вероятностный метод
Категория:Философия математики Категория:Математические термины