которых может быть отрицательной величиной, например, труд. Но потребление труда потребителем не может превосходить естественно определенной величины - 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 считаются различными.

Другими словами бинарное отношение - это некоторое множество упорядоченных пар 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 Часто это свойство также называют нерефлексивностью, но такая терминология приводит к парадоксальным выражениям. Например, «бинарное отношение не является ни рефлексивным, ни нерефлексивным». Чтобы избежать этой игры слов, мы и используем термин «иррефлексивность».

Пусть 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:

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

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

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

Отношение 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. Множества и операции над ними. Подмножеством понимают объединение в единое целое определенных вполне различаемых объектов. Объекты при этом называютэлементами образуемого ими множества.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Удобным приемом наглядного изображения операций являются диаграммы Эйлера - Венна. На них множества представлены плоскими фигурами (чаще всего кругами). Области, соответствующие множествам, полученным в результате операции, обычно выделяют цветом. На рис. 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. Рассмотрим на множестве
бинарное отношение, определяемое условием. Это отношение рефлексивно, антисимметрично и транзитивно, и, значит, является отношением порядка, причем частичного, поскольку элементне связан с элементоми элементне связан с элементом.

Свойства отношений:

1) рефлексивность;

2)симметричность;

3)транзитивность.

4)связанность.

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: х Rх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

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

Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.

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

Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно х Rх: .

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

Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y , граф содержит стрелку, идущую от y к х (рис. 35).

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

Существуют отношения, которые не обладают свойством симметричности.

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

Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

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

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRz xRz.

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z , содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а= b, b=с)(а=с).

Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b , а отрезок b перпендикулярен отрезку с , то отрезки а и с не перпендикулярны!

Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y , либо элемент y находится в отношении R с элементом х . С помощью символов это можно записать так: xy xRy или yRx.

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y , либо y>x.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y , что ни число х не является делителем числа y , ни число y не является делителем числа х (числа 17 и 11 , 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y ». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

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

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества - классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х ={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

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

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

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

Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х ={3, 4, 5, 6, 7, 8, 9, 10 } задано отношение «иметь один и тот же остаток при делении на 3 ». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9 ). Во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10 ). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8 ). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х . Следовательно, отношение «иметь один и тот же остаток при делении на 3 », заданное на множестве Х , является отношением эквивалентности.

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка , если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х< y ».

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

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

Множество Х называется упорядоченным, если на нем задано отношение порядка.

Например, множество Х= {2, 8, 12, 32 } можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х , а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.

Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.

Определения

• 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 выполняется xRy или yRx) транзитивное отношение называется отношением линейного порядка.
• Антирефлексивное асимметричное отношение называется отношением доминирования.

Виды двухместных отношений

• Обратное отношение [уточнить ] (отношение, обратное к R) - это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R −1 . Для данного отношения и обратного ему верно равенство: (R −1) −1 = R.
• Взаимо-обратные отношения (взаимообратные отношения) - отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого - областью значений другого.
• Рефлексивное отношение - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого х этого множества элемент х на­ходится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство , одновременность , сходство.
• Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отно­шении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
• Транзитивное отношение - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношение [уточнить ] - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности , подобия , одновременности, некоторые отношения родства (например, отношение братства).
• Антисимметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR −1 y следует х = у (то есть R и R −1 выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение [уточнить ] - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
• Отношение эквивалентности (отношение тождества [уточнить ] , отношение типа равенства) - двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям): Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке, подобие , одновременность . Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».
• Отношения порядка - отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») - «строгий» порядок.
• Функция - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что каждому значению x отно­шения xRy y . Пример: «y отец x ». Свойство функциональности отно­шения R записывается в виде аксиомы: (xRy и xRz )→(y ≡z ). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y , но не наоборот.
• Биекция (одно-однозначное отношение) - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у , и каждому значению у соответствует единственное значение х . Одно-однозначное отношение является частным случаем однозначного отношения.
• Связанное отношение - это двухместное отношение R , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx ). Пример: отношение «меньше» (<).

Операции над отношениями

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

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.

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

Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

Пусть теперь , . Произведением отношений , называется отношение такое, что

Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.

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

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

Имеют место следующие тождества:

Отметим, что аналоги последних двух тождеств для не имеют места.

Некоторые свойства отношения можно определить, используя операции над отношениями:

См. также

Литература

• А. И. Мальцев. Алгебраические системы. - М .: Наука, 1970.

Wikimedia Foundation . 2010 .

Смотреть что такое "Бинарное отношение" в других словарях:

Бинарное отношение - . Иначе: двуместное или двойственное. «Бинарным отношением на множестве X» называется подмножество упорядоченных пар элементов из X. Примерами Б.о. являются равенство (=), неравенства (< или >), отношение включения A Ì B.… … Экономико-математический словарь

бинарное отношение - Иначе: двуместное или двойственное. «Бинарным отношением на множестве X» называется подмножество упорядоченных пар элементов из X. Примерами Б.о. являются равенство (=), неравенства (), отношение включения A ? B. В широком смысле слова… … Справочник технического переводчика

Двуместный предикат на заданном множестве. Под Б. о. иногда понимают подмножество множества упорядоченных пар (а, 6) элементов заданного множества А. Б. о. частный случай отношения. Пусть. Если, то говорят, что элемент находится в бинарном… … Математическая энциклопедия

В логике то, что в отличие от свойства характеризует не отдельный предмет, а пару, тройку и т.д. предметов. Традиционная логика не рассматривала О.; в современной логике О. пропозициональная функция от двух или большего числа переменных. Бинарным … Философская энциклопедия

отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки

В теории потребления это формальное описание способности потребителя сравнивать (упорядочивать по желательности) разные наборы товаров (потребительские наборы). Чтобы описать отношение предпочтения, не обязательно измерять желательность… … Википедия

У этого термина существуют и другие значения, см. Отношение. Отношение математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов … Википедия

У этого термина существуют и другие значения, см. Отношение. Отношение в логике первого порядка двух и более аргументный предикат (многоместный предикат), двух и более предикатное свойство. Знак отношения: R.[уточнить] В терминах отношений… … Википедия

У этого термина существуют и другие значения, см. Эквивалентность. Отношение эквивалентности () на множестве это бинарное отношение, для которого выполнены следующие условия: Рефлексивность: для любого в, Симметричность: если … Википедия

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Бинарное отношение на мно … Википедия