Jornal do Falcão

Купил я себе сегодня новую клавиатуру (всего за 200 рублей :)) Старая была вполне работоспособна, но на ней стёрлись многие буквы, и меня это постоянно раздражало. Так что теперь я могу печатать быстрее, чем раньше. И под это дело у меня возникла мысль, а не написать ли новый пост? Тем более, что тема "подвернулась" сама собой: сегодня я вспомнил об одной старой задаче, которая предлагалась в самом первом выпуске журнала "Квант". Было это в далёком 1970 году. Задача достаточно непростая, и её решение, приведённое несколькими номерами позже, было длинным и сложным. Но сама постановка задачи весьма проста, и смысл должен быть понятен каждому. Прежде всего, вот ссылка на тот номер журнала, в котором приведено решение. Речь идёт о задаче М5. Там, среди прочего, даются и "занимательные" переформулировки, но я не буду из них исходить, и вообще по этой ссылке ходить не обязательно. Сейчас всё будет изложено "с нуля".

Журнал у меня с некоторого времени почти весь "под замком", но посты на математическую тему я обычно делаю открытыми для всех. Итак, приступим. Этот пост можно ещё "приурочить" к началу учебного года, хотя у меня пока продолжается отпуск :)

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

(А1) Через любые две различные точки проходит одна и только одна прямая.

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

(А2) Существуют по крайней мере три точки, не лежащие на одной прямой.

Смысл у этой аксиомы очень простой: не все точки лежат на одной и той же прямой. Этим постулируется, что мы имеем дело не с одной прямой, а с чем-то вроде плоскости. В курсе планиметрии именно эти аксиомы излагаются в самом начале.

Возникает вопрос: что эти две простые аксиомы могут описывать? Здесь надо абстрагироваться от обычной геометрии и представить себе следующее. "Точками" разрешается называть любые объекты. Например, роль "точек" могут играть люди, составляющие некоторую компанию. А "прямыми" будут называться те или иные совокупности точек. Например, в случае людей это могут быть какие-нибудь комиссии, создаваемые из отдельных участников.

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

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

То, что у нас получилось, будет называться "мини-плоскостью", если при этом выполняются условия А1 и А2. Второе условие и его проверка совсем очевидны: не должно быть линии, проходящей через все наши точки. Что касается А1, то выполнение этого условия означает, что для любых двух (различных) участников у нас есть ровно одна линия, на которой оба они находятся.

Приведём простейший пример "мини-плоскости", например, из 10 точек. Расположим 9 точек вдоль одной прямой, а десятую точку поместим вне этой прямой и соединим линиями с каждой из девяти точек. Получится схема, в которой точек 10, и линий нарисовано тоже 10.

Можно привести примеры, когда линий будет больше, чем точек. В частности, аксиомы А1 и А2 не запрещают проводить линию всего лишь через одну точку. Это ничему не помогает и не мешает -- просто увеличивает число линий. Если такие линии есть, то их можно просто стереть, сравнивая далее количество линий и количество точек. Так вот, оказывается, что на "мини-плоскости" линий всегда имеется столько же, сколько точек, или больше. Это и есть то утверждение, о котором далее пойдёт речь, и это точная переформулировка задачи из "Кванта".

Далее я намерен изложить её решение в такой форме, чтобы оно содержало минимум формул и обозначений, и чтобы смысл был наиболее "прозрачен" для читателя. Я буду основываться на доказательстве, идею которого предложил известный американский математик Джон Конвей. Сам же доказываемый факт был впервые установлен в работе 1948 года, авторами которой были де Брёйн и Эрдёш.

( Collapse )

В конце хочу дать ссылку, не имеющую отношения к содержанию поста. На данный момент (07.09.13) в журнале моего френда, коллеги и тёзки fiviol проходит интересная игра. Я в ней уже завершил участие, но приглашаю всех тех, кто любит разгадывать анаграммы. Которые в исполнении автора бывают обычно интересными и остроумными. Кто любит такие задания, добро пожаловать сюда.

Итак, пора, наконец, подвести обещанные итоги вероятностного опроса, проводившегося здесь. Сам опрос уже закрыт; я считаю, что он удался. В нём приняло участие 140 человек, и из них 34 правильно ответили на все три вопроса, что составляет почти 25%. То есть отвечали люди явно не наобум: при случайном выборе шанс ответить верно составляет 1 из 27, то есть около 4%.

Вот "доска почёта" с имена "отличившихся":

whitefluffy, beldmit, nickitos, knop, gdt, mysha_17, engimono, eliratus, mikev, fakir57, kcmamu, gul_chataj, dr_math, eslitak, p_govorun, shurik_s, rus4, spartach, lithovore, irishoak, fiviol, timur0, lanino, diana_shipilova, o_jovem_louco, dmitri_ldin, riateche, eyeless_watcher, barkpeeler, georgeyak, [Bad username: Andrey Khalyavin], [Bad username: Roma Lee], oni_yokai, mathclimber.

Итоги я старался подводить внимательно, но если вдруг кого забыл, то прошу сообщить.

Сообщаю верные ответы, их номера таковы:

для 18 карточек:
2. Более вероятен случай, что сумма чисел на карточках окажется нечётной -- его дали 52 участника;

для 19 карточек:
3. Вероятности чётной и нечётной суммы чисел на карточках одинаковы -- 114 участников;

для 20 карточек:
1. Более вероятен случай, что сумма чисел на карточках окажется чётной -- 60 участников.

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

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

Мне самому эта вероятностная задача встретилась на одном из математических форумов. Я сначала решил её при помощи производящих функций, то есть с использованием "техники". Вскоре после этого я придумал решение, не основанное на каких-либо вычислениях, а опирающееся только на соображения симметрии. Его я далее и излагаю под "катом". Считаю, что это рассуждение должно быть доступно всем без исключения, то есть никаких специальных знаний для его понимания не требуется. Замечу на всякий случай, что возможны и другие подходы -- я излагаю всего лишь один из множества возможных.

( Collapse )

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

Начну я с того, что сообщу ответы, коротко напомнив то, о чём спрашивалось.

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

ОТВЕТ: 14.

2. Здесь вопрос был похожий, но спрашивалось, сколько бросаний нужно до выпадения двух "орлов" и следующей за ними "решки". Может показаться, что ответ такой же, однако это не так.

ОТВЕТ: 8.

3. Задано было два вопроса о том, как долго надо собирать (опять-таки, "в среднем") полный комплект этикеток, карт и т.п. Сформулирую условие в общем виде. Есть n видов, например, игральных карт. Мы приобретаем какой-то товар, в который вложена одна из этих карт, причём вероятность встретить данную карту считается равной 1/n, то есть всё "по-честному". Спрашивается тогда, как долго надо "в среднем" собирать полный комплект.

Общий ОТВЕТ даётся такой арифметической формулой: n(1+1/2+1/3+...+1/n). Соответственно, при n=6 имеем

а) около 15 (точное значение 14,7),

а при n=36, то есть для колоды карт получается

б) около 150.

Для тех, кого интересуют объяснения, они приводятся под "катом".

( Collapse )

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

Итак, в чём состоит этот парадокс? Предположим, что некто произнёс фразу "я лгу", имея в виду, что он лжёт в момент произнесения этих слов. Лжёт он, или говорит правду? Нетрудно убедиться в том, что оба варианта приводят к противоречию.

В самом деле, если человек солгал, то сообщённая им информация ложна. А сказал он нам, что лжёт. Тем самым, это должно быть неправдой, но тогда это означает, что человек не солгал, а сказал правду. Но это противоречит нашему изначальному предположению, что он соглгал.

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

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

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

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

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

( Collapse )

Это третья, завершающая часть поста. Комментарии отменены; обсуждение всех трёх частей проводится здесь.

Часть первая
Часть вторая

( Collapse )

ПРОДОЛЖЕНИЕ поста, начатого здесь. Обсуждение проводится по прежнему "адресу".

В данной части поста, я считаю наиболее важными и принципиальными пункты 10 -- 11, где описывается процесс построения модели. Полезно также перечитать пункт 7 -- для тех, кто не знаком с правилами логического рассуждения, которые мы здесь выделяем в качестве основных. В пунктах 8 -- 9 у меня собраны в основном иллюстративные примеры, а в заключительном пункте 12, который мне пришлось разместить в третьей части, идёт серия формальных проверок того, что перед этим было построено. Я вообще-то планировал уложиться в две части, но пришлось сделать три из-за ограничений на длину записей, которая существует в ЖЖ. Так или иначе, я считаю, что на пункт 10 следует обратить особое внимание всем тем, кто в первую очередь интересуется вопросом "из чего же, из чего же, из чего же сделаны наши модели?" :)

7. Прежде всего, я хочу напомнить те основные правила логического рассуждения, которые я выделял в качестве "базовых" в серии предыдущих постов на эту тему. Для того, чтобы сократить число этих правил, мы прежде всего хотим сократить число используемых нами логических связок до отрицания и импликации. Этим мы ничего не теряем, так как все остальные связки через них выражаются. Так, (p or q) есть не что иное как (not(p) -> q), а под (p and q) теперь можно понимать not(not(p) or not(q)). Конечно, сами формулы становятся более громоздкими, если отказаться от связок "или", "и", но нам никто не запрещает их использовать в качестве сокращённых обозначений, что мы далее и будем делать. Но при этом получается, что для исчисления высказываний нам достаточно всего трёх правил логического рассуждения. Напомним их здесь.

(1) Правило Отсечения, или "модус поненс": если доказано A, а также доказано A->B, то разрешается считать доказанным B.

(2) Правило Условного Рассуждения: для доказательства утверждения вида A->B, разрешается принять A в качестве дополнительного предположения (условия), и доказать B при этом условии.

(3) Правило Рассуждения От Противного: для доказательства утверждения B достаточно привести к противоречию утверждение not(B), то есть вывести из него как некоторое утверждение A, так и его отрицание not(A).

Помимо этих правил, мы часто применяем и другие -- например "правило разбора случаев". Но все эти правила можно вывести из правил (1), (2), (3), и в таком качестве далее их использовать. Особенность выписанных правил в том, что они позволяют доказать любой "закон логики" на уровне исчисления высказываний. (То есть без использования логических кванторов.) Под "законом логики" здесь понимается такая формула, которая истинна всегда, независимо от истинностных значений входящих в неё высказывательных переменных.

Однако исчисление высказываний представляет собой довольно узкий фрагмент логики, и для получения "полноценной" картины (способной вобрать в себя "всю математику"), нужно привлекать исчисление предикатов, "устройство" которого я коротко напомнил в предыдущем посте. Для формулировки недостающих правил логического рассуждения (а их будет ещё два), мы минимизируем число используемых нами логических кванторов, оставляя лишь квантор всеобщности. Дело в том, что квантор существования через него выражается следующим образом: если нам надо сказать, что существует некий объект x, удовлетворяющий какому-то условию Ф (оно обычно зависит от x, но мы это здесь не выделяем), то вместо этого можно сказать логически эквивалентную по смыслу вещь. А именно, если мы утверждаем, что Ф выполнено для некоторого x, то мы этим отрицаем? Если бы всё обстояло иначе, то Ф не выполнялось бы никогда. То есть при любом x имело бы место не-Ф. Осталось выписать отрицание этого факта. Таким образом, под (Ex)Ф мы в дальнейшем будем понимать не что иное как not((Ax)(not(Ф))) -- отрицание того, что всегда имеет место не-Ф.

Теперь осталось сформулировать ещё два правила, а также добавить одну небольшую оговорку.

(4) Правило Обобщения: если доказана формула вида Ф(x) для произвольного x, то разрешается считать доказанной формулу (Ax)Ф(x).

(5) Правило Перехода К Частному Случаю: Если доказана формула (Ax)Ф(x), то разрешается считать доказанной формулу Ф(t) для любого выражения t.

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

( Collapse )

Для обсуждения этого поста.

Этот пост я планировал написать чуть ли не с лета, но всё как-то откладывал и откладывал. Но вот в недавней френд-ленте мне встретилось упоминание о том же самом, и я в комментах пообещал, что напишу планируемый пост в самое ближайшее время. Как и предыдущие мои посты, затрагивающие логическую тематику (некоторые из записей перечислены здесь), он идёт как открытый. Комментарии отменены, а для обсуждения я завожу, как обычно, отдельный пост (тоже открытый).

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

Текст я разделяю на две части, а изложение разбито на отдельные пункты. В первой части, то есть в данном посте, информация даётся в основном "вводная", а собственно доказательство теоремы я изложу в одном из следующих постов. При "сокращённом" варианте чтения, можно пункты 2 и 4 лишь "пробежать глазами", так как они в большей степени посвящены обоснованию значимости обсуждаемого результата. А вот на пункты 1, 3 и особенно 5 следует обратить особое внимание, так как это важно для понимания доказательства.

1. Начать я хочу с того, что не следует путать теорему Гёделя о полноте, которой посвящён этот пост, со знаменитыми теоремами Гёделя о неполноте (о которых я когда-то уже писал, и которым не так давно посвятил серию постов fregimus). Тут речь идёт о "полноте" и "неполноте" совершенно разных вещей. "Неполнота" относится к свойствам формальных теорий, в которых оказывается принципиально невозможно доказать всё, что нам бы хотелось; в таком смысле этот результат можно назвать "пессимистическим". То же, о чём я хочу написать здесь, есть результат в каком-то смысле противоположного характера, и его можно причислить к "оптимистическим". Здесь слово "полнота" относится к системе правил логических рассуждений. Оказывается, что эти правила (которые я описывал в своих старых постах и которые ниже коротко напомню), оказываются достаточно "полными" для того, чтобы с их помощью можно было провести любое математическое рассуждение.

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

То есть, если совсем коротко: всякий непротиворечивый набор формальных положений что-нибудь да описывает.

( Collapse )

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

Основной текст идёт под "катом" -- я думаю, что математическая проблематика интересует далеко не всех. Эту запись нет смысла помещать в режиме "френдс-онли", поэтому я делаю её открытой. ( Collapse )

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

Следуя примеру некоторых ЖЖ-юзеров, я решил разместить список ссылок на ряд своих прежних постов -- по рубрикам. Все эти посты являются общедоступными. ( Collapse )