Техники доказательств

Шерлок Холмс говорил: «Когда вы исключили невозможное, оставшееся - истина». Но математики пошли дальше: они создали арсенал техник, где каждая - свой способ раскрыть истину. Разбор случаев, индукция, конструкции... Какой инструмент выбрать?

• **Разбор случаев в праве:** Юридическая аргументация систематически рассматривает все сценарии — если обвиняемый виновен, должны быть улики X, Y, Z; если невиновен — алиби
• **Индукция в программировании:** Доказательство корректности рекурсивных алгоритмов (сортировка, обход деревьев) использует структурную индукцию
• **Конструктивные доказательства в криптографии:** Доказательство безопасности часто требует явного построения атаки или симулятора — «существует взломщик» неинформативно

Разбор случаев

**Доказательство разбором случаев** (proof by cases, case analysis) - техника, при которой мы делим область рассмотрения на исчерпывающие случаи и доказываем утверждение для каждого отдельно. Это как юридическая защита, рассматривающая все возможные сценарии: «Если мой клиент был дома - он невиновен. Если был в городе - есть алиби на каждый момент».

**Логическое обоснование:** Если P ∨ Q (случаи исчерпывающие), и мы доказали (P → R) и (Q → R), то R следует при любом раскладе. Это правило ∨-элиминации: из «A или B» и «A влечёт C» и «B влечёт C» следует C.

**Без потери общности (WLOG):** Иногда случаи симметричны. Можно сказать «без потери общности, пусть x ≤ y» - это сокращает работу вдвое, так как случай y ≤ x доказывается аналогично с перестановкой переменных.

Математическая индукция

**Математическая индукция** - техника доказательства утверждений вида «для всех натуральных n, P(n)». Идея проста: если первая костяшка домино падает, и падение каждой костяшки вызывает падение следующей - упадут все. Но в математике «все» действительно означает бесконечность.

**Принцип индукции:** Чтобы доказать ∀n ∈ ℕ. P(n), достаточно: 1) **База:** P(0) или P(1) - первый элемент удовлетворяет свойству 2) **Шаг:** ∀k. P(k) → P(k+1) - если свойство выполнено для k, то и для k+1

**Сильная индукция:** Иногда для доказательства P(k+1) нужны не только P(k), но и P(k-1), P(k-2), ... Сильная индукция позволяет в шаге предполагать P(j) для всех j < k+1. Пример: доказательство того, что каждое n > 1 раскладывается на простые множители.

**Структурная индукция:** Обобщение на рекурсивно определённые структуры (деревья, списки, формулы). База - примитивные элементы, шаг - составные конструкции. Если свойство верно для листьев дерева и сохраняется при объединении поддеревьев - верно для всего дерева.

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

**Конструктивное доказательство** не просто утверждает, что объект существует - оно показывает, как его построить. Это разница между «где-то в городе есть ресторан» и «вот адрес: улица Пушкина, дом 15». В программировании это значит - предоставить не just типы, а working code.

**Соответствие Карри-Говарда:** Конструктивное доказательство ∃x.P(x) - это пара (witness, proof), где witness - конкретный объект x₀, а proof - доказательство P(x₀). Доказательство A → B - это функция, преобразующая доказательство A в доказательство B.

**Конструктивизм в программировании:** В языках с зависимыми типами (Coq, Agda, Idris) доказательство существования - это код, который вычисляет объект. Вы не можете просто сказать «либо p, либо ¬p» - вы должны написать алгоритм, который решает, какое именно.

**Закон исключённого третьего:** Классическая логика принимает P ∨ ¬P как аксиому. Конструктивная логика требует алгоритм выбора. Это не значит, что конструктивизм слабее - он строже. Многие теоремы верны в обеих логиках, но конструктивные доказательства информативнее.

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

**Доказательство существования** (∃x.P(x)) утверждает, что объект с заданным свойством есть. Существует три основных подхода: **конструктивный** (назвать объект), **счётный** (подсчитать и показать > 0), и **от противного** (предположить отсутствие, получить противоречие).

**Вероятностный метод Эрдёша:** Если случайный объект имеет свойство P с ненулевой вероятностью, то объект с P существует. Это неконструктивно (не указывает конкретный объект), но чрезвычайно мощно в комбинаторике.

**Неконструктивность от противного:** Доказательство Евклида о бесконечности простых неконструктивно: оно показывает, что конечность ведёт к противоречию, но не строит бесконечную последовательность простых. Для каждого N мы знаем «есть простое > N», но не какое именно без факторизации.

**Экзистенциальная сила:** Иногда неконструктивные доказательства - единственный путь. Теорема Брауэра о неподвижной точке: непрерывное отображение диска в себя имеет неподвижную точку. Доказательство через алгебраическую топологию не указывает координаты точки.

Ключевые идеи

• **Разбор случаев** делит область на исчерпывающие подмножества и доказывает для каждого; требует убедиться, что случаи покрывают всё
• **Математическая индукция** — доказательство для бесконечных множеств через базу и шаг; сильная индукция позволяет использовать все предыдущие факты
• **Конструктивные доказательства** строят объект явно, в отличие от неконструктивных, которые лишь утверждают существование
• **Доказательства существования** используют разные методы: свидетель, противоречие, подсчёт, вероятность — с разным уровнем информативности

Связанные темы

Техники доказательств связаны с:

• Доказательство от противного — Альтернативный метод, часто неконструктивный
• Натуральная дедукция — Формализует правила вывода для каждой техники
• Кванторы — Индукция доказывает ∀n, конструкции - ∃x

Вопросы для размышления

• Почему конструктивное доказательство информативнее неконструктивного, хотя оба доказывают одно утверждение?
• Приведите пример задачи, где разбор случаев — естественный подход, а индукция — нет (и наоборот)
• Если вы доказали теорему неконструктивно, когда стоит искать конструктивное доказательство, а когда — нет?

Связанные уроки

• ml-03