Конструктивен ли прямой перебор?

[Munin]

(Оффтоп)

Gagarin1968 в сообщении #1211460 писал(а):

пункт 1е - фамильярность (у нас принято обращаться друг к другу на "Вы", с большой буквы),

А у нас - на "вы" с любой буквы.

GAA:

Munin заблокирован на две недели за продолжение оффтопика после замечания модератора.

[Gagarin1968]

Aritaborian в сообщении #1211474 писал(а):

Можно доказать, что существует розовый единорог. Доказав это, вы не обязаны предъявлять его и не обязаны перебирать множество всех единорогов в поисках розовых.

Aritaborian
Так ведь это же и есть чистая теорема о существовании. Но она ведь неконструктивна. Или я ошибаюсь?

[iifat]

Aritaborian в сообщении #1211459 писал(а):

отсутствие явного способа (алгоритма) доказательства утверждения $P(a)$ для каждого элемента $a\in A$ делает данное доказательство неконструктивным

Как по мне, это делает данное доказательство вовсе не доказательством. Соответственно, нахождение такого способа делает рассуждение одновременно доказательством, и притом конструктивным.

[Aritaborian]

Кстати, да:

grizzly в сообщении #1211361 писал(а):

В теории Рамсея результаты обычно получают неконструктивными методами -- доказывают существование искомого решения, не давая алгоритма его нахождения. Утверждение, что это решение может быть найдено методом полного перебора, само по себе ничего не доказывает до тех пор, пока это перебор не был осуществлён.

Меня снова подвела невнимательность. Перечитал. С одной стороны нечто называют результатом, с другой же — говорят, что никаким доказательством это не пахнет. И верно второе. Как можно тогда первое называть «результатом»?

[grizzly]

Aritaborian
Я лучше поясню на примере.
Вот мы покрасили все египетские дроби в 150 цветов. ("Покрасили" здесь означает, что мы указали конкретный алгоритм раскраски.) Одна из теорем теории Рамсея утверждает, что существует конечное одноцветное подмножество этих дробей, сумма которых будет равна 1. Это теорема. Она доказана. Но доказательство не даёт никакого способа найти искомое подмножество. На вопрос "а как найти?" есть пока только один ответ -- методом перебора.

Ещё раз: без теоремы существования утверждение: "можно найти методом перебора" является просто голословным. Когда методом перебора нужное множество будет найдено, можно будет сказать, что мы доказали утверждение конструктивно.

[Someone]

Aritaborian в сообщении #1211659 писал(а):

С одной стороны нечто называют результатом, с другой же — говорят, что никаким доказательством это не пахнет.

Перебор объектов, если он закончился предъявлением конкретного объекта, является конструктивным доказательством.

В математике есть несколько конструктивных направлений, которые отличаются пониманием конструктивности. Не всякое математическое доказательство является конструктивным в смысле какого-либо этих направлений. Не нужно рассматривать это обстоятельство как повод для заявлений типа "это не доказательство, потому что оно не конструктивно". В конструктивной математике это не доказательство, а в классической — вполне себе доказательство.

[Aritaborian]

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