Обобщением понятия равенства является отношение эквивалентности.

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

Отношение эквивалентности разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности. Если в качестве A рассмотреть множество людей, проживающих в домах некоторого города, то отношение проживания в одном доме будет отношением эквивалентности. Более математическим примером является отношение сравнения по модулю n в множестве целых чисел Z : , если делится на n . При этом Z разбивается на классы , характеризуемые остатками от деления на n . Более общим примером является эквивалентность элементов группы G по подгруппе H : если . Классами эквивалентности здесь являются правые смежные классы по подгруппе H .

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

Связанные определения

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

Бинарные отношения могут обладать различными свойствами, такими как

Виды отношений

• Рефлексивное транзитивное отношение называется отношением квазипорядка.
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности .
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка .
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка .
• Полное антисимметричное (для любых 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.[уточнить] В терминах отношений… … Википедия

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

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