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

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

... меньше, чем ...,

... делится на ...,

... включено в ...,

... конгруэнтно ... .

Определение. Бинарным отношением (соответствием) называется всякое подмножество  множества X  Y. В этом случае говорят, что между множествами X и Y установлено бинарное соответствие. Этот факт символически записывается в виде x  y, x  X, y  Y, где  – символ отношения, указывающий конкретное подмножество множества X  Y, то есть,   X  Y.

Если множества X и Y в бинарном соответствии совпадают, то говорят об отношении между элементами множества X.

Отношение  на множестве X называется рефлексивным, если для любого элемента x  X справедливо x  x или, иначе, (x, x)  .

Если условие рефлексивности не выполняется ни для одного элемента x  X, то отношение  называется антирефлексивным.

Отношение  между элементами множества X называется симметрическим, если для любых элементов x, y  X справедливо утверждение

x  y  y  x или, то же самое, (x, y)    (y, x)  .

Отношение  между элементами множества X называется антисимметрическим, если для любых элементов x, y  X справедливо утверждение

(x, y)    (y, x)  .

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

Отношение  между элементами множества X называется тождественным, если для любых элементов x, y  X справедливо утверждение:

x  y и y  x  x = y или [(x, y)   и (y, x)   ]  x = y.

Антисимметрическое отношение является пересечением тождественного и антирефлексивного отношений.

Отношение  между элементами множества X называется транзитивным, если для любых элементов x, y, z  X справедливо

x  y, y  z  x  z или [(x, y)   и (y, z)  ]  (x, z)  .

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

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

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

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

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

Дополнительным к отношению  называется такое отношение , что

(x₁, x₂)  тогда и только тогда, когда  (x₁, x₂)  .

Композицией отношений  и  определяется как отношение

   = {(x, z)найдется y для которого (x, y)   и (y, z)  }.

Теорема 1. Для любого отношения  имеет место ·^-1 = {(x, x) (x, x)  Dom }, ^–1· = {(x, x)  (x, x)  Im }.

Теорема 2. Композиция трех бинарных отношений ассоциативно, то есть, если , ,  – бинарные отношения, то () = ().

Отношение эквивалентности

Отношение между элементами множества X, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности и обозначается x₁  x₂.

Таким образом, отношение   X  X является отношением эквивалентности, если:

a) x  x для любого элемента x  X;

b) x₁  x₂  x₂  x₁ для любых элементов x₁, x₂  X;

c) x₁  x₂ и x₂  x₃  x₁  x₃ для любых элементов x₁, x₂, x₃  X.

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

Определение. Пусть  отношение эквивалентности на множестве X и x  X. Классом эквивалентности, порожденным элементом x, называется множество {y  X | y  x}, то есть, множество всех таких y из X, которые связаны с x отношением :, то есть тех y, для которых (y, x)  .

Обозначение: x / или [x]_.

Совокупность всех классов эквивалентности отношения  на множестве X обозначается через X / или [X]_.

Разбиением множества X называется такое семейство множеств {X₁, X₂,..., X_n}, которое удовлетворяет следующим условиям:

1) X_i  , i = 1,... , n, – каждое из множеств X_i непусто;

2) X_i  X_j =  при i  j – различные множества X_i не пересекаются;

3) = X – объединение всех множеств X_i совпадает с X.

Теорема 1. Пусть на множестве X задано отношение эквивалентности . Тогда классы эквивалентности отношения  на множестве X образуют разбиение множества X, то есть,

1) Для каждого элемента x  X класс [x]_ непуст.

2) Различные классы эквивалентности не пересекаются.

3) Каждый элемент x множества X принадлежит одному из классов эквивалентности.

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

Определение. Фактор-множеством множества А по отношению эквивалентности  называется множество A / всех классов эквивалентности.