«Парадокс исследователя»

9

Л. Цинман

«Парадокс исследователь»

При доказательстве утверждения методом математической индукции инота возникает необходимая ситуация. Проиллюстрируем ее на двух примерах.

Пример 1

Докажем методом математической индукции, что для всех натуральных $n$ справедливо следующее утверждение: сумма кубов первых $n$ натуральных чисел есть квадрат некомороо натурального числа.

Обозначим это утверждение через $A(n)$. Доказательства методом математической индукции проводятся, как известно, в два этапа.

a) Базис идукции: $A(1)$. Убеждаемся в справедливости $A(1)$:
$$1^3 = 1^2.$$
6) Иndукции шаг: $A(k) \Rightarrow A(k+1)$. Предположим, что для неокоторого натурального числа $k$ справедливо утверждение $A(k)$, и докажем, что тогда справедливо и $A(k+1)$. Итак, путь нашлось такое натуральное число $p$, для которого
$$1^3 + 2^3 + \ldots + k^3 = p^2.$$ (1)
Докажем, что тогда существует такое натуральное число $q$, для которого
$$1^3 + 2^3 + \ldots + k^3 + (k+1)^3 = q^2.$$ (2)
Из (2) и (1) следует, что нам надо доказать существование такого $q$, для которого
$$(k+1)^3 = q^2 - p^2.$$ (3)

Но как это можно было бы доказать? Естественно пути доказательства не видно.

Итак, попытка доказать нашей утверждение неосредственным применением метода математической индукции наолкнулась на трудности при проведении индукционного шага.

Вернемся снова к рассмотрению $A(n)$ и проверим его справедливость для нескольких начальных значений $n$:
$$1^3 = 1^2;$$
$$1^3 + 2^3 = 3^2;$$
$$1^3 + 2^3 + 3^2 = 6^2;$$
$$1^3 + 2^3 + 3^3 + 4^3 = 10^2;$$
$$1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 15^2.$$

Присмотревшись к этим равенствам, приходим к гипотезе: для всех натуральных $n$ справедливо утверждение: сумма кубов первых $n$ натуральных чисел есть квадрат натурального числа, равное сумме этих чисел.

Обозначим это утверждение через $B(n)$. Конечно, $B(n)$ несет в себе больше информации, чем $A(n)$, и потому его естественно считать более сильным утверждением. Доказав $B(n)$, мы получим справедливость $A(n)$ в качестве очевидного следствия.

Попробуем теперь применить метод математической индукции к доказательству усиленного утверждения.

a) Справедливость $B(1)$ фактически уже установлена:
$$1^3 = 1^2.$$
6) Допустим, что для неокоторого натурального числа $k$ справедливо $B(k)$:
$$1^3 + 2^3 + \ldots + k^3 = (1 + 2 + \ldots + k)^2.$$ (4)
Докажем, что тогда справедливо и $B(k+1)$:
$$1^3 + 2^3 + \ldots + k^3 + (k+1)^3 = (1 + 2 + \ldots + k + k + 1)^2.$$ (5)

10

Использовая равенство (4), можно свести доказательство равенства (5) к доказательству равенства
$$(k+1)^3 = (1+2+\ldots+k+k+1)^2 - (1+2+\ldots+k)^2 - \left[ \frac{(k+2)(k+1)}{2} \right]^2 - \left[ \frac{(k+1)k}{2} \right]^2 = (k+1)^3.$$

Преобразуем правило частей равенства (6):
$$(1+2+\ldots+k+k+1)^2 - (1+2+\ldots+k)^2 = \left[ \frac{(k+2)(k+1)}{2} \right]^2 - \left[ \frac{(k+1)k}{2} \right]^2 = (k+1)^3.$$

Итак, равенство (6) устанавливает. Тем самым для всех $n$ доказано $B(n)$, а значит, и $A(n)$.

Пример 2 *)
Однажды учитель задал ученикам на дом такую задачу: доказать, попытясь методом математической индукции, что для любого натурального числа $n$ верно равенство $A(n)$:
$$\frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1)}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n} < \frac{1}{\sqrt{n}}.$$

Коля В., садясь дома за доказательство этого равенства, случайно переписал условия равенства с ошибкой, добавив в знаменатель 1. Таким образом, он принял за доказательство более сильного равенства $B(n)$:
$$\frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1)}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n} < \frac{1}{\sqrt{n+1}}.$$

Вот его доказательство.
a) Убеждаемся в справедливости $B(1)$:
$$\frac{1}{2} < \frac{1}{\sqrt{2}}.$$
6) Покажем, что из справедливости $B(k)$ для некоторого натурального $k$
$$\frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1)}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2k} < \frac{1}{\sqrt{k+1}}$$
следует справедливо этого равенства и для $k+1$:
$$\frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1)(2k+1)}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2k} < \frac{1}{\sqrt{k+1}}$$
Для этого достаточно доказать, что
$$\frac{2k+1}{2k+2} < \frac{\sqrt{k}}{\sqrt{k+1}}.$$

Но равенство (9) равносильно неверному равенству $k+1 < 0$.

12

рого доказамельства не существует вообщее.

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

А разница в том, что в задачах на построение речь идет не о построениях вообщее, а о построениях molky с помощью циркуля и линейки. Таким образом, мы точно формулируем средства, которые собираемся использовать для решения. А в таком случае появляется возможность как-то описать класс задач, которые решаются этим средствами. Поэтому, когда нам предлагют конкретную задачу на построение, мы можем попытаться установить, принадлежит она этому классу или нет.

На рубеже XIX и XX веков был предложен такой способ построения математики, который позволяет получить доказательства в поле течно. Различные доказательства при этом способе в виде формальных систем.

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

Изучением формальных систем занимается математическая логика *). В этой статье не место писать о ней. Подчерком только, что решение вообщее

*) Школьнику, желающей ему познакомиться с математической логикой, мы рекомендуем книги P. P. Столла «Множества. Логика. Аксиматические теории» (М., «Провесшие», 1968), Э. Мендельсона «Введение в математической логики» (М., «Нayka», 1971) и П. С. Новикова «Элементы математической логики» (М., «Нayka», 1973).

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

Teорема

В рамках арифметики натуральных чисел, заданной в виде формальной системы, можно ответить на поставленный выше вопрос. Существует несколько — формальных арифметических систем. Пусть $S$ — одна из этих систем. Автором статьи получен следующий результат.

Teорема. В системе $S$ имеются парадоксальные пары.

В пункте 1 определения парадоксальной пары требуется, чтобы $A(n)$ было оченьным следствием $B(n)$. Понятие оченьного следствия, естественно, тоже требует уточнения. В доказательстве формулированной теоремы некоторых теорий конкретаная конью и кция $B(n)$ образует парадоксальную пару с любым м ее членом.

Коньонкиция нескольких утверждения сложно-сочинному предположению, составленному из этих утверждений с помощью союза «и». Таким образом, коньонкиция нескольких утверждений справедлива тогда и только тогда, когда справедливо каждое из этих утверждений. Позому естественному считать, что каждый коньонкия является ее оченьным следствием.

Сформирование теорема показывает, что в форматной арифметической системе действительное можно столкнуть с «парадоксом исследователя». Это надо учитывать и при содержательных расчудениях, использующих метод математической индукции.