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

Пусть F=<X, X, G_F >, где G_F X² – отношение на множестве Х.

G_F = {(x,y)| xX, yX, xFy}.

Определение: Отношение на множестве Х называется рефлексивным, если всякий элемент xX вступает в это отношение сам с собой:

(xX) [xFx]- «и»

Особенности графа: в каждой вершине графа рефлексивного на множестве Х отношения - петля.

Особенности графика: графику рефлексивного отношения принадлежат все пары вида (х,х): (xX) (x; x).

Определение 2: Отношение F на множестве Х называется антирефлексивным, если ни один элемент множества Х не вступает в отношения F сам с собою:

(хХ)[ ]-«и».

Особенности графа: ни в одной вершине графа нет петли.

Особенности графика: графику не принадлежит ни одна пара с равными компанентами (вида (х,х)): (xX) (x; x).

Примеры: отношение равенства на множестве множеств; не меньше; не больше на числовом множестве; параллельности на множестве прямых и т.д. – рефлексивные отношения. Отношения неравенства; больше; меньше на числовых множествах; перпендикулярности на множестве прямых и др. – антирефлексивные отношения.

Рассмотрим отношение, заданное на множестве людей: «быть отцом».

Является ли оно рефлексивным? Нет, так как ни один человек не может быть отцом самому себе. Стало быть, оно антирефлексивное.

Определение 3: Отношение F на множестве Х называется симметричным, если для любых элементов х,уХ истинно утверждение: если элемент x вступил в отношение F c элементом y (хFy), то и элемент y вступил в данное отношение с элементом x (уFx):(х,уХ)[xFyyFx] – «и».

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

Особенности графика: если графику принадлежит пара (х,у), то и пара (у,х) принадлежат этому графику: (x,yX) [(х,у) G_F (y,x) G_F].

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

Определение 4: Отношение F на множестве Х называется асимметричным, если для любых двух элементов х и у множества Х верно утверждение: если элемент хX вступает в отношение F с элементом у, то неверно, что элемент у вступает в отношение F c элементом х этого же множества: (x,yX) [xFy]-«и».

Другими словами: ни для каких элементов х и у Х; не может быть одновременно xFy u yFx.

Особенности графа: все стрелки графа асимметричного отношения одинарные и ни в одной вершине нет петель!

Особенности графика: (x,yX) если (х,у) G_F, то (у,х) G_F.

Примеры: отношения «>»; «<»; «толще» и т.д. являются асимметричными.

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

Итак, F - антисимметрично (x,yX) (x ≠ y) [xFy=>].

Особенности графа: граф антисимметричного отношения содержит только одинарные стрелки и могут быть петли.

Особенности графика: (x,yX) если (x,y)G_F, то (у,х) G_F, и (x,x)G_F

Замечание: асимметричное отношение - это одновременно антисимметричное и антирефлексивное отношение.

Определение 6: Отношение F на множестве Х называется транзитивным, если для любых трех элементов множества Х справедливо утверждение: если элемент х находится в отношении F с элементом y, а элемент y находится в отношении F с элементом z, то элемент х вступит в отношение F с элементом z: (xFy)Λ(yFz)=>(xFz).

Таким образом, F – транзитивно (x,y,zX)[xFyyFzxFz].

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

Особенности графика: если (x,y)G_F (y,z)G_F то (х,z)G_F.

Пример 1: отношение параллельности на множестве прямых является транзитивным: (aв)(вс) (ac) для любых (a,в,с) из множества прямых на плоскости.

Пример 2: отношение «>» на множестве действительных чисел:

(х > y)(y > z) (x > z)(x,y,zR).

Определение 7: Отношение F на множестве Х называется антитранзитивным, если для (х,у,zX) верно утверждение: если элемент х находится в отношении F с элементом y, а элемент y находится в отношении F с элементом z, то элемент х не вступает в отношение F с элементом z: [xFyyFz=>].

Таким образом, F - антитранзитивно (x,y,zX)[xFyyFz=>].

Особенности графа: если граф содержит стрелку от х к у и у к z, то не содержит стрелку от х к z.

Особенности графика: если (x,y)G_F (y,z)G_F то (х,z) G_F.

Пример 1: отношение перпендикулярности на множестве прямых антитранзитивно.

а

в с

Определение 8: Отношение F на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

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

Отношение эквивалентности связано с разбиением множества на классы.

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

Доказательство смотри стр 174 учебника ч.1 (Охременко Д.В., Тонких А.П.)

Пример: Пусть X = {x ׀ xN, x < 12}. Зададим отношение F: x и у делятся на 5 с одинаковым остатком.

Является ли оно отношением эквивалентности? Если да, то задайте классы эквивалентности. Укажите граф.

Данное отношение рефлексивно, симметрично, транзитивно. Следовательно, оно является отношением эквивалентности и производит разбиение множества Х на классы эквивалентности.

1:5=0(ост.1) 6:5=1(ост.1) 11:5=2(ост.1)

2:5=0(ост.2) 7:5=1(ост.2)

3:5=0(ост.3) 8:5=1(ост.3)

4:5=0(ост.4) 9:5=1(ост.4)

5:5=1(ост.0) 10:5=2(ост.0)

Тогда Х ₁ = {1,6,11} X ₂ = {2,7} X ₃ = {3,8} X ₄ = {4,9} X ₅ = {5,10}.

Все условия разбиения множества на классы выполнены:

X _iX_j = Ǿ (i,jN) X₁X₂X₃X₄X₅ = X.

Дата добавления: 2014-01-11