Базовые понятия и утверждения

1. Множества и операции над ними. Подмножеством понимают объединение в единое целое определенных вполне различаемых объектов. Объекты при этом называютэлементами образуемого ими множества.

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

Запись означает, чтоявляется элементом множества
; в противном случае пишут
.

Множество называют конечным , если оно содержит конечное число элементов, ибесконечным , если оно содержит бесконечное число элементов. Множество, не содержащее элементов, называютпустым и обозначают символом
.

Число элементов конечного множества
называют егомощностью и обозначают
.

Множество можно описать, указав свойство, присущее элементам только этого множества. Множество всех объектов, обладающих свойством
, обозначают
. Конечное множество можно задать путем перечисления его элементов, т.е.
.

Например, запись
означает, что множество
содержит два элемента - числа
и.

Если каждый элемент множества есть элемент множестваB , то говорят, чтоестьподмножество , и пишут:
.

Заметим, что пустое множество
считают подмножеством любого множества.

Если
и
, то говорят, что множестваиравны , и пишут:
.

Если
и
, тоназываютсобственным подмножеством и, чтобы подчеркнуть это, применяют запись
.

Множество всех подмножеств множества
называют егобулеаном и обозначают
.

Например, если
, то

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

1. Множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств и, называютобъединением A и B и обозначают
, т.е..

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

Если
, то множестваиназываютнепересекающимися .

3. Множество, состоящее из всех элементов множества , не принадлежащих множеству, называютразностью A и B и обозначают
, т.е.
.

4. Обычно в конкретных рассуждениях всякое множество рассматривают как подмножество некоторого достаточно широкого множества, которое называют универсальным . Множество элементов универсального множества, не принадлежащих множеству, называютдополнением и обозначают, т.е.
. Из определения следует, что
.

5. Множество, состоящее из упорядоченных пар
, в которых- элемент множества, а- элемент множества, называютд екартовым произведением множеств A и B и обозначают
, т.е..

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

Рис. 1.1.

В качестве примеранайдем объединение, пересечение, разность и декартово произведение множеств
и
.

Поскольку
,
, то
,
,
,.

Пусть задано универсальное множество . Тогда для любых множеств
выполняются следующиесвойства :

коммутативные законы :

1.
; 2.
;

ассоциативные законы :

дистрибутивные законы :

законы идемпотентности :

7.
; 8.
;

законы де Моргана :

9.
; 10.
;

законы нуля :

11.
; 12.
;

законы единицы :

13.
; 14.
;

законы поглощения :

15.
; 16.
;

законы дополнения :

17.
; 18.
;

закон двойного дополнения :

19.
.

О том, как доказываются эти равенства, можно узнать во второй части данного параграфа.

Операции объединения, пересечения и декартова произведения можно обобщить на случай произвольного конечного числа участников.

Объединением множеств
называют множество, любой элемент которого является элементом хотя бы одного из данных множеств. Обозначение:
или.

Пересечением множеств
называют множество, любой элемент которого является элементом каждого из данных множеств. Обозначение:
или .

Декартовым произведением множеств
называют множество

В частном случае одинаковых сомножителей декартово произведение
обозначают
.

Например, если
, то

Приведем без доказательств утверждения о числе элементов конечных множеств .

1. Если между конечными множествами исуществует взаимно-однозначное соответствие, то
.

2. Если

также конечно и

Например,если
, то множество
имеет мощность
.

3. Если
- конечные попарно-непересекающиеся множества, то множество
также конечно и

Это утверждение называют правилом суммы .

4. Если
- конечные множества, то множествотакже конечно и

Последнее равенство называется формулой включений и исключений . В частных случаях двух и трех множеств она принимает вид:

Заметим, что формула включений и исключений действует и в том случае, когда множества
попарно не пересекаются (в этом случае все слагаемые в правой части формулы, содержащие пересечения множеств, обнуляются и формула трансформируется в правило суммы).

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

Пример 1.В группе из 100 туристов 65 человек знают английский язык, 55 человек знают французский и 38 человек знают оба языка. Сколько туристов в группе знает хотя бы один из этих языков?

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

Упражнение 1.1.Из 100 студентов-лингвистов польский язык изучают 42, чешский - 25, венгерский - 36, польский и чешский - 15, польский и венгерский - 14, чешский и венгерский - 12, польский, чешский и венгерский - 5. Сколько студентов не изучают ни одного из перечисленных языков?

Совокупность непустых, попарно непересекающихся подмножеств
множестваназываютразбиением , если
.

Например, для множества
совокупность подмножеств
разбиением является, а совокупность подмножеств
не является.

Упражнение 1.2. Найти все разбиения множества
и множества
.

2. Бинарные отношения на множестве. Бинарные отношения -простой и вместе с тем очень важный объект дискретной математики.

Определение. Бинарным отношением на множестве
называется подмножество декартова произведения
.

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

Пусть - некоторое бинарное отношение на множестве
. Если
, то говорят, чтоисвязаны бинарным отношениеми пишут
.

Пример 2. Пусть
. Тогда

и следующие множества могут служить примерами бинарных отношений на множестве
:

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

Определенное на множестве
бинарное отношение:

рефлексивно, если для
выполняется
;

симметрично , если для
из
следует
;

антисимметрично , если для
из
и
следует
;

транзитивно, если для
из
и
следует
.

Определение. Если бинарное отношение рефлексивно, симметрично и транзитивно одновременно, то оно называется отношением эквивалентности.

Например, бинарное отношениеиз примера 2 рефлексивно, антисимметрично и транзитивно,- антисимметрично и транзитивно,- рефлексивно, симметрично, антисимметрично и транзитивно,- рефлексивно, симметрично и транзитивно. Следовательно, бинарные отношенияиявляются отношениями эквивалентности, аи- нет.

Определение. Пусть- отношение эквивалентности на множестве
и- элемент
. Классом эквивалентности элементапо бинарному отношениюназывают множество
.

Например, множества
,
,

по отношению, а
,
,
- классы эквивалентности элементов
по.

Упражнение 1.3.На множестве
определены бинарные отношения
и
. Задать эти бинарные отношения перечислением элементов, указать свойства этих бинарных отношений, определить, являются ли они отношениями эквивалентности (если являются, то найти классы эквивалентности их элементов).

Перечислим свойства классов эквивалентности , присущие любому отношению эквивалентности, определенному на произвольном множестве
.

1. Класс эквивалентности любого элемента множества
- непустое множество.

2. Классы эквивалентности любых двух элементов множества
либо не пересекаются, либо совпадают.

3. Объединение классов эквивалентности всех элементов множества
совпадает с самим множеством
.

Доказательство этих свойств приведено во второй части параграфа.

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

Для иллюстрации этого утверждения вновь обратимся к бинарным отношениям ииз примера 2.

Очевидно, что классы эквивалентности
,
,
элементов множества
по отношениюне пусты, попарно не пересекаются, а их объединение совпадает с самим множеством
. Следовательно,порождает разбиение множества
на три подмножества:
,
,.

Для классов эквивалентности
,
,
элементов
по отношениюимеем: классы эквивалентности элементов
исовпадают и при этом не имеют общих элементов с классом эквивалентности элемента, объединение всех классов совпадает с множеством
. Следовательно, отношениепорождает разбиение множества
на два подмножества:
,
.

Рассмотрим еще один важный класс бинарных отношений.

Определение. Бинарное отношение называется отношением порядка, если оно рефлексивно, антисимметрично и транзитивно.

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

Например, отношениями порядка являются отношенияииз примера 2 (- линейного,- частичного).

Пример 3. Рассмотрим на множестве
бинарное отношение, определяемое условием. Это отношение рефлексивно, антисимметрично и транзитивно, и, значит, является отношением порядка, причем частичного, поскольку элементне связан с элементоми элементне связан с элементом.

Лекция 3.

п.3. Отношения на множествах. Свойства бинарных отношений.

3.1. Бинарные отношения .

Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.

Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.

В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами ) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.

Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).

Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.

Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.

Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .

4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями

.

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

Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

. ,

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.

Введем обобщенное понятие отношения.

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

rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }

Многоместные отношения удобно задавать с помощью реляционных таблиц . Такое задание соответствует перечислению множества n -к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных . Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.

Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:

r-1={(b , a ) | (a , b )Îr}.

Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:

t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.

Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:

r={(1, x ), (1, y ), (3, x )};

s={(x ,), (x , !), (y , d), (y , à)}.

Найти r-1 и s◦r, r◦s.

Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};

2) Используя определение композиции двух отношений, получаем

s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},

поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;

из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;

из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;

из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

2) ;

3) - ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.

Свойство 3 доказать самостоятельно.

3.2. Свойства бинарных отношений .

Рассмотрим специальные свойства бинарных отношений на множестве A .

Свойства бинарных отношений.

1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .

2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .

3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.

4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .

5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.

Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?

Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

	(a , b )Îr	(b , a )	(b , a )Îr?

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

	(a , b )Îr	(b , c )Îr	(a , c )	(a , c )Îr?

Как по матрице представления

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

3.3 Отношение эквивалентности. Отношение частичного порядка.

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение 3.6. Отношение r на A есть отношение эквивалентности , если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности a rb часто обозначается: a ~ b .

Пример 3. 8 . Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .

Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;

это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;

это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .

Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.

Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,

Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.

Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

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

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

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

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.

которых может быть отрицательной величиной, например, труд. Но потребление труда потребителем не может превосходить естественно определенной величины - 24 часа.

Свойство «продолжаемости вверх» означает, что, потенциально, потребителю доступно неограниченное количество блага. Конечно, этого свойства хотелось бы избежать, и во многих современных работах, например, по общему равновесию, оно отсутствует, но ряд основных классических результатов теории потребителя значительно проще формулируется и получается в случае его выполнения. Действительно, при отсутствии этого свойства мы уже, например, не можем быть уверены о том, что потребитель израсходует весь получаемый им доход (т. е. что выбор потребителя принадлежит бюджетной линии).

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

Свойство 0 X имеет достаточно прозрачный смысл, оно фактически означает, что потребитель потенциально может ничего не потреблять. Такая ситуация не означает что это будет его выбором, но мы признаем за ним такую возможность. Иногда бывает удобно предполагать, что множество допустимых альтернатив представляет собой неотрицательный ортант Rl + , т. е. X = Rl + . В дальнейшем, в каждом конкретном случае, будет либо указано, либо ясно из контекста, какой из вышеприведенных случаев имеется в виду8 .

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

2.2 Бинарные отношения и их свойства

Чтобы мотивировать и пояснить понятие бинарного отношения, рассмотрим известную детскую игру «камень-ножницы-бумага». Предполагается, что: камень побеждает ножницы (тупит), ножницы побеждают бумагу (режут), бумага побеждает камень (оборачивает), в остальных случаях (например, камень - камень) - боевая ничья. Будем говорить, что x находится в отношении R к y и писать x R y, в случае, если x побеждает y, где x и y принадлежат множеству {камень, ножницы, бумага}. Естественно отождествить отношение R с множеством, элементами которого являются упорядоченные пары9 hкамень, ножницыi, hножницы, бумагаi, hбумага, каменьi и только они. Отметим, что так определенное отношение (множество) R, очевидно, является подмножеством множества, состоящего из всевозможных упорядоченных пар, где каждый элемент пробегает множество {камень, ножницы, бумага}.

Этот простой пример приводит нас к следующему определению бинарного отношения.

Определение 1:

Пусть X - произвольное непустое множество. Декартовым квадратом множества X назовем множество, обозначаемое X × X , элементами которого являются всевозможные упорядоченные пары hx, yi, где x, y пробегают все множество X . Под бинарным отношением R, заданным на множестве X , будем понимать, некоторое подмножество декартова квадрата X × X , т. е. формально R X × X .

8 Более подробное обсуждение понятия блага и множества допустимых альтернатив см. в книге Э. Маленво:

Лекции по микроэкономическому анализу, М.: Наука, 1985, гл. 1, § 3 и гл. 2, § 4.

9 Выражение «упорядоченная пара» означает, что пары ha, bi и hb, ai считаются различными.

2.2. Бинарные отношения и их свойства

Другими словами бинарное отношение - это некоторое множество упорядоченных пар hx, yi, где x и y - элементы множества X . Понятие бинарного отношения имеет достаточно простую графическую иллюстрацию (см. Рис. 2.1 ).

Рис. 2.1. Бинарное отношение R, заданное на множестве X

При рассмотрении бинарных отношений в случае, когда пара hx, yi принадлежит множеству R, вместо hx, yi R обычно пишут x R y и говорят, что x находится в отношении R к y.

Определим теперь некоторые свойства бинарных отношений, которые мы в дальнейшем будем использовать при рассмотрении предпочтений 10 .

Определение 2:

Бинарное отношение R называется

рефлексивным , если x X выполнено x R x

иррефлексивным 11 , если x R x не выполняется ни при каком x X (т. е. x X(x R x));

симметричным , если x, y X из x R y следует y R x;

Асимметричным , если x, y X из x R y следует, что y R x неверно;

Транзитивным , если x, y, z X выполнено

(x R y и y R z) x R z;

отрицательно транзитивным , если x, y, z X выполнено

((x R y) и(y R z))(x R z);

Полным , если x, y X выполнено либо x R y, либо y R x, либо и то и другое.

Проиллюстрируем эти свойства бинарных отношений на примерах.

11 Часто это свойство также называют нерефлексивностью, но такая терминология приводит к парадоксальным выражениям. Например, «бинарное отношение не является ни рефлексивным, ни нерефлексивным». Чтобы избежать этой игры слов, мы и используем термин «иррефлексивность».

2.2. Бинарные отношения и их свойства

Пусть X - множество студентов, учащихся в этом учебном году в Новосибирском Государственном Университете, R - отношение «выше ростом, чем» заданное на X . Посмотрим, каким из указанных выше свойств удовлетворяет данное бинарное отношение.

Очевидно, что какого бы мы студента ни взяли, его рост не может быть больше его же роста, т. е., например, 175 не может быть больше 175. Таким образом, это отношение является иррефлексивным и не удовлетворяет свойству рефлексивности.

Это отношение также является асимметричным и не является симметричным. Действительно, пусть h(a) - рост некоторого студента a, а h(b) - рост студента b, и a R b, т. е. студент a имеет больший рост, чем b (h(a) > h(b)). Тогда вполне понятно, что неверно (h(b) > h(a)), что и означает, что неверно b R a. Таким образом, с учетом произвольности выбора a и b получили желаемое.

Проверим теперь, что данное отношение является транзитивным. Из множества X возьмем трех произвольных студентов a, b, c, чей рост составляет h(a), h(b) и h(c) соответственно, причем выполнено следующее: h(a) > h(b) и h(b) > h(c). Очевидно, что по свойству сравнения действительных чисел мы имеем, что h(a) > h(c). Это в точности означает, что a R c и мы, таким образом, показали транзитивность R.

Выполнение свойства отрицательной транзитивности мы проверим чуть позже, а сейчас перейдем к проверке свойства полноты. Как несложно понять, данное отношение не является полным, если среди студентов есть хотя бы двое с одинаковым ростом. В этом случае ни один из этих двух студентов не будет выше другого и, таким образом, мы имеем нарушение полноты. Если же среди нашего множества X нет ни одной пары студентов с одинаковым ростом, то введенное на X отношение «выше ростом, чем» обладает свойством полноты. 4

Пусть на множестве X = R2 + задано отношение R по правилу (x1 , x2 ) R (y1 , y2 ) x1 + y2 > y1 + x2 . Перед тем как отвечать на вопрос о том, каким свойствам удовлетворяет данное бинарное отношение, заметим, что x1 + y2 > y1 + x2 x1 − x2 > y1 − y2 , т. е. (x1 , x2 ) R (y1 , y2 ) x1 − x2 > y1 − y2 . Как несложно догадаться, данное бинарное отношение удовлетворяет тем же свойствам, что и отношение > на действительной прямой, т. е. полнота, транзитивность, рефлексивность. (Проверьте самостоятельно выполнение/невыполнение усло-

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

Эти определения также легко проиллюстрировать графически в духе Рис. 2.1 . Так, например, рефлексивность означает, что вся диагональ декартова квадрата X ×X принадлежит R. Свойство симметричности означает, что множество R симметрично относительно диагонали декартова квадрата. Полнота означает, что если мы «согнем по диагонали» декартов квадрат, то в итоге получим треугольник без выколотых точек.

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

Теорема 1:

Каждое асимметричное бинарное отношение является иррефлексивным.

Каждое полное бинарное отношение является рефлексивным.

2.2. Бинарные отношения и их свойства

Каждое иррефлексивное и транзитивное бинарное отношение является асимметричным.

Отношение R является отрицательно транзитивным тогда и только тогда, когда

x, y, z X из x R y следует x R z или z R y.

Доказательство: Доказательство свойств тривиально. С целью демонстрации техники доказательства мы докажем только третий пункт теоремы.

Предположим противное, т. е. пусть отношение R иррефлексивно, транзитивно, но не является асимметричным. Тогда найдется пара x, y X такая, что x R y и y R x. Так как отношение R транзитивно, то из x R y и y R x следует x R x. Получили противоречие с иррефлексивностью.

Пример 3 (продолжение Примера 1 ):

Нам осталось проверить свойство отрицательной транзитивности. Для его проверки воспользуемся представлением этого свойства из только что доказанного утверждения. Для этого из множества X возьмем трех произвольных студентов a, b, c, чей рост составляет h(a), h(b) и h(c) соответственно, причем выполнено h(a) > h(b). Очевидно, что каким бы ни был h(c), должно быть выполнено хотя бы одно из неравенств h(a) > h(c) или h(c) > h(b). Таким образом, видим, что для данного отношения R выполнено свойство отрицательной транзитив-

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

2.2.1 Задачи

/ 1. Предположим, условно, что существует всего два города, в каждом из которых продаются по три товара. Какова размерность пространства благ, исходя из определения блага по Дебре?

/ 2. Пусть X - множество всех ныне живущих людей на планете Земля. Проверьте выполнение следующих свойств:

полнота,

рефлексивность,

симметричность,

транзитивность,

отрицательная транзитивность

для следующих бинарных отношений, заданных на X:

(a) «является потомком»;

(b) «является внуком»;

(c) «является родителем такого же числа детей, что и»;

(d) «состоит в браке с» (допуская полигамию);

(e) «состоит в браке с» (предполагая моногамные отношения);

(f) «состоит в родстве с»;

(g) «хотя бы раз в жизни думал о».

/ 3. Пусть X - множество населенных пунктов на планете Земля. Какими свойствами обладают следующие отношения:

(a) «расположен восточнее» (в случае, если Земля круглая);

(b) «расположен восточнее» (в случае если, Земля плоская и стоит на черепахах);

(c) «имеет ту же численность, что и. . . »;

(d) «имеет то же число безработных, что и. . . »?

Определения

• 1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RAB, RAА.
• 2. Если А=В, то R - это бинарное отношение на A.
• 3. Обозначение: (x, y)R xRy.
• 4. Область определения бинарного отношения R - это множество R = {x: существует y такое, что (x, y)R}.
• 5. Область значений бинарного отношения R - это множество R = {y: существует x такое, что (x, y)R}.
• 6. Дополнение бинарного отношения R между элементами А и В - это множество R = (AB) R.
• 7. Обратное отношение для бинарного отношения R - это множество R1 = {(y, x) : (x, y)R}.
• 8. Произведение отношений R1AB и R2BC - это отношение R1 R2 = {(x, y) : существует zB такое, что (x, z)R1 и (z, y)R2}.
• 9. Отношение f называется функцией из А в В, если выполняется два условия:
  • а) f = А, f В
  • б) для всех x, y1, y2 из того, что (x, y1)f и (x, y2)f следует y1=y2.
• 10. Отношение f называется функцией из А на В, если в первом пункте будет выполняться f = А, f = В.
• 11. Обозначение: (x, y)f y = f(x).
• 12. Тождественная функция iA: AA определяется так: iA(x) = x.
• 13. Функция f называется 1-1-функцией, если для любых x1, x2, y из того, что y = f(x1) и y = f(x2) следует x1=x2.
• 14. Функция f: AB осуществляет взаимно однозначное соответствие между А и В, если f = А, f = В и f является 1-1-функцией.
• 15. Свойства бинарного отношения R на множестве А:
  • - рефлексивность: (x, x)R для всех xA.
  • - иррефлексивность: (x, x)R для всех xA.
  • - симметричность: (x, y)R (y, x)R.
  • - антисимметричность: (x, y)R и (y, x)R x=y.
  • - транзитивность: (x, y)R и (y, z)R (x, z)R.
  • - дихотомия: либо (x, y)R, либо (y, x)R для всех xA и yA.
• 16. Множества А1, A2, ..., Аr из Р(А) образуют разбиение множества А, если
• - Аi , i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Подмножества Аi , i = 1, ..., r, называются блоками разбиения.

• 17. Эквивалентность на множестве А - это рефлексивное, транзитивное и симметричное отношение на А.
• 18. Класс эквивалентности элемента x по эквивалентности R - это множество [x]R={y: (x, y)R}.
• 19. Фактор множество A по R - это множество классов эквивалентности элементов множества А. Обозначение: A/R.
• 20. Классы эквивалентности (элементы фактор множества А/R) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R, классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R. Классы эквивалентности либо не пересекаются, либо совпадают.
• 21. Предпорядок на множестве A - это рефлексивное и транзитивное отношение на А.
• 22. Частичный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А.
• 23. Линейный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пусть A={1, 2, 3}, B={a, b}. Выпишем декартово произведение: AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }. Возьмём любое подмножество этого декартова произведения: R = { (1, a), (1, b), (2, b) }. Тогда R - это бинарное отношение на множествах A и B.

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R - это множество R = {1, 2} {1, 2, 3}, то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3, a) или (3, b). Если добавить обе пары, то не будет выполняться второе условие, так как ab. По этой же причине из R нужно выбросить одну из пар: (1, a) или (1, b). Таким образом, отношение R = { (1, a), (2, b), (3, b) } является функцией. Заметим, что R не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1, a), (2, a), (3, a) }, { (1, a), (2, a), (3, b) }, { (1, b), (2, b), (3, b) } и т.д.

Пусть A={1, 2, 3}. Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) }. Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) }.

Примеры решения задач

1. Найти R, R, R1, RR, RR1, R1R для R = {(x, y) | x, y D и x+y0}.

Если (x, y)R, то x и y пробегают все действительные числа. Поэтому R = R = D.

Если (x, y)R, то x+y0, значит y+x0 и (y, x)R. Поэтому R1=R.

Для любых xD, yD возьмём z=-|max(x, y)|-1, тогда x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Поэтому RR = RR1 = R1R = D2.

2. Для каких бинарных отношений R справедливо R1= R?

Пусть RAB. Возможны два случая:

• (1) AB. Возьмём xAB. Тогда (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Противоречие.
• (2) AB=. Так как R1BA, а RAB, то R1= R= . Из R1 = следует, что R = . Из R = следует, что R=AB. Противоречие.

Поэтому если A и B, то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)R (x-y) - рациональное число. Доказать, что R есть эквивалентность.

Рефлексивность:

Для любого xD x-x=0 - рациональное число. Потому (x, x)R.

Симметричность:

Если (x, y)R, то x-y = . Тогда y-x=-(x-y)=- - рациональное число. Поэтому (y, x)R.

Транзитивность:

Если (x, y)R, (y, z)R, то x-y = и y-z =. Складывая эти два уравнения, получаем, что x-z = + - рациональное число. Поэтому (x, z)R.

Следовательно, R - это эквивалентность.

4. Разбиение плоскости D2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R, соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).

а) две точки эквивалентны, если лежат на прямой вида y=2x+b, где b - любое действительное число.

b) две точки (x1,y1) и (x2,y2) эквивалентны, если (целая часть x1 равна целой части x2) и (целая часть y1 равна целой части y2).

с) решить самостоятельно.

Задачи для самостоятельного решения

• 1. Доказать, что если f есть функция из A в B и g есть функция из B в C, то fg есть функция из A в C.
• 2. Пусть A и B - конечные множества, состоящие из m и n элементов соответственно.

Сколько существует бинарных отношений между элементами множеств A и B?

Сколько имеется функций из A в B?

Сколько имеется 1-1 функций из A в B?

При каких m и n существует взаимно-однозначное соответствие между A и B?

3. Доказать, что f удовлетворяет условию f(AB)=f(A)f(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.

Систематизация свойств.

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

Свойство рефлексивности рассматривается для одного элемента множества.

Отношение называется рефлексивным , если для любого предмета из области его определения имеет место это отношение предмета к самому себе. Отношение ровесник, определенное на области пар людей, рефлексивно, потому что любой человек ровесник самого себя.

Если отношение имеет место не для любой такой пары, то оно называется не рефлексивным . Нерефлексивно отношение любит , определенное на области пар людей, так как не все люди любят себя.

Если отношение не имеет места ни для одной такой пары, то отношение называется анти рефлексивным . Отношение больше, определённое на области пар материальных предметов, антирефлексивно, поскольку ни один предмет не больше самого себя.

Свойство симметричности рассматривается для двух разных элементов множества.

Отношение называется симметричным , когда для любых пар предметов из области его определения верно, что, когда это отношение x и y , то оно имеет место и в паре (y,x) . Отношение ровесник симметрично, так как для любых двух людей верно, что, если первый ровесник второго, то и второй ровесник первого.

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

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

Свойство транзитивности рассматривается для трёх разных элементов множества.

Отношение называется транзитивным , если оно обязательно имеет место для пары  (x,z) при условии его наличия в парах (x,y) и (y,z) . Отношение ровесник транзитивно, так как для любых трёх людей, если один человек ровесник другого, а тот ровесник третьего, первый непременно является ровесником третьего.

Отношение называется не транзитивным , если это верно не для любыхпредметов из области определения отношения. Нетранзитивно отношение любит , потому что неверно, что оно имеет место в паре (x,z) всегда, когда оно наличествует в парах (x,y) и (y,z), т. е. не обязательно, чтобы первый человек любил третьего, когда первый любит второго, а второй любит третьего.

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

Определения.

• Определение . Отношение ρ называется рефлексивным , если каждый элемент x∈A находится в этом отношении сам с собой: xρx для всех x∈A . На языке кванторов: ∀ x∈A: xρx
• Определение. Отношение ρ называется симметричным , если из того, что xρy следует, что yρx: ∀x,y∈A: xρy⟹ yρx
• Определение. Отношение ρ называется транзитивным , если из того, что xρy и yρz , следует, что xρz : ∀x,y,z∈A: (xρy ∧ yρz) ⟹ xρz
  • не рефлексивным , если: ¬∀ x∈A: xρx
  • не симметричным , если: ¬∀x,y∈A: xρy⟹ yρx
  • не транзитивным , если: ¬∀x,y∈A: (xρy∧ yρz)⟹ xρz
    • анти рефлексивным (иррефлексивным), если: ∀x∈A: ¬(xρx)
    • анти симметричным , если: ∀x,y∈A : (xρy⟹ yρx) ⟹ x=y
    • анти транзитивным , если: ∀x,y,z∈A: (xρy∧ yρz) ⟹ ¬(xρz)
• Определение. Бинарное отношение на некотором множестве называют эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.