Основные методы доказательств в математике

Основные методы доказательств

• Утверждения делятся на два типа: всеобщности и существования.
• Любое математическое утверждение, кроме аксиом, должно быть доказано.
• В математике любое утверждение можно записать в виде «Существует такое ..., что ...» или «Для любого ... верно, что ...».

Переход к формальному языку

• При доказательстве математического утверждения важно определить, является ли оно утверждением о существовании или о всеобщности.
• Существование чего-либо часто доказывается приведением примера.
• Доказывать утверждения о всеобщности обычно сложнее.
• Большинство теорем в учебниках являются утверждениями о всеобщности.

Доказательство утверждений существования

• Для доказательства существования достаточно привести пример и объяснить, почему он подходит.
• Необязательно объяснять, как был придуман пример для доказательства существования. Главное, показать, что он удовлетворяет условиям.

Другие формы вопроса «существует ли?»

• Вопросы типа «можно ли что-либо сделать?» также являются вопросами о существовании.
• Чтобы ответить «да» на вопрос о существовании, достаточно привести пример и доказать его корректность.
• Противоположностью вопросу «можно ли» является вопрос «обязательно ли», требующий доказательства всеобщности. Для ответа «нет» достаточно контрпримера.

Доказательство утверждений всеобщности

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

Доказательство от противного

• Предполагается ложность утверждения -Х, и выводится противоречие.
• Под словами «выведем противоречие» понимается следующее: мы должны доказать истинность импликаций ¬X → Y и «X → ¬Ү для некоторого утверждения Ү.
• Схема рассуждений корректна, так как истинность одновременно ¬X → Y и ¬X → «Y, согласно логическим законам, действительно означает истинность Х.

Теорема о бесконечности простых чисел

• Это пример доказательства от противного. Предполагается конечность множества простых чисел и показывается, что это приводит к противоречию.

Закон контрапозиции

• Если требуется доказать утверждение вида А → В, можно вместо него доказать утверждение «В → ¬А, что может оказаться проще.

Принцип Дирихле

• Принцип Дирихле является полезным инструментом для доказательства других утверждений.
• Формулировка принципа Дирихле: если п + 1 кроликов посажены в п клеток, то в какой-то клетке окажется хотя бы 2 кролика.
• Общая формулировка: при любой рассадке nk + 1 кроликов по п клеткам найдется такая клетка, в которой оказалось хотя бы к + 1 кроликов.

Задачи, решаемые с помощью принципа Дирихле

• Из любых n + 1 целых чисел найдутся два, разность которых делится на п.
• В любой группе людей найдутся двое, у которых одинаковое число друзей среди этой группы.

Оценка + пример

• В задачах, где требуется найти наибольшее или наименьшее возможное значение чего-либо, нужно построить пример и доказать его оптимальность.
• Часть рассуждений с примером показывает, что при данном n конфигурация существует.
• Часть рассуждений с оценкой показывает, что для меньшего (или большего) значения параметра конфигурация невозможна.
• Решение задач на "оценку + пример" должно состоять из двух частей: доказательства существования и доказательства всеобщности.
• Хороший стиль оформления решений - явно разбивать текст решения на две части, озаглавливая их соответственно «оценка» и «пример».

Если кратко

• Прежде, чем доказывать утверждение, нужно понять: это утверждение о существовании или о всеобщности.
• Утверждения о существовании обычно доказываются проще других: нужно лишь придумать пример и объяснить, почему он подходит.
• Утверждения о всеобщности доказываются сложнее, и для этого есть несколько способов.
• Отдельно выделяют класс математических утверждений, в которых говорится о наибольшем или наименьшем возможном значении чего-либо. Чтобы доказать такие утверждения используют метод «оценка + пример».