1. Понятие отношения.Подмножество R⊂Xn называется n-местным или n-арным отношением на множестве X. Говорят, что элементы x1, x2, …, xn (в указанном порядке) связаны отношением R или находятся в отношении R, если (x1, x2, …, xn)∈R. Наиболее часто в приложениях используются двухместные, или бинарные отношения, которые в основном и будут изучаться в дальнейшем. Иногда используются и другие отношения. При n=1 отношение называется унарным. Унарное отношение на множестве X – это просто некоторое подмножество R множества X. Унарное отношение можно трактовать как свойство: элемент x∈X обладает свойством R, если x∈R. При n=3 отношение называется тернарным. В качестве примера приведем отношение R на множестве действительных чисел, которое содержит все тройки чисел (x1, x2, x3) такие, что x3=x1+x2. Например, (1, 2, 3)∈R, (2, 3, 4)∉R.
По определению бинарное отношение R на множестве X – это подмножество декартова произведения X×X. Бинарное отношение можно рассматривать как соответствие из X в X. Тем самым для бинарных отношений на множестве X определены булевы операции (объединение, пересечение и др.), операция композиции, обращение. Диагональное соответствие EX отвечает отношению равенства:
EX = {(x, x) | x∈X} = {(x,y)| x=y, x,y∈X } ⊂ X×X.
Если x и y связаны отношением R, то часто вместо (x,y)∈R пишут xRy. Например, для отношения «равно» и отношения «меньше» на множестве действительных чисел вместо (x,y)∈= и (x,y)∈< принято писать соответственно x=y и x<y. Эти два отношения являются примерами двух важнейших классов бинарных отношений – отношений эквивалентности и отношений порядка.
2. Свойства бинарных отношений. Пусть R⊂X×X – бинарное отношение на множестве X (мы будем далее опускать слово «бинарное», когда это не ведет к недоразумениям).
Отношение R называется рефлексивным, если оно содержит все пары вида (x,x), то есть xRx для любого x из X. Отношение R называется антирефлексивным, если оно не содержит ни одной пары вида (x,x). Например, отношение x≤y рефлексивно, а отношение x<y антирефлексивно. Рефлексивное отношение на множестве действительных чисел изображается на координатной плоскости множеством точек, содержащим прямую y=x. В общем случае рефлексивность отношения R означает, что R⊃EX, а антирефлексивность – что R∩EX=∅.
Отношение R называется симметричным, если вместе с каждой парой (x,y) оно содержит также и пару (y,x), то есть xRy выполняется тогда и только тогда, когда выполняется yRx. Отношение R симметрично, если наличие (или отсутствие) связи между элементами x и y не зависит от порядка, в котором указаны эти элементы. Например, отношение x+y>0 симметрично, а отношение x+2y>0 – нет (симметричное отношение на множестве действительных чисел изображается на координатной плоскости множеством точек, симметричным относительно прямой y=x). Симметричность отношения R означает, что R=R–1.
Отношение R называется асимметричным, если невозможно одновременное выполнение условий xRy и yRx. Например, отношение x<y асимметрично. Асимметричность отношения R означает, что R∩R–1=∅. Отношение R называется антисимметричным, если одновременное выполнение условий xRy и yRx невозможно при x≠y, то есть, если xRy и yRx, то x=y. Например, отношение x≤y антисимметрично. Антисимметричность отношения R означает, что R∩R–1⊂EX. Ясно, что всякое асимметричное отношение является антисимметричным и антирефлексивным.
Отношение R называется транзитивным, если вместе с любыми парами (x,y) и (y,z) оно содержит также и пару (x,z), то есть из xRy и yRz следует xRz. Например, отношение x<y транзитивно, а отношение x+y>0 – нет. Транзитивность отношения R означает, что R2⊂R. Приведем некоторые свойства отношений, которые непосредственно вытекают из определений.
Каково бы ни было отношение R, отношение R∪EX рефлексивно.
Каково бы ни было отношение R, отношения R∩R–1 и R∪R–1 симметричны.
Если отношение R рефлексивно и транзитивно, то R2=R.
Докажем последнее утверждение.
Доказательство. Поскольку R транзитивно, имеем R2⊂R. Обратно, так как R рефлексивно, то EX⊂R, откуда, умножая на R, получаем R=REX⊂R2.
Примеры. Рассмотрим несколько отношений на множестве всех подмножеств некоторого множества U. Отношение включения X⊂Y рефлексивно, антисимметрично и транзитивно. Отношение строго включения X⊂Y, X≠Y, асимметрично и транзитивно. Пусть R – отношение, которое связывает множества X и Y, имеющие непустое пересечение, X∩Y≠∅. Это отношение симметрично, но, вообще говоря, не транзитивно (транзитивным оно окажется лишь в том случае, когда множество U состоит из одного элемента). Отношение R не рефлексивно; рефлексивным является его сужение на множество непустых подмножеств множества U.
3. Отношения эквивалентности.Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Таким образом, R⊂X×X – отношение эквивалентности на множестве X, если
R⊃EX , R–1=R и R2=R.
Простейшим примером отношения эквивалентности на множестве X может служить отношение равенства EX. Для обозначения отношений эквивалентности принято использовать символ ~.
Рассмотрим несколько примеров.
Примеры.1) Пусть X – множество функций, определенных на всей числовой прямой. Будем считать, что функции f и g связаны отношением ~, если они принимают одинаковые значения в точке 0, то есть f(x)~g(x), если f(0)=g(0). Например, sinx~x, ex~cosx. Отношение ~ рефлексивно (f(0)=f(0) для любой функции f(x)); симметрично (из f(0)=g(0) следует, что g(0)=f(0)); транзитивно (если f(0)=g(0) и g(0)=h(0), то f(0)=h(0)). Следовательно, ~ является отношением эквивалентности.
2) Пусть ~ – отношение на множестве натуральных чисел, при котором x~y, если x и y дают одинаковые остатки при делении на 5. Например, 6~11, 2~7, 1~6. Легко видеть, что это отношение рефлексивно, симметрично и транзитивно и, значит, является отношением эквивалентности.
Следующая теорема описывает в общем виде типичную ситуацию, в которой возникают отношения эквивалентности.
Теорема.Пусть ϕ – отображение множества X в некоторое множество Y. Определим отношение ~ на X, полагая x~y, если ϕ(x)=ϕ(y). Тогда отношение ~ является отношением эквивалентности.
Доказательство. Достаточно заметить, что отношение ~ рефлексивно, поскольку ϕ(x) = ϕ(x) для любого x, симметрично, поскольку ϕ(x)=ϕ(y) влечет ϕ(y)=ϕ(x), и транзитивно, поскольку из ϕ(x)= ϕ(y) и ϕ(y)=ϕ(z) следует, что ϕ(x)=ϕ(z).
Про отношение эквивалентности, описанное в предыдущей теореме, будем говорить, что оно порождается отображением ϕ. Будем обозначать это отношение эквивалентности через ~ϕ или просто через ~, когда ясно, о каком отображении идет речь. Далее мы увидим, что всякое отношение эквивалентности может быть представлено как ~ϕ для подходящего отображения.
Теорема применима к обоим рассмотренным перед ней примерам. В первом примере в качестве Y можно взять множество действительных чисел, а отображение ϕ определить на множестве функций соответствием ϕ:f→f(0). Во втором примере в качестве ϕ(x) можно взять остаток от деления x на 5.
Отображение ϕ порождает разбиение множества X на классы, содержащие элементы, имеющие одинаковый образ, то есть эквивалентные относительно ~ϕ. Описываемая ниже конструкция устанавливает взаимно однозначное соответствие между отношениями эквивалентности на множестве X и его разбиениями в общем случае. Будем говорить, что дано разбиение множества X, если задано семейство его непустых подмножеств, такое, что два различных подмножества из этого семейства не пересекаются, а объединение всех подмножеств есть X.
Всякому разбиению множества X отвечает отношение эквивалентности, задаваемое следующим образом: x~y в том и только том случае, когда x и y содержатся в одном общем подмножестве из разбиения.
Опишем теперь обратное построение.
Пусть ~ отношение эквивалентности на X. Для произвольного элемента x∈X обозначим через Ax множество всех элементов, эквивалентных x, то есть
Ax={y | y~x}.
Множества вида Ax называются классами эквивалентности. Так как x~x, то x∈Ax, так что классы эквивалентности непусты, и их объединение дает все множество X. Покажем, что различные классы эквивалентности не пересекаются. Предположим, что Ax∩Ay≠∅, и покажем, что в этом случае Ax=Ay. Пусть z∈Ax∩Ay. Тогда z~x и z~y. Так как отношение эквивалентности симметрично, то y~z. Теперь из y~z и z~x в силу транзитивности следует y~x, так что y∈Ax. Пусть z – произвольный элемент из Ay. Тогда z~y. Так как y~x, отсюда по транзитивности следует , что z~x, то есть z∈Ax. Таким образом, Ax⊂Ay. Аналогично Ay⊂Ax. Замечание.Соответствие x→Ax задает отображение ϕ:X→2X множества X в множество его подмножеств 2X. При этом ϕ(x)=ϕ(y) тогда и только тогда, когда Ax=Ay, то есть когда x~y. Значит, ~ = ~ϕ.Таким образом, произвольное отношение эквивалентности на множестве X порождается некоторым отображением.
