метод математической индукции

[home-mik]

Всем доброго времени суток!

Читая главу про индуктивные доказательства книги "Введение в теорию автоматов, языков и вычислений", наткнулся на следующий фрагмент:

Цитата:

Пусть требуется доказать некое утверждение $S(n)$, которое зависит от целого числа n. Существует общий подход к доказательствам такого рода. Доказательство разбивается на следующие два этапа.

1. Базис. На этом этапе мы показываем, что $S(i)$ верно для некоторого частного целого значения $i$. Обычно полагают $i = 0$ или $i = 1$, но существуют примеры, где выбирается большее начальное значение, например, когда для всех меньших значений $i$ утверждение $S$ ложно.

2. Индуктивный переход. Здесь мы предполагаем, что $n\geqslant i$, где $i$ — целое число из базиса индукции, и доказываем, что из истинности $S(n)$ следует истинность $S(n + 1)$, т.е. доказываем утверждение “если $S(n)$, то $S(n + 1)$”. На уровне здравого смысла данное доказательство убеждает нас в том, что $S(n)$ на самом деле верно для всякого целого $n$, большего или равного базисному $i$. Обосновать это можно следующим образом. Предположим, что $S(n)$ ложно для одного или нескольких таких целых $n$. Тогда среди этих значений $n$ существует наименьшее, скажем, $j$, причем $j\geqslant i$. Значение $j$не может быть равным $i$, так как на основании базиса индукции $S(i)$ истинно. Поэтому $j$ должно быть строго больше $i$. Таким образом, мы знаем, что $j $–$ 1\geqslant i$ и $S(j $–$ 1)$ истинно.
Но во второй части доказательства показано, что если $n\geqslant i$, то $S(n)$ влечет $S(n + 1)$. Предположим, что $n = j $–$ 1$. Тогда, совершая индуктивный переход, из $S(j $–$ 1)$ выводим $S(j)$. Следовательно, из истинности $S(j $–$ 1)$ следует истинность $S(j)$. Но мы предполагали, что справедливо отрицание доказываемого утверждения, а именно: $S(j)$ ложно для некоторого $j\geqslant i$. Придя к противоречию, мы тем самым доказали методом “от противного”, что $S(n)$ истинно для всех $n\geqslant i$.

К сожалению, в приведенных рассуждениях присутствует трудноуловимый логический изъян. Дело в том, что первый пункт нашего предположения о том, что мы можем выбрать наименьшее$ j\geqslant i$, для которого $S(j)$ ложно, зависит от того, принимаем ли мы на веру справедливость принципа индукции. Это значит, что по сути единственный способ доказать существование такого $j$ есть индуктивное доказательство. Но с позиций здравого смысла приведенное нами “доказательство” вполне осмысленно, и соответствует нашему пониманию мира.

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

Спасибо!

[Null]

home-mik в сообщении #1510383 писал(а):

мы можем выбрать наименьшее $j \ge i$, для которого $S(j)$ ложно

Говориться о том, что это утверждение тоже надо доказывать. Можно доказать с помощью математической индукции. Получается цикл доказательств.

[arseniiv]

Иначе говоря, принцип математической индукции нам необходимо постулировать, он не выводится из чего-то ещё (кроме других формулировок этого принципа, типа структурной индукции, или например более сильной индукции по ординалам). Он для нас вполне очевиден, но любое его «честное» доказательство необходимо окажется ошибочным.

В более общих теориях оказывается, что возможность доказывать по индукции и определять вещи рекурсивно — это неотъемлемые спутники способов построить соответствующие объекты: вот натуральные числа мы можем получить двумя способами: или взять 0 «бесплатно», или «продать» уже имеющееся у нас натуральное $n$ и получить взамен $n + 1$. А наличие индукции/рекурсии позволяет нам гарантировать, что других способов нет, и строить что-то полезное на основе неизвестных нам заранее натуральных чисел, выходит у нас есть способы порождать натуральные числа и способы (один способ, но с другими объектами бывает несколько) их поглощать, некая симметрия. В логике такому аналогичны правила введения и удаления связок и кванторов.

[home-mik]

Null в сообщении #1510397 писал(а):

home-mik в сообщении #1510383 писал(а):

мы можем выбрать наименьшее $j\geqslant i$, для которого $S(j)$ ложно

Говориться о том, что это утверждение тоже надо доказывать. Можно доказать с помощью математической индукции. Получается цикл доказательств.

Мы же сами предположили, что для некоторых $n\geqslant i$ $S(n)$ ложно. Зачем еще доказывать, что из этих n можно выбрать наименьшее? Может быть ситуация, когда нельзя выбрать? Т.е. набор чисел есть, а наименьшее из них выбрать нельзя, это как?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Во всех постах, пож-ста.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[home-mik]

arseniiv в сообщении #1510404 писал(а):

Иначе говоря, принцип математической индукции нам необходимо постулировать, он не выводится из чего-то ещё (кроме других формулировок этого принципа, типа структурной индукции, или например более сильной индукции по ординалам). Он для нас вполне очевиден, но любое его «честное» доказательство необходимо окажется ошибочным.

В более общих теориях оказывается, что возможность доказывать по индукции и определять вещи рекурсивно — это неотъемлемые спутники способов построить соответствующие объекты: вот натуральные числа мы можем получить двумя способами: или взять 0 «бесплатно», или «продать» уже имеющееся у нас натуральное $n$ и получить взамен $n + 1$. А наличие индукции/рекурсии позволяет нам гарантировать, что других способов нет, и строить что-то полезное на основе неизвестных нам заранее натуральных чисел, выходит у нас есть способы порождать натуральные числа и способы (один способ, но с другими объектами бывает несколько) их поглощать, некая симметрия. В логике такому аналогичны правила введения и удаления связок и кванторов.

Я единственно что не понял из ваших слов, как рекурсия гарантирует, что другого способа построить объекты, скажем натуральные числа, нет. И я так понимаю, поэтому же я не понял слова автора книги о том, что

Цитата:

что по сути единственный способ доказать существование такого $j$ есть индуктивное доказательство

Мне непонятно, во-первых, почему оно единственное, а во-вторых, зачем вообще это доказывать?

Нет, если мы изначально даем определение натуральных чисел, как рекурсивно построенных объектов, то тогда понятно. Тогда любое натуральное число просто по определению не построить без принятия на веру принципа математической индукции. Но автор про проблему введения натуральных чисел не упоминал. У него проблемы начались только когда понадобилось выбрать наименьшее $j\geqslant i$, для которого $S(j)$ ложно, как будто эта проблема касается только этого утверждения, а не всех натуральных чисел в принципе.

[пианист]

home-mik в сообщении #1510445 писал(а):

во-первых, почему оно единственное

Дык доказательство "для всех $n \in \mathbb N$" просто не может быть не по индукции, нет других способов, т.к. $\mathbb N$ изначально так выстроено, в виде бесконечной очереди. Либо будет опираться на такие утверждения, те, возможно, тоже, но в конечном итоге вопрос все равно сведется к индукции.
А формулировки (равносильные) принципа индукции могут быть разные, в т.ч. что любое множество натуральных чисел содержит минимальное число.

home-mik в сообщении #1510445 писал(а):

а во-вторых, зачем вообще это доказывать

Можно и не доказывать. Собс-но, такие вещи только в матлогике доказывают, а в "обычной" математике используют как очевидные.

[home-mik]

пианист в сообщении #1510447 писал(а):

home-mik в сообщении #1510445 писал(а):

во-первых, почему оно единственное

Дык доказательство "для всех $n \in \mathbb N$" просто не может быть не по индукции, нет других способов, т.к. $\mathbb N$ изначально так выстроено, в виде бесконечной очереди. Либо будет опираться на такие утверждения, те, возможно, тоже, но в конечном итоге вопрос все равно сведется к индукции.
А формулировки (равносильные) принципа индукции могут быть разные, в т.ч. что любое множество натуральных чисел содержит минимальное число.

Ну то есть, просто по определению, получается. Меня, видимо, с панталыку сбило то, что автор об этой проблеме упомянул только в контексте поиска наименьшего числа, а не в общем контексте определения натуральных чисел в принципе.

Причем он дальше пишет о возможности определить целые числа рекурсивно, но только как о возможности, а не как о единственном способе:

Цитата:

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

Согласитесь, звучит так, как будто можно определить (рекурсивно), а можно и не определить, а определить как-нибудь по-другому. А тут получается, что по-другому и нельзя никак.

[svv]

home-mik в сообщении #1510419 писал(а):

Мы же сами предположили, что для некоторых $n\geqslant i$ $S(n)$ ложно. Зачем еще доказывать, что из этих n можно выбрать наименьшее?

Потому что существование наименьшего $j\geqslant i$, при котором $S(j)$ ложно, противоречит либо базе индукции (если $j=i$), либо индуктивному переходу (если $j>i$).
Для других $n>j$, из того, что $S(n)$ ложно, противоречия не получается, потому что $S(n-1)$ тоже может быть ложно.

home-mik в сообщении #1510419 писал(а):

Может быть ситуация, когда нельзя выбрать? Т.е. набор чисел есть, а наименьшее из них выбрать нельзя, это как?

Ну, например: а вдруг получится как с вещественными числами — для какого наименьшего вещественного числа $x$ неравенство $x\leqslant 17$ ложно?

[arseniiv]

home-mik в сообщении #1510445 писал(а):

Я единственно что не понял из ваших слов, как рекурсия гарантирует, что другого способа построить объекты, скажем натуральные числа, нет.

А присмотритесь к индукции (и рекурсии): она выглядит как разбор случаев:
(1) что если число — 0? (докажем про него наше утверждение или построим для него объект);
(2) что если число — последователь другого числа, для которого мы утверждение доказали или объект построили? (и тут докажем/построим)
— и если мы управились с этими двумя случаями, то мы доказали/построили для всех натуральных чисел. То есть если есть другие способы построения натуральных чисел, их почему-то не пришлось учесть; вероятно, они дают те же числа, которые можно получить и без них, так что такие способы можно просто забыть — от них нет помощи.

Хотя последнее намекает: а вдруг это не всегда так? И действительно мы можем построить аналогичным индуктивным определением (есть ноль, есть последователь, результаты построения начиная с разных чисел разные, индукция) счётные множества, которые более-менее натурально отображаются в натуральные (и из них), например мы можем взять такие конструкторы:
(a) 1 (в этот раз естественнее будет без нуля);
(b) $n \mapsto 2 n$;
(c) $n \mapsto 2 n + 1$.
а индукция будет иметь вид «если $A(1)$, также для любого $n$, если $A(n)$ влечёт $A(2 n)$ и $A(2 n + 1)$, то для всех натуральных $n$ выполнено $A(n)$». Для такой системы мы тоже можем определить сложение, умножение и тому подобное, а также довольно простые переводы из этой системы натуральных чисел в ту и назад (эта в какой-то мере связана с двоичной записью чисел: (b) и (c) делают битовый сдвиг влево с возможным заполнением появившегося справа нуля единицей — а та с унарной записью в виде набора палочек — каждое прибавление единицы ещё одна палочка).

Главное, что и тут, и там индукция гарантирует, что нам достаточно тех способов, которые мы перечислили, чтобы породить все натуральные числа. «Нет других» — возможно, действительно не лучшая формулировка.

-- Пн мар 22, 2021 17:37:37 --

Да, ещё индукция может быть (на первый взгляд) более сильной, чем «надо», одна из широко применяемых имеет индуктивный переход «если для всех $m < n$ выполнено $A(m)$, то $A(n)$». Она эквивалентна обычной. Я бы сказал, что эту индукцию лучше считать теоремой, а ту постулировать, но это может оказаться вопросом вкуса. Кстати из этой индукции можно полностью убрать базу: она получается из перехода, если взять $n = 0$: «если для всех $m < 0$ выполнено $A(m)$, то $A(0)$» эквивалентно просто $A(0)$, потому что $m < 0$ нет и нам остаётся доказывать $A(0)$ безусловно. В такой форме это всё выходит уже частным случаем ординальной индукции (в ней будет добавлено всего лишь ещё одно требование).

[home-mik]

arseniiv в сообщении #1510487 писал(а):

home-mik в сообщении #1510445 писал(а):

Я единственно что не понял из ваших слов, как рекурсия гарантирует, что другого способа построить объекты, скажем натуральные числа, нет.

А присмотритесь к индукции (и рекурсии): она выглядит как разбор случаев:
(1) что если число — 0? (докажем про него наше утверждение или построим для него объект);
(2) что если число — последователь другого числа, для которого мы утверждение доказали или объект построили? (и тут докажем/построим)
— и если мы управились с этими двумя случаями, то мы доказали/построили для всех натуральных чисел. То есть если есть другие способы построения натуральных чисел, их почему-то не пришлось учесть; вероятно, они дают те же числа, которые можно получить и без них, так что такие способы можно просто забыть — от них нет помощи.

Хотя последнее намекает: а вдруг это не всегда так? И действительно мы можем построить аналогичным индуктивным определением (есть ноль, есть последователь, результаты построения начиная с разных чисел разные, индукция) счётные множества, которые более-менее натурально отображаются в натуральные (и из них), например мы можем взять такие конструкторы:
(a) 1 (в этот раз естественнее будет без нуля);
(b) $n \mapsto 2 n$;
(c) $n \mapsto 2 n + 1$.
а индукция будет иметь вид «если $A(1)$, также для любого $n$, если $A(n)$ влечёт $A(2 n)$ и $A(2 n + 1)$, то для всех натуральных $n$ выполнено $A(n)$». Для такой системы мы тоже можем определить сложение, умножение и тому подобное, а также довольно простые переводы из этой системы натуральных чисел в ту и назад (эта в какой-то мере связана с двоичной записью чисел: (b) и (c) делают битовый сдвиг влево с возможным заполнением появившегося справа нуля единицей — а та с унарной записью в виде набора палочек — каждое прибавление единицы ещё одна палочка).

Главное, что и тут, и там индукция гарантирует, что нам достаточно тех способов, которые мы перечислили, чтобы породить все натуральные числа. «Нет других» — возможно, действительно не лучшая формулировка.

-- Пн мар 22, 2021 17:37:37 --

Да, ещё индукция может быть (на первый взгляд) более сильной, чем «надо», одна из широко применяемых имеет индуктивный переход «если для всех $m < n$ выполнено $A(m)$, то $A(n)$». Она эквивалентна обычной. Я бы сказал, что эту индукцию лучше считать теоремой, а ту постулировать, но это может оказаться вопросом вкуса. Кстати из этой индукции можно полностью убрать базу: она получается из перехода, если взять $n = 0$: «если для всех $m < 0$ выполнено $A(m)$, то $A(0)$» эквивалентно просто $A(0)$, потому что $m < 0$ нет и нам остаётся доказывать $A(0)$ безусловно. В такой форме это всё выходит уже частным случаем ординальной индукции (в ней будет добавлено всего лишь ещё одно требование).

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

-- 23.03.2021, 10:39 --

svv в сообщении #1510481 писал(а):

home-mik в
[quote="home-mik в сообщении #1510419 писал(а):

Может быть ситуация, когда нельзя выбрать? Т.е. набор чисел есть, а наименьшее из них выбрать нельзя, это как?

Ну, например: а вдруг получится как с вещественными числами — для какого наименьшего вещественного числа $x$ неравенство $x\leqslant 17$ ложно?

А каким образом индукция позволяет доказать, что для натуральных чисел такое число (наименьшее из множества) можно выбрать? Т.е. как из принципа наименьшего числа индукция доказывается, понятно. А вот наоборот - не очень. Или это очевидно уже из того, что сами натуральные числа строятся по индукции, которая начинается с базы, и вот эта самая база и есть наименьшее число?

[mihaild]

home-mik в сообщении #1510560 писал(а):

А каким образом индукция позволяет доказать, что для натуральных чисел такое число (наименьшее из множества) можно выбрать?

Пусть у нас есть множество натуральных чисел $A$, в котором нет наименьшего. Рассмотрим предикат $P(x) := \forall y \in A: y > x$ - "все элементы $A$ больше $y$". По индукции можно доказать, что он истинен для всех натуральных чисел: $P(0)$ истинно (иначе $0 \in A$ и $0$ - наименьший элемент $A$). Если же $P(x) \wedge \neg P(x + 1)$, то $x + 1$ - наименьший элемент $A$, а таких нет, так что $P(x) \rightarrow P(x + 1)$.
Таким образом, $\forall x: P(x)$. Но если $x_0 \in A$, то $\neg P(x_0)$. Значит $A$ пусто.

[vpb]

home-mik
Я вот такую вещь заметил среди участников форума. У изучающих математику самостоятельно их познавательная активность часто заезжает на совершенно побочную колею, а именно: преувеличенного интереса к матлогике, основаниям, теории множеств, а в последнее время и теории категорий. И так она в этой колее и остается, люди там гибнут. Я тоже через это прошел, но как-то очень быстро. Помню, в десятом классе еще за один день прочитал книжку Успенский, Теорема Гёделя о неполноте (из серии "Популярные лекции о математике"), хмыкнул: "Хе, любопытно !", и на следующий день продолжил заниматься нормальной математикой. Дело в том, что когда есть чем заниматься (меня вот в те времена очень интересовали простые числа, типа проблема Гольдбаха, распределение простых чисел и т.д.; потом, правда, изменились интересы), всякая заумь быстро из головы вылетает. (Я не отрицаю ценность знания основ матлогики как таковых, но не склонен переоценивать.)

Короче, имейте это в виду, а то вдруг головой не туда двинетесь ...

[arseniiv]

Ну индукция это ещё не матлогика, это соседствует со всякими практическими конструкциями особенно в алгоритмах. Например мы хотим доказать, что какой-то алгоритм с рекурсией под капотом даёт результат для всех входных данных, которые мы хотели, придумывая его, если сам тип данных достаточно сложный. Часто поможет какая-то форма индукции, и часто это может быть структурная индукция, которую с полпинка, без понимания «основ» обычной натуральночисленной индукции не обязательно правильно нарисуешь. Имеется в виду не индукция по монотонной натуральночисленной величине, а по самим объектам, что бывает удобнее (а бывает нет), и тогда нужно знать, что индукция «перебирает способы построения». Тогда не нужно будет удостоверяться, что наша индукция выводится из индукции для $\mathbb N$, можно будет сразу знать, порядок или что-то упущено.

Кстати это напомнило мне добавить, что иногда есть нужда в индуктивном доказательстве сразу нескольких утверждений (или рекурсивном определении нескольких объектов; ну это уже можно наверно не оговаривать) о нескольких множествах, элементы которых строятся через друг друга (то есть эти множества определены взаимно индуктивно). Например представим себе такие множества строк $A, B$ (пример немного искусственный, лень искать хороший), для которых:
- $\mathtt A \in A$;
- для всех $b \in B$, $bb \in A$;
- $\mathtt B \in B$
- для всех $a_1, a_2 \in A$, $a_1 \mathtt C a_2 \in B$;
- и никаких других элементов в $A, B$ нет.

Скажем, мы хотим доказать, что в любой строке $a \in A$ букв $\mathtt C$ меньше половины. Нам это удастся очень просто, если мы согласимся доказывать это одновременно с доказательством, что в $b \in B$ наблюдается то же (вообще обычно мы будем доказывать разные утверждения, но тут мне лень было думать и получается одно и то же для обоих множеств), а именно всё выйдет вот так:
- очевидно, что в $\mathtt A$ букв $\mathtt C$ ноль, меньше $1/2$;
- если в $b$ букв $\mathtt C$ меньше половины, то же верно и для $bb$;
- очевидно и для $\mathtt B$;
- если в $a_1, a_2$ букв $\mathtt C$ по $n_1, n_2$, то в $b := a_1 \mathtt C a_2$ их $n = n_1 + n_2 + 1$; так как $n_1 + n_2 < \frac12(|a_1| + |a_2|)$, то $n < \frac12 (|a_1| + |a_2|) + 1$, и т. к. $n$ целое, это даёт нам сказать и $n < \frac12 (|a_1| + |a_2| + 1) = \frac12 |b|$. Всё!