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

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

Что вообще доказывают

Почти всегда — импликацию $P \Rightarrow Q$: «если выполнено $P$, то верно $Q$».

Важно, что импликация ложна только когда $P$ истинно, а $Q$ ложно. Если $P$ ложно, вся импликация истинна независимо от $Q$ — то самое «vacuously true», которое смущает при первой встрече.

Прямое доказательство

Предполагаем $P$, цепочкой шагов выводим $Q$.

Утверждение. Если $n$ чётно, то $n^2$ чётно.

Пусть $n = 2k$. Тогда $n^2 = 4k^2 = 2(2k^2)$, что чётно. $\square$

Скучно и работает в большинстве случаев. Символ $\square$ (или $\blacksquare$, или QED) означает конец доказательства.

Контрапозиция

$P \Rightarrow Q$ равносильно $\neg Q \Rightarrow \neg P$. Не «похоже», а именно равносильно — это одно и то же утверждение.

Приём полезен, когда отрицание $Q$ даёт больше зацепок, чем $P$.

Утверждение. Если $n^2$ чётно, то $n$ чётно.

Докажем контрапозицию: если $n$ нечётно, то $n^2$ нечётно. Пусть $n = 2k+1$, тогда $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ — нечётно. $\square$

Прямо это доказывать неудобно: из чётности $n^2$ трудно что-то извлечь. Из нечётности $n$ — легко.

Не путайте с обратным утверждением. $Q \Rightarrow P$ — это не то же самое, что $P \Rightarrow Q$. «Если идёт дождь, асфальт мокрый» не равносильно «если асфальт мокрый, идёт дождь». А вот «если асфальт сухой, дождя нет» — равносильно.

От противного

Предполагаем, что утверждение ложно, и выводим противоречие.

Утверждение. $\sqrt2$ иррационально.

Предположим противное: $\sqrt2 = p/q$ — несократимая дробь. Тогда $p^2 = 2q^2$, значит $p^2$ чётно, значит (по предыдущему утверждению) $p$ чётно, $p = 2m$. Подставляем: $4m^2 = 2q^2$, то есть $q^2 = 2m^2$, значит и $q$ чётно. Но тогда дробь сократима — противоречие. $\square$

Приём мощный, но легко им злоупотребить: часто доказательство «от противного» на самом деле является прямым, просто с лишней обёрткой.

Индукция

Доказываем утверждение $P(n)$ для всех натуральных $n$:

1. база: $P(0)$ (или $P(1)$) верно;
2. шаг: из $P(n)$ следует $P(n+1)$.

Это рекурсия, у которой доказана корректность: база — терминальный случай, шаг — рекурсивный вызов.

Утверждение. $\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$.

База: при $n = 1$ слева $1$, справа $1 \cdot 2 / 2 = 1$. Верно.

Шаг: пусть формула верна для $n$. Тогда $\sum_{i=1}^{n+1} i = \underbrace{\frac{n(n+1)}{2}}_{\text{индуктивное предположение}} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$ что и требовалось. $\square$

Сильная индукция — вариант, где на шаге разрешено пользоваться $P(k)$ для всех $k \le n$, а не только для $n$. Формально эквивалентна обычной, но иногда удобнее.

Контрпример

Чтобы опровергнуть $\forall x : P(x)$, достаточно одного $x$ с $\neg P(x)$. Это прямое следствие правила отрицания кванторов из предыдущего урока.

Асимметрия принципиальная: подтвердить «для всех» примерами нельзя, опровергнуть одним примером — можно. Отсюда практический навык: встретив утверждение, первым делом попробуйте его сломать на краевом случае — пустом множестве, нуле, отрицательном числе, совпадающих аргументах.

«Без ограничения общности»

W.l.o.g. означает: случаев несколько, но они симметричны, поэтому разбирается один.

Пусть $a \ne b$. Без ограничения общности $a < b$.

Здесь всё честно: случай $a > b$ получается переименованием. Но иногда за w.l.o.g. прячут пробел в рассуждении. Читая, стоит потратить секунду на вопрос «а действительно ли случаи симметричны».

Разрешите себе не понимать доказательства

Отдельное правило, которое экономит месяцы: можно пользоваться утверждением, не понимая его доказательства. Знать формулировку теоремы Эккарта–Янга и уметь применять SVD — полезно. Уметь доказывать её — почти никогда не нужно.

Границу проводите так: если утверждение вы используете, а доказательство только читаете — доказательство можно пропустить.