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

Как доказывают общие утверждения?

Мы уже знаем: утверждение о существовании («хотя бы один», «можно найти») доказывается одним подходящим примером. А как быть с общим утверждением («все», «каждый», «любой»)? Напомним: в нём говорится, что все элементы некоторого множества обладают определённым свойством.

Самый простой способ такое утверждение доказать — «испытать» по очереди все элементы множества: проверить для каждого нужное свойство. Когда элементы «закончатся» и все они выдержали проверку — утверждение доказано. Этот способ называют методом перебора.

Метод перебора. Чтобы доказать общее утверждение методом перебора, нужно по очереди проверить каждый элемент множества. Если множество конечно и все его элементы обладают нужным свойством — утверждение доказано.

Например, чтобы доказать, что в математическом кружке занимаются все мальчики из 5«А», достаточно найти фамилию каждого мальчика из классного журнала в списке участников кружка. Мальчиков в классе конечное число — значит, проверка когда-нибудь закончится.

Справа — похожая задача из упражнений к этому пункту: докажи методом перебора, что все числа из множества $\{20,\,56,\,101\}$ при делении на $9$ дают в остатке $2$.

Бесконечные множества — ловушка перебора

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

        💡 Из жизни: представь, что из непрозрачного мешка можно вытащить любое
        число разноцветных шаров. Если вытащить подряд тысячу, миллион или сколько угодно белых
        шаров — нет никакой гарантии, что следующий шар не окажется, скажем, красным. Поэтому
        перебором нельзя убедиться, что все шары в мешке белые. Попробуй сам справа —
        тяни шары один за другим.
      

⚠️ Частая ошибка: думать, что если утверждение проверено для очень многих (пусть даже миллионов) элементов бесконечного множества, то оно уже доказано для всех. Это не так! Сколько бы примеров мы ни проверили, всегда остаётся бесконечно много непроверенных — и именно среди них может скрываться опровергающий пример.

Утверждения, которые никто не доказал

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

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

Из упражнений к этому пункту

Упражнения к этому пункту заодно повторяют деление с остатком, проценты и смешанные числа — коротко освежим формулы.

Деление с остатком. $a = b\cdot c + r,\quad r < b$, где $a$ — делимое, $b$ — делитель, $c$ — неполное частное, $r$ — остаток.

Проценты: $a\%$ от числа $b$ равно

$$\dfrac{a}{100}\cdot b.$$

Смешанное число в виде неправильной дроби:

$$2\tfrac{3}{4} = \dfrac{2\cdot4+3}{4} = \dfrac{11}{4}.$$

🧠 Запомни:

Метод перебора доказывает общее утверждение, только если множество конечно — проверил каждый элемент, и всё.
Для бесконечного множества никакое конечное число проверок не доказывает общее утверждение — дальше всегда может найтись опровергающий пример.
Один контрпример полностью опровергает утверждение «все», сколько бы подтверждений до него ни было.
Некоторые математические утверждения до сих пор не доказаны и не опровергнуты.

← Глава 1 · §3, п.3 «Хотя бы один» Все темы Глава 1 · §3, п.5 → Введение обозначений

При делении на $9$ каждого числа из множества $\{20,\,56,\,101\}$ в остатке получается $2$

Нажми «Проверить следующее число»

Утверждение: «Все шары в мешке белые». Тяни шары один за другим — сколько проверок хватит, чтобы быть уверенным?

Вытянуто шаров: 0

Наведи курсор на подчёркнутые слова в тексте слева — интерактив сам переключится