?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

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

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

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

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

Tags:

Comments

( 56 comments — Leave a comment )
spamsink
Jul. 16th, 2010 01:31 am (UTC)
Под квантором несчитово переворачивать подвыражения без зависимых переменных.

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

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

Edited at 2010-07-16 01:54 am (UTC)
fregimus
Jul. 16th, 2010 06:00 am (UTC)
Можно переворачивать. «каждый человек, если идет дождь, берет зонтик» и «для каждого верно, что, если он не взял зонтик, значит, дождя нет». Что не так?

Результат тривиальный, это точно. Только парадоксальный немного.
(no subject) - spamsink - Jul. 16th, 2010 08:29 am (UTC) - Expand
Rainaldo Anonimato [isopenid.ru]
Jul. 16th, 2010 04:20 am (UTC)
Чего ж Вы комментов не скрыли?:)
fregimus
Jul. 16th, 2010 06:00 am (UTC)
А зачем?
(no subject) - Rainaldo Anonimato [isopenid.ru] - Jul. 16th, 2010 11:56 am (UTC) - Expand
(no subject) - fregimus - Jul. 16th, 2010 08:55 pm (UTC) - Expand
(no subject) - Rainaldo Anonimato [isopenid.ru] - Jul. 16th, 2010 09:19 pm (UTC) - Expand
(no subject) - fregimus - Jul. 16th, 2010 09:56 pm (UTC) - Expand
(no subject) - Rainaldo Anonimato [isopenid.ru] - Jul. 16th, 2010 10:34 pm (UTC) - Expand
yurvor
Jul. 16th, 2010 04:40 am (UTC)
Детское, это мы в школе обсуждали :) Только мы доказывали, что все лошади белые :)

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

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

Edited at 2010-07-16 04:49 am (UTC)
fregimus
Jul. 16th, 2010 06:00 am (UTC)
Внимательнее читай. Это не доказательство, что все люди рыжие.
(no subject) - slavin_e - Jul. 16th, 2010 07:45 am (UTC) - Expand
(no subject) - fregimus - Jul. 16th, 2010 07:49 am (UTC) - Expand
(no subject) - yurvor - Jul. 16th, 2010 11:25 am (UTC) - Expand
(no subject) - fregimus - Jul. 16th, 2010 11:33 am (UTC) - Expand
(no subject) - yurvor - Jul. 16th, 2010 11:39 am (UTC) - Expand
(no subject) - yurvor - Jul. 16th, 2010 11:39 am (UTC) - Expand
(no subject) - (Anonymous) - Jul. 16th, 2010 12:03 pm (UTC) - Expand
(no subject) - yurvor - Jul. 16th, 2010 12:12 pm (UTC) - Expand
(no subject) - fregimus - Jul. 16th, 2010 08:51 pm (UTC) - Expand
(no subject) - yurvor - Jul. 16th, 2010 09:16 pm (UTC) - Expand
zlyuk
Jul. 16th, 2010 05:55 am (UTC)
а в чём парадокс-то? (в данной формулировке) теорема верна.
кстати, случай когда все рыжие не требует даже индукции, потому что вывод импликации верен.
fregimus
Jul. 16th, 2010 06:03 am (UTC)
Парадокс в том, что рыжесть заразна. Как только один рыжий, так и все сразу рыжие. Но — тсс, ни слова боле. Я вижу, что Вы парадокс уже разбили!
(no subject) - Rainaldo Anonimato [isopenid.ru] - Jul. 16th, 2010 12:00 pm (UTC) - Expand
falcao
Jul. 16th, 2010 06:32 am (UTC)
по оформлению
У меня есть два замечания "оформительского" характера. Прежде всего, для "лёгкого" случая -- когда все в компании рыжие, индукция выглядит "излишеством". Там ведь уже дано заключение, то есть доказывать нечего. Просто берём любого рыжего, а потом смотрим, что все действительно рыжие! Это верно и для компаний с бесконечным числом "учаснегов". К тому же наличие индукции мешает воспринять парадокс тем, кто либо не знает, что это такое, либо забыл :)

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

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

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

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

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

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

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

которое отличается расстановкой скобок. Но это совсем другое утверждение, и оно уже не будет логической тавтологией (то есть тождественно истинным).
fregimus
Jul. 16th, 2010 07:44 am (UTC)
Re: по оформлению
Спасибо, контрапозицию поправил. Я и словов-то таких не знаю.

Индукция, конечно, не требуется. Но она очень хорошо запутывает обычную интуицию, поэтому я ее и привел!
бабка и дедка - falcao - Jul. 16th, 2010 07:56 am (UTC) - Expand
Re: бабка и дедка - fregimus - Jul. 16th, 2010 08:01 am (UTC) - Expand
круг читателей - falcao - Jul. 16th, 2010 08:19 am (UTC) - Expand
(no subject) - fregimus - Jul. 16th, 2010 09:32 am (UTC) - Expand
Re: бабка и дедка - zlyuk - Jul. 16th, 2010 09:17 am (UTC) - Expand
Re: бабка и дедка - fregimus - Jul. 16th, 2010 09:31 am (UTC) - Expand
plakhov
Jul. 16th, 2010 07:18 am (UTC)
Какие-то очень сложные тут комментарии. Я детский оставлю.

Теорема верна, но это не один и тот же человек.
fregimus
Jul. 16th, 2010 07:47 am (UTC)
Конечно. Или один, но все время перекрашивается!
naverno
Jul. 16th, 2010 07:47 am (UTC)
Чудно. Повесил на Ленту в Аутсайд. Пущай народ не расслабляется, хоть и пятница)
fregimus
Jul. 16th, 2010 07:48 am (UTC)
Нет, расслабляться нельзя, а уж по пятницам — особенно!
zwilling
Jul. 16th, 2010 08:00 am (UTC)
А что такого? Импликация "если Вася рыжий, то все в компании рыжие" верна для всех случаев, кроме рыжего Васи в смешанной компании. Следовательно, она верна в рыжей компании для рыжего Васи, а в смешанной - для нерыжего.
fregimus
Jul. 16th, 2010 08:17 am (UTC)
Дайте угадаю: Вы — математик!
(no subject) - zwilling - Jul. 16th, 2010 08:28 am (UTC) - Expand
(Anonymous)
Jul. 16th, 2010 08:11 am (UTC)
ой беда беда
Послущайте, ну а если я просто дома зонтик забыл? А дождь то идет! :((((((((((
fregimus
Jul. 16th, 2010 08:16 am (UTC)
Не огорчайтесь, я могу дать Вам запасной. Вот:

(Deleted comment)
(no subject) - fregimus - Jul. 16th, 2010 09:21 am (UTC) - Expand
(Deleted comment)
(no subject) - fregimus - Jul. 16th, 2010 11:00 am (UTC) - Expand
autoench
Jul. 16th, 2010 10:35 am (UTC)
Дык вроде верно, человек-то этот рыжим быть вовсе не обязан.
И даже случай с лысыми вписывается)
fregimus
Jul. 16th, 2010 11:01 am (UTC)
Нет, человек рыжим быть не обязан! Кажется, даже во Всеобщей декларации прав человека так написано!
cmike
Jul. 16th, 2010 10:48 am (UTC)
Поэтому можно взять такого человека из компании рыжих и переместить их в другую компанию и она порыжеет? Очевидно, что это невозможно — следовательно, такого человека нельзя переместить в компанию, в которой не все рыжие?
fregimus
Jul. 16th, 2010 11:03 am (UTC)
Не перекрасив — нельзя, это точно!
(Anonymous)
Jul. 16th, 2010 02:04 pm (UTC)
Stupid braine
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
fregimus
Jul. 16th, 2010 09:00 pm (UTC)
Re: Stupid braine
one not the idiot has suggested
to talk about red
and others not the red
discuss its offer with persistence red


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

Edited at 2010-07-16 09:04 pm (UTC)
Re: Stupid braine - (Anonymous) - Jul. 19th, 2010 08:33 am (UTC) - Expand
Rainaldo Anonimato [isopenid.ru]
Jul. 16th, 2010 11:29 pm (UTC)
Хотя действительно... Парадокс и некоторая "ошибка" на грани "математической" логики и "бытовой" - возможны...
"Математическая" логика всё-таки неявно предполагает "детерминированный" мир, все свойства и измерения в котором как бы уже проделаны (существуют) и - главное - не влияют одни на другие.
"Бытовой" язык, как обычно, более гибок и неоднозначен.
Слово "рыжий" - ведь не обязано означать постоянного свойства. Ничто не запрещает считать, что всякий может стать или перестать быть рыжим по собственной (или чужой) воле в любой произвольный момент.
Слова "если... то..." - могут означать не только логическую, но и казуальную либо просто временнУю связь-последовательность... Но это (хотя по сути более интересно) можно сейчас даже оставить без внимания.

Итак: сделаем лишь один "человеческий" шаг на "поле логики" и ничего не станем менять в исходных формулировках условий, но только рассмотрим случай, о котором никто даже не подумал, хотя он полностью в пределах этого языка:
мы берём такую из "любых компаний", в которой каждый из её членов с присущей только ему периодичностью - перекрашивается, становясь то рыжим, то нет, то снова рыжим - и так непрерывно.
Что тогда станет означать исходное утверждение, выраженное теми же самыми словами (но не теми же смыслами)? Для сторонников "суженных" логических "формул" со значками кванторов и предикатов - я скажу, что на эту трактовку меня "подбодрил" Фрегимус в треде выше, сообщив мне, что "математика — это как раз простыми словами, а кванторы — так, сокращ. и т. п. для удоб."
Так вот: "простыми словами" то же утверждение, но для "динамически рыжей", а не взятой в статике - ситуации - будет означать, что в рассматриваемой компании всегда можно найти такого человека, что если он сейчас не рыжий (переасился в другой цвет), то всё понятно: и компания не будет поголовно рыжей, но если он же (тот же самый человек!) станет не рыжим (покрасится), то и вся остальная компания дружно должна сделать то же самое в тот же миг!:)
Кстати, ещё интереснее: в другом языке (в том же итальянском) такую "перекодировку" высказываний совершить на самом деле сложнее, чем в русском.
В итальянском - почти с десяток разных форм (и сочетаний этих форм) наклонений, простых и сложных времён и спряжений глаголов - отвечают за эти оттенки смыслов и градаций: факт - условие - следствие - предположение - фантазия - невозможность... Перепутать эти оттенки сложно. В русском же - и условное, и сослагательное, и изъявительное наклонение (почему-то ещё и в прошедшем времени, от которого в русском - и глаголов-то не осталось, какие-то "бывшие краткие причастия":)) в одном смысловом тумане.
Вот и бабка с дедкой - приуныли, плачут: были ли у бабки яйца, могут ли быть, будут ли? Вот и дедка не знает...
Rainaldo Anonimato [isopenid.ru]
Jul. 16th, 2010 11:37 pm (UTC)
исправлял - недоглядел
Следует читать:
...всегда можно найти такого человека, что если он сейчас не рыжий (перекрасился в другой цвет), то всё понятно: и компания не будет поголовно рыжей, но если он же (тот же самый человек!) станет рыжим (покрасится), то и вся остальная компания дружно должна сделать то же самое (порыжеть) в тот же миг!:)

Если возьмёт зонтик - дождь будет, если не возьмёт - дождя не будет...
Rainaldo Anonimato [isopenid.ru]
Jul. 17th, 2010 12:13 am (UTC)
Конечно. легко просчитать банальное возражение, что всё якобы можно свести к тому же примитивному статическому утверждению, которое по сути можно переформулировать так: "в любой момент времени в компании либо найдётся хоть один не рыжий, либо все в ней будут рыжими". Мол, тавтология.

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

...И отсюда бравурным маршем: вот потому-то компьютер, пока он думает на языке математики, не станет человеком! :)))
(Anonymous)
Jul. 19th, 2010 08:34 am (UTC)
Stupid Braine
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
( 56 comments — Leave a comment )