Откуда мы знаем, что такое точка?

Вначале отметим в большом прямоугольнике, изображающем множество М, место для элементов со свойством (a) – для этого, очевидно, достаточно нарисовать один кружок. Тем самым элементы из М, в принципе, могут быть разбиты на два класса – на элементы со свойством (a) и на элементы без этого свойства (любой из этих классов может быть пуст). Далее, отметим на рисунке места, где в принципе могут располагаться элементы со свойством (b): для этого, очевидно, придется нарисовать два квадрата: один внутри кружка и еще один вне кружка. Теперь будем отмечать места для элементов со свойством (с): нам, очевидно, придется нарисовать четыре треугольника (см. рис. 15.1). Каждый раз, добавляя возможные места для элементов со следующим новым свойством, мы рисуем в точности столько новых символов, сколько было построено различных возможных классов на предыдущем шаге. Иными словами, на каждом новом шаге число различных возможных классов, отвечающих нашему разбиению, удваивается. Поскольку для одного-единственного свойства (a) возможных классов было 2, мы, очевидно, получили наглядное геометрическое доказательство сформулированной выше теоремы.

Рис. 15.1

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

Задача. На острове Буяне расположена пиратская база, где в круглых и прямоугольных башнях содержатся 113 пленников. Круглых башен 7, прямоугольных 10. Три круглые башни – внутри трех прямоугольных, четыре круглые башни – внутри четырех круглых. Семьдесят семь пленников содержатся в круглых башнях, восемьдесят восемь – в прямоугольных. Однажды все 113 пленников сбежали – им удалось перелезть через стены башен. Скольким пленникам пришлось перелезать через две стены?

16. ЗМЕЙ ГОРЫНЫЧ И ТРАНЗИТИВНОСТЬ

Пусть М – некоторое множество (для определенности – конечное). Отношением на множестве М называют закон, который сопоставляет некоторым элементам из М какие-нибудь (другие или те же самые) элементы этого множества.

Таким образом, отношение на множестве – это чрезвычайно общее понятие. Здесь мы напомним лишь некоторые свойства отношений, которые понадобятся для решения приводимой ниже задачи про Змея Горыныча.

Но прежде рассмотрим пример. Пусть М – это множество из 10 человек, а Р – отношение, заданное на М следующим образом:

P: «человек а – брат человека b».

Тот факт, что «человек а – брат человека b» мы будем коротко записывать в виде: aPb.

Изобразим теперь элементы нашего множества М в виде точек на плоскости, обозначив их соответственно a,b,c,d,…. При этом, если, например, имеет место соотношение aPb, из точки a проведем стрелку к точке b и с другими точками поступим аналогичным образом (см. рис. 16.1). Рисунок, который у нас получился, называется графом отношения P.

Упражнение. Как объяснить, что на рис. 16.1 некоторые стрелки заострены с двух сторон, а некоторые – только с одной?

Определение 1. С кажем, что отношение Р (заданное на некотором множестве М) асимметрично, если ни для какой пары элементов a,b из множества М не может одновременно быть aPb

и bPa.

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

Рис. 16.1

Определение 2. Скажем, что отношение Р, заданное на множестве М, транзитивно, если для любых трех элементов a,b,c

из М одновременная справедливость aPb и bPc влечет за собой справедливость аPc.

На графе транзитивного отношения, таким образом, одновременно с составным путем (вдоль стрелок), идущим из a в c через b, cуществует стрелка, непосредственно идущая из a в c.

Определение 3. Отношение Р, заданное на множестве М, называется связным, если для любых двух элементов a, b из М справедливо хотя бы одно из двух соотношений: aPb, bPa.

Определение 4. Отношение Р задает на множестве М линейный порядок, если оно асимметрично, транзитивно и связно.

Пример. Пусть множество М состоит из n человек. Очевидно, что линейно упорядочить множество М – это поставить людей, составляющих данное множество, в очередь друг за другом. Заметим, что в силу правила произведения из n людей можно образовать n! различных очередей.

Преподавая тему «Отношения на множестве», авторы столкнулись с некоторым дефицитом интересных, но несложных задач. Предлагаемая ниже задача представляет собой попытку компенсировать упомянутый дефицит.

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

а) Как это удалось сделать Змею Горынычу?