Найти ошибку в рассуждениях (метод математической индукции)

[Skyfall]

Условие задачи:
Найдите ошибку в рассуждениях.
Докажем, что любые $n$ точек лежат на одной прямой. При $n=1$ и $n=2$ это очевидно благодаря соответствующей геометрической аксиоме. Осталось доказать это для произвольного $n$, предполагая, что для $n-1$ это верно. В самом деле, рассмотрим произвольные $n$ точек $A_1, A_2, ..., A_{n-1}, A_n$. Отбросим последнюю точку и применим предположение индукции. Получим прямую $l$, на которой лежат точки $A_1, A_2, ..., A_{n-1}$. Нам надо доказать, что и последняя точка $A_n $ лежит на этой прямой. Отбросим первую точку и применим предположение индукции к точкам $A_2, A_3, ..., A_n$. Получим, что они все лежат на некоторой прямой $l'$. Могут ли прямые $l$ и $l'$ быть различны? Нет, т.к. обе они проходят через точки $A_2$ и $A_{n-1}$, а как известно из той же аксиомы геометрии, через две точки можно провести только одну прямую. Значит, прямые $l$ и $l'$ совпадают и проходят через все $n$ точек.

Моя попытка:
Ошибка в

Цитата:

Отбросим первую точку и применим предположение индукции к точкам $A_2, A_3, ..., A_n$

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

[mihaild]

Skyfall в сообщении #1229970 писал(а):

Могут ли прямые $l$ и $l'$ быть различны? Нет, т.е. обе они проходят через точки $A_2$ и $A_{n-1}$,

Ошибка вот тут. Подставьте $n = 3$.

Skyfall в сообщении #1229970 писал(а):

Ведь нельзя использовать предположение индукции более одного раза?

Можно.

[Skyfall]

mihaild в сообщении #1229971 писал(а):

Ошибка вот тут. Подставьте $n = 3$.

Выходит задачка больше на внимательность) Спасибо.

mihaild в сообщении #1229971 писал(а):

Можно.

Может знаете примеры? Или можете объяснить в чем смысл?
Как я понимаю, в методе математической индукции делается предположение для $n$ и затем "выводится" истинность для $n+1$. Или тут (в предположении индукции) в силу произвольности $n$ мы можем выбирать $n$ объектов разными способами столько раз, сколько это имеет смысл для решения?

[mihaild]

Skyfall в сообщении #1229986 писал(а):

Или тут (в предположении индукции) в силу произвольности $n$ мы можем выбирать $n$ объектов разными способами столько раз, сколько это имеет смысл для решения?

Примерно так. Мы формулируем некоторое утверждение с одним свободным параметром $n$, например "через любое множество не более чем из $n$ точек можно провести прямую". Дальше мы доказываем это утверждение при $n = 1$, и, пользуясь предположением, что оно верно при $n = k$ (или при всех $n \leqslant k$), доказываем, что оно верно для $n = k+1$.

Вообще, термин "использовать предположение несколько раз" не имеет какого-то формального смысла.

[Sinoid]

mihaild в сообщении #1229991 писал(а):

Дальше мы доказываем это утверждение при $n = 1$, и, пользуясь предположением, что оно верно при $n = k$ (или при всех $n \leqslant k$), доказываем, что оно верно для $n = k+1$.

Если я не ошибаюсь, это называется методом возвратной математической индукции.

[svv]

Цитата:

ЛЕММА 1. Все лошади имеют одинаковую масть (докажем по индукции).
Доказательство. Очевидно, что одна лошадь имеет одинаковую масть. Обозначим через $P(k)$ предположение, что $k$ лошадей имеют одинаковую масть, и покажем, что из такого предположения вытекает, что $k+1$ лошадей имеют ту же масть. Возьмем множество, состоящее из $k+1$ лошадей, и удалим из него одну лошадь, тогда оставшиеся $k$ лошадей по предположению имеют одинаковую масть. Вернем удаленную лошадь в множество, а вместо нее удалим другую. Получится снова табун из $k$ лошадей. Согласно предположению, все они одной масти. Так мы переберем все $k+1$ множеств, в каждом по $k$ лошадей. Отсюда следует, что все лошади одной масти, т. е. предположение, что $P(k)$, влечет за собой $P(k+1)$. Но ранее мы уже показали, что предположение $P(1)$ выполняется всегда, значит, $P$ справедливо для любого $k$ и все лошади имеют одинаковую масть.

(Из книжки «Физики продолжают шутить»)

Skyfall, как бы Вы сформулировали, в чём здесь ошибка? Внимательным быть, конечно, нужно, но что всё-таки неправильного в этом рассуждении?

[miflin]

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

Skyfall, как бы Вы сформулировали, в чём здесь ошибка?

Вопрос задан не мне, и я прошу прощения. Но времени, вроде бы, прошло достаточно...

Когда-то это "доказательство" обсуждалось, и меня не убедили в том, что я неправ в своем мнении относительно ошибки.
Попробую ещё раз. Ошибка, на мой взгляд, заключается в применении выражения "одинаковой масти" к единичному объекту,
т.к. понятие "одинаковый" подразумевает сравнение, т.е. объектов должно быть, как минимум, два,
и утверждение "Очевидно, что одна лошадь имеет одинаковую масть" бессмысленно.

Далее, в конце "доказательства", встречается вариация понятия "одинаковый": "Отсюда следует, что все лошади одной масти".
Тогда можно бы начать "доказательство" с фразы "Очевидно, что одна лошадь одной масти", но это как бы уже и не смешно...

[Sinoid]

miflin в сообщении #1230047 писал(а):

т.к. понятие "одинаковый" подразумевает сравнение, т.е. объектов должно быть, как минимум, два,

А разве отрезок не равен сам себе?

[mihaild]

miflin, давайте переформулируем утверждение: множество цветов любого непустого конечного множества лошадей одноэлементно.

[miflin]

Sinoid в сообщении #1230053 писал(а):

А разве отрезок не равен сам себе?

Какие содержательные следствия можно из этого получить?

mihaild в сообщении #1230055 писал(а):

miflin, давайте переформулируем утверждение:

Давайте. И что нам это даст?
Я всё-таки хотел, чтобы применялась та терминология, которая использована в "доказательстве".
Что неверно в моих рассуждениях?

[mihaild]

miflin в сообщении #1230062 писал(а):

Какие содержательные следствия можно из этого получить?

Ну извините, рефлексивность - важное свойство, много где используется (в частности, многие рассуждения имеют вид "возьмем $a$ и $b$ с какими-то свойствами и докажем, что $a = b$").

miflin в сообщении #1230062 писал(а):

Давайте. И что нам это даст?

Это даст нам больший формализм.

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

[svv]

miflin в сообщении #1230062 писал(а):

mihaild в сообщении #1230055 писал(а):

miflin, давайте переформулируем утверждение:

Давайте. И что нам это даст?

Ну, теперь Ваша претензия к доказательству уже не работает, а доказательство всё равно расцветает пышным цветом без принципиальных изменений.

[miflin]

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

Ну, теперь Ваша претензия к доказательству уже не работает, а доказательство всё равно расцветает пышным цветом без принципиальных изменений.

Не работает потому, что перейдем на формализованный язык и будет нестыковка в терминологии?
Или же в моей претензии есть изначальный дефект (в рамках терминологии, в которой изложено доказательство,
которое Вы процитировали из "Физики продолжают шутить")?

[amon]

miflin,
Как я понимаю, Вам пытаются объяснить, что операция "Вернем удаленную лошадь в множество, а вместо нее удалим другую" не всегда выполнима, и такой случай надо рассмотреть отдельно.

[svv]

miflin в сообщении #1230070 писал(а):

Не работает потому, что перейдем на формализованный язык и будет нестыковка в терминологии?
Или же в моей претензии есть изначальный дефект (в рамках терминологии, в которой изложено доказательство,
которое Вы процитировали из "Физики продолжают шутить")?

Скорее, потому, что она несущественна. То есть — она законна, но доказательство легко скорректировать так, что к его новой форме она уже относиться не будет. Предлагается вместо «такие-то лошади имеют одинаковую масть» (что по отношению к одной лошади действительно звучит коряво) говорить «множество мастей такого-то множества лошадей состоит из одного элемента».

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