Откуда мы знаем, что такое точка? | страница 21

Поскольку для одного-единственного свойства (a) возможных классов было 2, мы, очевидно, получили наглядное геометрическое доказательство сформулированной выше теоремы.

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

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

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

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

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

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

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

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

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

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

и bPa.

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

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

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

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