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

[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)

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

[fregimus.livejournal.com]

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

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

[rainaldo anonimato (from livejournal.com)]

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

[fregimus.livejournal.com]

А зачем?

[yurvor.livejournal.com]

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

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

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

[fregimus.livejournal.com]

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

[zlyuk.livejournal.com]

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

[fregimus.livejournal.com]

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

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

[falcao.livejournal.com]

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

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

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

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

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

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

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

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

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

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

[fregimus.livejournal.com]

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

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

[plakhov.livejournal.com]

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

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

[fregimus.livejournal.com]

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

[naverno.livejournal.com]

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

[fregimus.livejournal.com]

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

[zwilling.livejournal.com]

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

[fregimus.livejournal.com]

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

ой беда беда

[(Anonymous)]

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

[fregimus.livejournal.com]

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

[autoench.livejournal.com]

Дык вроде верно, человек-то этот рыжим быть вовсе не обязан.
И даже случай с лысыми вписывается)

[fregimus.livejournal.com]

Нет, человек рыжим быть не обязан! Кажется, даже во Всеобщей декларации прав человека так написано!

[cmike.livejournal.com]

Поэтому можно взять такого человека из компании рыжих и переместить их в другую компанию и она порыжеет? Очевидно, что это невозможно — следовательно, такого человека нельзя переместить в компанию, в которой не все рыжие?

[fregimus.livejournal.com]

Не перекрасив — нельзя, это точно!

Stupid braine

[(Anonymous)]

In the company where one not the idiot has suggested to talk about red and others not the red discuss its offer with persistence red - means that they not red but idiots

Re: Stupid braine

[fregimus.livejournal.com]

one not the idiot has suggested
to talk about red
and others not the red
discuss its offer with persistence red

да Вы просто стихами говорите!

[rainaldo anonimato (from livejournal.com)]

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

Итак: сделаем лишь один "человеческий" шаг на "поле логики" и ничего не станем менять в исходных формулировках условий, но только рассмотрим случай, о котором никто даже не подумал, хотя он полностью в пределах этого языка:
мы берём такую из "любых компаний", в которой каждый из её членов с присущей только ему периодичностью - перекрашивается, становясь то рыжим, то нет, то снова рыжим - и так непрерывно.
Что тогда станет означать исходное утверждение, выраженное теми же самыми словами (но не теми же смыслами)? Для сторонников "суженных" логических "формул" со значками кванторов и предикатов - я скажу, что на эту трактовку меня "подбодрил" Фрегимус в треде выше, сообщив мне, что "математика — это как раз простыми словами, а кванторы — так, сокращ. и т. п. для удоб."
Так вот: "простыми словами" то же утверждение, но для "динамически рыжей", а не взятой в статике - ситуации - будет означать, что в рассматриваемой компании всегда можно найти такого человека, что если он сейчас не рыжий (переасился в другой цвет), то всё понятно: и компания не будет поголовно рыжей, но если он же (тот же самый человек!) станет не рыжим (покрасится), то и вся остальная компания дружно должна сделать то же самое в тот же миг!:)
Кстати, ещё интереснее: в другом языке (в том же итальянском) такую "перекодировку" высказываний совершить на самом деле сложнее, чем в русском.
В итальянском - почти с десяток разных форм (и сочетаний этих форм) наклонений, простых и сложных времён и спряжений глаголов - отвечают за эти оттенки смыслов и градаций: факт - условие - следствие - предположение - фантазия - невозможность... Перепутать эти оттенки сложно. В русском же - и условное, и сослагательное, и изъявительное наклонение (почему-то ещё и в прошедшем времени, от которого в русском - и глаголов-то не осталось, какие-то "бывшие краткие причастия":)) в одном смысловом тумане.
Вот и бабка с дедкой - приуныли, плачут: были ли у бабки яйца, могут ли быть, будут ли? Вот и дедка не знает...

исправлял - недоглядел

[rainaldo anonimato (from livejournal.com)]

Следует читать:
...всегда можно найти такого человека, что если он сейчас не рыжий (перекрасился в другой цвет), то всё понятно: и компания не будет поголовно рыжей, но если он же (тот же самый человек!) станет рыжим (покрасится), то и вся остальная компания дружно должна сделать то же самое (порыжеть) в тот же миг!:)

Если возьмёт зонтик - дождь будет, если не возьмёт - дождя не будет...

[rainaldo anonimato (from livejournal.com)]

Конечно. легко просчитать банальное возражение, что всё якобы можно свести к тому же примитивному статическому утверждению, которое по сути можно переформулировать так: "в любой момент времени в компании либо найдётся хоть один не рыжий, либо все в ней будут рыжими". Мол, тавтология.

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

...И отсюда бравурным маршем: вот потому-то компьютер, пока он думает на языке математики, не станет человеком! :)))

Stupid Braine

[(Anonymous)]

I'll try to do but can't at all
Because my rhyme got fall
All red the carrots sits at holes
Beside big round bolls