В рамках курса 6.1200 в Массачусетском технологическом институте (MIT) профессор Закари Абель представил фундаментальные методы построения математических доказательств. Лекция охватывает логические выводы, стратегии работы с теоремами существования и всеобщности, а также глубокое погружение в методы доказательства от противного и математическую индукцию.
🧠 Логические выводы и правила вывода 1:06
Математическое доказательство строится из последовательности логических дедукций, начиная от базового набора аксиом . Правило вывода (inference rule) — это алгоритм объединения истинных пропозиций для формирования новых истинных утверждений .
Профессор Абель выделяет несколько классических правил:
- Modus ponens: если известно $P$ и известно, что $P$ влечет $Q$, то $Q$ истинно .
- Modus tollens: если $P$ влечет $Q$, но $Q$ ложно, то $P$ также должно быть ложным .
- Доказательство через ложь: если отрицание $P$ влечет ложь, то $P$ истинно .
Для проверки этих правил можно использовать таблицы истинности, что гарантирует их справедливость при любых значениях переменных . Однако лектор призывает не перерисовывать таблицы в каждом доказательстве, а использовать правила как понятные инструменты, если они очевидны из контекста .
Опасность «доказательства запугиванием»
Закари Абель настоятельно рекомендует исключить из математического словаря фразы «очевидно, что...», «это интуитивно понятно» или «ясно, что...» . По мнению профессора, использование таких слов — это «доказательство запугиванием» (proof by intimidation), которое несет три риска:
- Читатель (или проверяющий) может не счесть это очевидным, что приведет к потере баллов или демотивации .
- Фраза часто маскирует ошибку: автор пропускает шаг вместо того, чтобы его доказать .
- Доказательство существует именно для проверки правильности, и пропуск шагов лишает систему избыточности, помогающей ловить ошибки .
📋 Структуры и шаблоны доказательств 8:21
Для типичных математических утверждений существуют стандартные «шаблоны» (outlines), которые помогают структурировать мысли и не упустить важное.
Теоремы существования ($\exists$)
Чтобы доказать утверждение «существует $x$ в множестве $S$, обладающий свойством $P$», стандартный путь выглядит так:
- Выбрать конкретное значение $x$ .
- Показать, почему это $x$ принадлежит множеству $S$.
- Доказать, почему для этого $x$ выполняется свойство $P$ .
Например, для доказательства существования простого числа $n \ge 10$ достаточно выбрать $n = 17$, подтвердить его принадлежность к натуральным числам и проверить отсутствие делителей .
Универсальные теоремы ($\forall$)
Для доказательства утверждения «для всех $x$ в множестве $S$ верно $P(x)$»:
- Предположить, что $x$ — произвольный (generic) элемент множества $S$ .
- В процессе доказательства нельзя выбирать конкретное значение или использовать дополнительные свойства $x$, кроме его принадлежности к $S$ .
- Вывести свойство $P(x)$ .
Импликации ($P \implies Q$)
Прямое доказательство импликации начинается с предположения, что $P$ истинно . Это создает гипотетическую среду, в которой $P$ принимается как факт, из которого нужно вывести $Q$ .
🔄 Доказательство от противного и контрапозиция 21:56
Если прямое доказательство затруднено, используются косвенные методы.
- Метод контрапозиции: вместо «$P \implies Q$» доказывается эквивалентное утверждение «не $Q \implies$ не $P$» . Например, чтобы доказать «если $n^2$ четное, то $n$ четное», проще доказать «если $n$ нечетное, то $n^2$ нечетное» .
- Доказательство от противного (by contradiction):
Классический пример: иррациональность $\sqrt{2}$
Профессор Абель демонстрирует этот метод на доказательстве того, что $\sqrt{2} \notin \mathbb{Q}$ .
- Предположим, $\sqrt{2} = a/b$, где дробь несократима (нет общих делителей) .
- Тогда $a^2 = 2b^2$, значит, $a^2$ четное, и $a$ четное .
- Раз $a = 2c$, то $4c^2 = 2b^2$, откуда $2c^2 = b^2$, значит, $b$ тоже четное .
- Противоречие: мы предположили, что дробь несократима, но нашли общий делитель 2 .
🪜 Математическая индукция: принцип домино 44:11
Индукция часто кажется студентам сложной из-за «архаичных формулировок», похожих на «призыв древнего демона» . Однако, по словам Абеля, это интуитивно понятный механизм, напоминающий падение бесконечного ряда домино.
Для доказательства того, что свойство $P(n)$ верно для всех $n \ge 0$, необходимо:
- Базовый случай (Base case): доказать $P(0)$ .
- Индуктивный переход (Inductive step): доказать, что если $P(n)$ верно, то верно и $P(n+1)$ .
Пример: Сумма натуральных чисел
Для формулы $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ интуиция подсказывает, что переход от $n$ к $n+1$ — это просто добавление члена $(n+1)$ к обеим частям равенства . Алгебраическая проверка подтверждает, что если формула верна для $n$, она автоматически становится верной для $n+1$ .
Принцип индукции — это фактически аксиома о строении натуральных чисел: если начать с нуля и бесконечно прибавлять единицу, мы пройдем через все числа .
🧩 Задача об L-тромино 1:05:32
Для визуализации силы индукции профессор использует задачу о замощении двоичного квадрата (сторона $2^n \times 2^n$) фигурками L-тромино (уголки из 3 клеток). Теорема гласит: любой такой квадрат, из которого удалена одна любая клетка, можно полностью заполнить L-тромино .
Доказательство по индукции:
- База ($n=1$): Квадрат $2 \times 2$ без одной клетки — это и есть одна фигурка L-тромино. Решено .
- Переход ($n \to n+1$): Квадрат $2^{n+1} \times 2^{n+1}$ делится на четыре квадранта размером $2^n \times 2^n$ .
- Один квадрант уже содержит «удаленную» клетку (по условию).
- Ключевая идея: Поместим одно L-тромино в центр доски так, чтобы оно занимало по одной клетке в каждом из трех оставшихся квадрантов .
- Теперь каждый из четырех квадрантов имеет ровно одну «отсутствующую» клетку.
- По индуктивному предположению, мы умеем мостить такие квадраты $2^n$. Следовательно, вся доска замостится .
Этот алгоритм рекурсивен: чтобы замостить доску $16 \times 16$, мы разбиваем её до тех пор, пока не дойдем до базовых блоков $2 \times 2$ .
