Неконструктивное доказательство
Неконструктивное доказательство (неэффективное доказательство) — класс математических доказательств, доказывающих лишь существование в заданном (как правило, бесконечном) множестве элемента, удовлетворяющего заданным свойствам, но не дающее никакой информации о других свойствах элемента, то есть не позволяющие ни предъявить его, ни приблизительно описать. Доказательства, которые доказывают существование элемента, предъявляя способ получения этого элемента, называются конструктивными.
Если в доказательстве доказывается формула, в которой одна из величин — постоянная, но её значение восстановить невозможно, то это число называется неэффективной константой.
Это понятие не следует путать со случаем, когда константу (или другой искомый объект) просто очень сложно выразить или она оказывается выходящей за рамки разумных ожиданий. Например, доказательство, в котором возникает число Грэма является конструктивным, потому что число Грэма, хоть и очень велико, но может быть конкретно описано.
Неконструктивные доказательства, как правило, возникают при применении в ходе доказательства некоторых типичных утверждений и приёмов, самих по себе неконструктивных. Часто неконструктивные доказательства ведутся от противного.
Многие такие доказательства основаны на разных формах и обобщениях принципа Дирихле. Сам по себе этот принцип
Если элементов лежат в ячейках, то существует ячейка с не менее чем двумя элементами
