Парадокс заразного рыжего, или В любой компании найдется такой…

[fregimus]

Этот парадокс приписывают Р. Смаллиану.

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

Доказательство. В компании либо все рыжие, либо не все рыжие. Рассмотрим компанию из одних рыжих, и докажем индукцией, что для такой компании это верно. Для компании из одного это верно: если один рыжий, то и все в компании (из одного) рыжие. Теперь возьмем компанию из нескольких рыжих, и предположим, что в ней такой человек есть. Теперь добавим к ней еще одного рыжего. Этот предполагаемый человек, само собой, остался рыжим, и все в компании тоже по-прежнему рыжие. Таким образом, мы заключаем, что в компании из одних рыжих такой человек найдется.

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

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

Ваш ход. Кто догадался, говорите, только тихо, а кто гуголит, того Баба Яга съест.

_____________________________
1. «если А, то Б» можно эквивалентно записать в виде «если не Б, то не А». Например, утверждения «если идет дождь, я беру зонтик» и «если я не взял зонтик, значит, дождя нет» эквивалентны.

Comments

[spamsink]

Под квантором несчитово переворачивать подвыражения без зависимых переменных.

Детально, "В любой компании найдется такой человек, что, если не все в компании рыжие, то и он не рыжий." ==
∀ company ∃ person : ~all_redhaired(company) => ~redhaired(person) ==
∀ company: ~all_redhaired(company) => ∃ person ~redhaired(person) ==
∀ company: ~∃ person ~redhaired(person) => all_redhaired(company)

Получаем тривиальный результат: Если в компании не найдется ни одного не рыжего, то вся компания состоит из рыжих. А нетривиального не получаем.

[rainaldo anonimato (from livejournal.com)]

Чего ж Вы комментов не скрыли?:)

[yurvor.livejournal.com]

Детское, это мы в школе обсуждали :) Только мы доказывали, что все лошади белые :)

P.S. Правда, мы доказывали по-другому, а у тебя вообще всё банально - "найдется такой человек, что, если он рыжий," не равносильно "найдется рыжий человек". Например, в любой компании, включающей меня, завсегда найдусь я, такой, что если я рыжий, то и все в ней рыжие :))

P.P.S. А комменты действительно закрой :)

[zlyuk.livejournal.com]

а в чём парадокс-то? (в данной формулировке) теорема верна.
кстати, случай когда все рыжие не требует даже индукции, потому что вывод импликации верен.

[fregimus.livejournal.com]

Можно переворачивать. «каждый человек, если идет дождь, берет зонтик» и «для каждого верно, что, если он не взял зонтик, значит, дождя нет». Что не так?

Результат тривиальный, это точно. Только парадоксальный немного.

[fregimus.livejournal.com]

А зачем?

[fregimus.livejournal.com]

Внимательнее читай. Это не доказательство, что все люди рыжие.

[fregimus.livejournal.com]

Парадокс в том, что рыжесть заразна. Как только один рыжий, так и все сразу рыжие. Но — тсс, ни слова боле. Я вижу, что Вы парадокс уже разбили!

по оформлению

[falcao.livejournal.com]

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

Второе замечание: тот логический закон, на который Вы ссылаетесь -- это "закон контрапозиции". Называть его "законом отрицания импликации" вряд ли стоит, так как тут импликация не отрицается, а переписывается в логически эквивалентной форме.

Сама по себе теорема вообще-то верна: мы в любой компании можем указать требуемого человека. Если там все рыжие, указываем любого. И далее возникает имликация вида true -> true. Если не все рыжие, то указываем не рыжего, и тогда импликация имеет вид false -> false. То есть она в обоих случаях истинна.

Парадокс возникает за счёт того, что это верное утверждение можно спутать с другим, которое уже неверно. А именно: для любой компании, если в ней найдётся один рыжий, то тогда в ней все рыжие.

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

(Ex)(R(x) -> (Ay)R(y))

В другом же случае имеется в виду утверждение

(Ex)R(x) -> (Ay)R(y)

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

[plakhov.livejournal.com]

Какие-то очень сложные тут комментарии. Я детский оставлю.

Теорема верна, но это не один и тот же человек.

Re: по оформлению

[fregimus.livejournal.com]

Спасибо, контрапозицию поправил. Я и словов-то таких не знаю.

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

[slavin-e.livejournal.com]

yurvor, судя по всему, имел в виду, что слова "найдется такой человек, что, если он рыжий" не равносильны словам "найдется рыжий человек" в качестве составной части формулировки теоремы, а не в качестве полного утверждения. По крайней мере, я с первого раза прочитал его коммент именно так, и благодаря этому понял суть "парадокса".

[naverno.livejournal.com]

Чудно. Повесил на Ленту в Аутсайд. Пущай народ не расслабляется, хоть и пятница)

[fregimus.livejournal.com]

Конечно. Или один, но все время перекрашивается!

[fregimus.livejournal.com]

Нет, расслабляться нельзя, а уж по пятницам — особенно!

[fregimus.livejournal.com]

Да, я старался, запутывал!

бабка и дедка

[falcao.livejournal.com]

"Закон контрапозиции" (или просто "контрапозиция") -- это общепринятый термин. Я не видел, чтобы его называли как-либо по-другому.

Мне не очень понятно намерение "запутать". Что было бы плохого, если бы Вы сказали, что вот возьмём произвольного человека, а потом посмотрим на всех, и увидим, что все рыжие?

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

Мне кажется, это вполне согласуется даже с обычным фольклором -- типа того, что если бы у бабки были некоторые предметы мужского экстерьера, то она была бы "дедкой"! :)

[zwilling.livejournal.com]

А что такого? Импликация "если Вася рыжий, то все в компании рыжие" верна для всех случаев, кроме рыжего Васи в смешанной компании. Следовательно, она верна в рыжей компании для рыжего Васи, а в смешанной - для нерыжего.

Re: бабка и дедка

[fregimus.livejournal.com]

Дык у математиков другая интуиция, накачанная, как Шварценеггер!

Я слышал «если бы у бабки были колеса, она была бы автобусом» — как Вам?

ой беда беда

[(Anonymous)]

Послущайте, ну а если я просто дома зонтик забыл? А дождь то идет! :((((((((((

[fregimus.livejournal.com]

Не огорчайтесь, я могу дать Вам запасной. Вот:

[fregimus.livejournal.com]

Дайте угадаю: Вы — математик!

круг читателей

[falcao.livejournal.com]

Я в любом случае хотел бы понять Ваш замысел -- в том, что касалось индукции. Вы пишете для какого-то круга читателей. Математику (например, мне) здесь индукция представляется явно излишней. Условный "гуманитарий", способный понимать логику и парадоксы, может просто не владеть самим методом. Для кого тогда этот приём?

Про "автобус" я никогда не встречал такой фразы!

[zwilling.livejournal.com]

Ах, если бы! Будь я математиком, не искал бы сначала минут десять ошибку в доказательстве.

[spamsink]

Все так, потому что "идет дождь" прекрасно выносится за квантор и никому не мешает. А когда есть и существование, и общность, так не выйдет. falcao правильнее объяснил, да и если бы я скобки расставил, то виднее вышло бы.