лошадиное доказательство

[rwwd]

Лошадиное доказательство


Теорема: Все лошади одного цвета.

Доказательство. Докажем утверждение теоремы по индукции.

При n = 1, то есть для множества, состоящего из одной лошади, утверждение, очевидно, выполнено.

Пусть утверждение теоремы верно при n = k. Докажем, что оно верно и при n = k + 1. Для этого рассмотрим произвольное множество из k + 1 лошадей. Если убрать из него одну лошадь, то их останется k. По предположению индукции все они одного цвета. Теперь вернем на место убранную лошадь и заберем какую-либо другую. Опять-таки по предположению индукции и эти k оставшихся лошадей одного цвета. Но тогда и все k + 1 лошадей будут одного цвета.

Отсюда, согласно принципу математической индукции, все лошади одного цвета. Теорема доказана.

Как доказать что теорема не верна ?

[EtCetera]

Переход от $n=k$ к $n=k+1$ неверен при $k=1$.

[miflin]

n=1 не удовлетворяет условию, т.к. теорема подразумевает множественное число.
И дело не в том, что употреблено "все лошади" ("все лошади четвероногие" - проходит),
а главное - "одного", что подразумевает сравнение, т.е. требует, как минимум, две лошади.

[bot]

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

n=1 не удовлетворяет условию

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

Теорема имеет усиление. Все лошади белого цвета.

[miflin]

bot в сообщении #764706 писал(а):

Прав EtCetera - это единственное ключевое место: если бы здесь прошло, то дальше проблем бы не было.

Понятно, что ключевое.
Если бы прошло... Понятно, что проблем бы не было. Осталось только пояснить, почему всё-таки не проходит.

[gris]

А мне кажется, что дело в переходе от 1 к 2, как сказал EtCetera.
То, что лошадь одного цвета с собой, это всего лишь рефлексивность отношения эквивалентности. Ничего страшного тут нет. Но в переходе мы используем транзитивность, выделяя из множества из $n+1$ элемента меньшие, но обязательно пересекающиеся непустые подмножества. А с множеством из двух элементов такого сделать нельзя.

[miflin]

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

[nnosipov]

rwwd в сообщении #764683 писал(а):

Теорема: Все лошади одного цвета.
....
Как доказать что теорема не верна ?

Странный вопрос. Сходить на конюшню да посмотреть.

bot в сообщении #764706 писал(а):

Теорема имеет усиление. Все лошади белого цвета.

Я обычно доказываю студентам столь же сильную теорему: все студенты одного роста.

[Утундрий]

По-моему всё дело здесь в нарушении арности.

[Dan B-Yallay]

bot в сообщении #764706 писал(а):

Покажите множество, состоящее из одной лошади, в котором есть лошади разных цветов.

третья слева

[provincialka]

(Оффтоп)

bot в сообщении #764706 писал(а):

Теорема имеет усиление. Все лошади белого цвета.

Есть еще следствие: "Александр Македонский не существовал". Потому что известно, что он ездил на чёрном коне, Буцефале.

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

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

[Joker_vD]

provincialka в сообщении #764756 писал(а):

А вот где примеры рефлексивных отношений?

"Похож лицом"

[nikvic]

(Оффтоп)

Joker_vD в сообщении #764769 писал(а):

"Похож лицом"

"""Тридцать три богатыря // Видом будто из тюря // ...
Ю. Пухначёв (?).

[provincialka]

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

(Оффтоп)

Мой сын как-то меня удивил. Еще в дошкольном возрасте. Он расхвастался: я всех сильнее! Потом задумался и говорит: "Нет, так говорить нельзя. Если я сильнее всех, значит, сильнее самого себя. А этого быть не может". Я просто поразилась: вот что значит сын математика!

[_Ivana]

Дилетантские имхи:
1) "все лошади четвероногие" также можно "доказать" по предложенной методике, но это ложное утверждение. Даже здесь на форуме обсуждался одноногий конь
2) проблема тут вовсе не в индукционном переходе при $n=1$, а в подмене утверждений: вместо "если имеем $k$ лошадей одного цвета, то добавив к ним одну лошадь, полученный набор также будет одного цвета" - какое должно проверяться при правильном применении метода индукции, применяется очевидно истинное, но другое утверждение: "если из $m$ лошадей любые $m-1$ одного цвета, то все они одного цвета".
3) очень заинтриговали красивые умные слова "рефлексивные отношения", "эквивалентность", "арность", "транзитивность" и т.п. Подскажите простую книжку (желательно в сети), где про это можно почитать на доступном языке?