Математическая индукция

[Neopoznanno]

Всем добрый день!
У меня появилось непонимание насчёт корректности математической индукции, для пояснения проиллюстрирую его на двух задачах:

1) Доказать с помощью мат индукции, что $1 + 2 + 3 + ... + n = \frac{n \cdot (n + 1)}{2}$
В этой задаче мы проверяем базу при n = 1, показываем индукционный шаг и говорим, что раз это выполнено, то утверждение доказано.

2) Есть известная задачка про то, что все лошади одной масти. Даётся её доказательство методом мат индукции и спрашивается где ошибка. В этом случае мы говорим, что ошибка находится в базе, т.к. она не верна для n = 2 (хотя верна дня n = 1)

Теперь вопрос, а почему в первом случае мы говорим, что доказательство корректно? А вдруг на каком-нибудь n база не сработает. В таком случае вообще весь метод под сомнение ставится, т.к. нам для проверки базы надо бы проверить вообще все значения.

[nnosipov]

Neopoznanno в сообщении #1459491 писал(а):

В этом случае мы говорим, что ошибка находится в базе

Ничего такого мы не говорим. База --- при $n=1$ и только. Она верна. А вот с шагом индукции как раз проблема.

[Neopoznanno]

Можно поподробней? На википедии написано, что ошибка в базе. В книге Кнута "Конкретная математика" написано "Доказательство безупречно за исключением случая n = 2. Если все пары лошадей состоят из лошадей одинаковой масти, то данное утверждение справедливо для любого числа лошадей". Т.е. тоже говорится, что проблема в базе...

-- 02.05.2020, 12:43 --

Да и у нас на первом курсе мат анализа как-то доказывалось, что через любое количество точек можно провести одну прямую и говорилось, что здесь ошибка в базе (надо проверить для 3х точек)

[nnosipov]

Neopoznanno в сообщении #1459497 писал(а):

Можно поподробней?

База может быть разной. Если база --- это только $n=1$, то ошибка не в базе (я вот студентам именно так и рассказываю). А если база --- это $n=1$ и $n=2$, то тогда да, ошибка в базе.

[Neopoznanno]

Непонятно.

Ну хорошо, берём задачу про лошадей. База при $n = 1$ верна, как Вы сказали, ошибки нет и копать в эту сторону мы вообще не будем. Но где ошибка в шаге? У Кнута приводится доказательство, которое он называет корректным (но он конечно, возможно ошибается) и он говорит, что ошибка именно в том, что мы не проверяем базу для $n = 2$

[nnosipov]

Neopoznanno в сообщении #1459499 писал(а):

Но где ошибка в шаге?

Ну, Вы напишите подробно этот шаг индукции, проанализируйте рассуждение и найдите ошибку. Вы хотите, чтобы я за Вас это сделал?

[Neopoznanno]

Нет, я не это хотела сказать.

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

Я допускаю, что вышеперечисленные три источника могли ошибаться, поэтому хотелось бы поступить так:
1) Я пишу доказательство из книги Кнута, и Вы мне скажете, есть там ошибка в шаге или нет.
2.1) Если Вы не находите ошибку, то тему хочется продолжить и получить ответ на изначальный вопрос.
2.2) Если Вы её находите, то говорите, что ошибка есть и я честно иду уже не в первый раз искать в шаге, где она. При этом хотелось бы чтобы другие участники форума не оставались в стороне и по возможности написали правы Вы или нет.

Само упражнение:
То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так:

„Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует n лошадей (с номерами от 1 до n) По индуктивному предположению лошади с номерами от 1 до n одинаковой масти, и, аналогично, лошади с номерами от 2 до n имеют одинаковую масть. Но лошади посредине с номерами от 2 до n не могут изменять масть в зависимости от того, как они сгруппированы, — это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до n также должны быть одинаковой масти. Таким образом, все n лошадей одинаковой масти. чтд"

Есть ли ошибка в приведенном рассуждении и какая именно?


Вот здесь topic87949-30.html обсуждался этот вопрос. В частности есть такая фраза:
"Правильно, как мне кажется, доказывать именно по лошадям, а не по количеству лошадей. То есть тут правильным будет квантор существования, а не всеобщности."

В этом случае я понимаю, почему ошибка в шаге. Но допустим, что мне не показалось правильным доказывать именно по лошадям, а мне кажется, что правильно доказывать по количеству лошадей. В этом случае обсуждение закончилось тем, что нужно проверить базу при $n = 2$. Кажется моё непонимание только увеличилось, пока это писала:(

[nnosipov]

Neopoznanno в сообщении #1459506 писал(а):

Само упражнение:
То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так:

„Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует n лошадей (с номерами от 1 до n) По индуктивному предположению лошади с номерами от 1 до n одинаковой масти, и, аналогично, лошади с номерами от 2 до n имеют одинаковую масть. Но лошади посредине с номерами от 2 до n не могут изменять масть в зависимости от того, как они сгруппированы, — это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до n также должны быть одинаковой масти. Таким образом, все n лошадей одинаковой масти. чтд"

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

[Xaositect]

Neopoznanno в сообщении #1459497 писал(а):

В книге Кнута "Конкретная математика" написано "Доказательство безупречно за исключением случая n = 2. Если все пары лошадей состоят из лошадей одинаковой масти, то данное утверждение справедливо для любого числа лошадей". Т.е. тоже говорится, что проблема в базе...

В вашей цитате не говорится, что проблема в базе. Как раз таки наоборот, проблема в индукционном переходе - при значении $n = 2$ рассуждения в индукционном переходе некорректны --- а именно, в этом случае нет лошадей с номерами от 2 до $n-1$, которые там упоминаются.
В формулировке в "Конкретной математике" вообще $n$ появляется только в индукционном переходе.

Либо в русском переводе, либо в Вашей цитате опечатка, там в нескольких местах не $n$, а $n-1$:

Цитата:

All horses are the same color; we can prove this by induction on the number of horses in a given set. Here's how:
"If there's just one horse, then it's the same color as itself, so the basis is trivial. For the induction step, assume that there are n horses numbered $1$ to $n$. By the induction hypothesis, horses $1$ through $n - 1$ are the same color, and similarly horses $2$ through $n$ are the same color. But the middle horses, $2$ through $n - 1$, can't change color when they're in different groups; these are horses, not chameleons. So horses $1$ and $n$ must be the same color as well, by transitivity. Thus all n horses are the same color; QED."
What, if anything, is wrong with this reasoning?

[nnosipov]

Xaositect в сообщении #1459509 писал(а):

Как раз таки наоборот, проблема в индукционном переходе - при значении $n = 2$ рассуждения в индукционном переходе некорректны --- а именно, в этом случае нет лошадей с номерами от 2 до $n-1$, которые там упоминаются.

Не знаю, как другие, но мои студенты это вполне способны переварить (и даже иногда сами догадываются, в чем дело).

Как обычно, все дело в неряшливости (надеюсь, она не была преднамеренной).

Upd. Посмотрел: русский перевод адекватен оригиналу.

[Neopoznanno]

Xaositect
Да, я опечаталась, вы правы.

nnosipov, Xaositect, спасибо за ваши ответы, становится понятней, но остался ещё один вопрос.

Xaositect

Вы утверждаете, что ошибка в том, что нет лошадей с номерами от 2 до $n - 1$, а здесь не работает такая логика:
В случае $n = 2$ множество этих лошадей пусто, а про пустое множество можно сказать всё что угодно, в том числе и что это множество лошадей одной масти?

[Mikhail_K]

Neopoznanno
Если база - это $n=1$, то ошибка в шаге - в том смысле, что при $n=1$ рассуждение справедливо, но из справедливости его с произвольным $n\geq 1$ не вытекает справедливость для $n+1$.
Ошибки в шаге не было бы, если бы база была $n=1,2$. (Но тогда была бы ошибка в базе.)

То есть тут нет противопоставления "ошибка в базе"/"ошибка в шаге". Те, кто говорят "ошибка в шаге" - имеют в виду, что при имеющейся базе рассуждения в шаге несправедливы. Те, кто говорят "ошибка в базе" - имеют в виду, что для того, чтобы рассуждения в шаге были справедливы, база должна быть другой. И те и другие правы.

Забудьте о вопросе, в базе ошибка или в шаге - этот вопрос без уточнения выше не имеет смысла. Важнее разобраться, где именно ошибка. Но для этого надо рассуждение вначале выписать от начала и до конца, правильно и внятно. То, что Вы написали выше - изобилует ошибками или опечатками.

Neopoznanno в сообщении #1459515 писал(а):

В случае $n = 2$ множество этих лошадей пусто, а про пустое множество можно сказать всё что угодно, в том числе и что это множество лошадей одной масти?

Ну, пусть можно так сказать. Какой тогда следующий логический шаг? В нём и ошибка.

[Xaositect]

Neopoznanno в сообщении #1459515 писал(а):

В случае $n = 2$ множество этих лошадей пусто, а про пустое множество можно сказать всё что угодно, в том числе и что это множество лошадей одной масти?

Проблема не в том, что нельзя сказать, что эти лошади одной масти.
Там делается такой переход: Есть множество лошадей от $1$ до $n-1$ одной масти; есть множество лошадей от $2$ до $n$ одной масти. Лошади от $2$ до $n-1$ принадлежат обоим множествам - значит масти в первом и во втором множестве совпадают. Здесь непустота пересечения существенна.

[epros]

Xaositect в сообщении #1459509 писал(а):

By the induction hypothesis, horses $1$ through $n - 1$ are the same color

Это что, multigrade predicate? О какой логике мы говорим? В классической логике первого порядка предикатов с неопределённым количеством переменных точно нет.

-- Сб май 02, 2020 13:10:18 --

В логике второго порядка есть адекватный заменитель для multigrade predicate, но там закон мат. индукции выглядит несколько иначе.

[arseniiv]

Предикате от множества.

-- Сб май 02, 2020 14:15:18 --

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

-- Сб май 02, 2020 14:16:25 --

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