Главная Дискретная математика Бинарные отношения. Рефлексивность, симметричность, транзитивность. Классы эквивалентности.
Бинарные отношения. Рефлексивность, симметричность, транзитивность. Классы эквивалентности.

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

 

 

Декартово произведение множеств. Мощность множества

Определения:

1) Мощность множества A  – это число его элементов |A|.

2) Мощность множеств всех подмножеств множества A  равна  2^{|A|}.

3) Декартово произведение множеств A и B  – есть множество всевозможных точек вида (x,y), где x принадлежит A, y принадлежит B.

4)  Мощность декартова произведения множеств A и B равна |AxB|=|A|*|B| .

Бинарные отношения, рефлексивность, симметричность, транзитивность.

Определения:
1) Бинарное отношение между элементами множеств A  и B называется любое подмножество декартова произведения R \subseteq AxB .
2) Если  A = B, то R  – бинарное отношение на A.
3) Обозначение <x,y> \in R \Leftrightarrow xRy.
4) Область определения бинарного отношения R есть множество x, таких что существуют y и пара <x,y> принадлежит R .
5) Область значений бинарного отношения R есть множество y, что существуют x и пара <x,y> принадлежит R .
6) Дополнение бинарного отношения R между элементами A и B есть множество  -R = (AxB)\R .

7) Обратное отношение для бинарного отношения R есть множество точек <y,x> таких, что точки <x,y> принадлежат R .

8) Произведение отношенийR_{1}\subseteq AxBиR_{2}\subseteq BxCесть отношение  R_{1}R_{2}= \begin{Bmatrix} <x,z>|\exists z\in B:<x,z>\in R_{1}, <z,y>\in R_{2} \end{Bmatrix}.

9) Отношение f называется функцией из A в B , если

•    область определения бинарного отношения равна A  и областью задания является подмножеством B.
•    для любых x,y,z <x,y>\in f и<x,z>\in f \Rightarrow y=z.

10) Бинарное отношение f называется функцией из A на B, если
•    область определения бинарного отношения равна A  и областью задания является множество B,

•    для любых x,y,z <x,y>\in f и<x,z>\in f \Rightarrow y=z.

11) Если f  – функция, то<x,y>\in f обозначают y = f(x).

12) Тождественная функцияi_{A}:A\to Aопределяется i_{A}(x)=x.

13) Функция f называется 1-1-функцией, если для любыхx_{1},x_{2},y , y=f(x_{1})иy=f(x_{2}) \Rightarrow x_{1}=x_{2}.

14) Функция f:A\to B   осуществляет взаимно однозначное соответствие между множествами A и  B, если область определения бинарного отношения совпадает с A, область задания совпадает с B и f   является 1-1-функцией.
– блоки разбиения.

15) Бинарное отношение R на множестве A может иметь следующие свойства:
•    рефлексивность \forall x\in A, <x,x>\in R ,
•    иррефлексивность \forall x\in A, <x,x>\notin R,
•    симметричность \forall x,y\in A, <x,y>\in R \Rightarrow <y,x>\in R,
•    антисимметричность \forall x,y, <x,y>\in R , <y,x>\in R \Rightarrow x=y,
•    транзитивность\forall x,y,z\in A, <x,y>\in R ,<y,z>\in R \Rightarrow <x,z>\in R ,
•    дихотомия\forall x\neq yлибо<x,y>\in R, либо<y,x>\in R.

16) Эквивалентность на множестве A  – это если выполнена рефлексивность, симметричность и транзитивность отношения на A.

17) Класс эквивалентности элемента x по эквивалентности R есть множество [x]_{R} = \begin{Bmatrix} y|<x,y>\in R \end{Bmatrix}.

18) Фактор множество A по R есть множество классов эквивалентности элементов множества A и обозначается  A/R.

19) Свойства классов эквивалентности:
•    классы эквивалентности образуют разбиение множества A,
•    любому разбиению множества A соответствует отношение эквивалентности, классы эквивалентности которого совпадают с блоками указанного разбиения,
•    \forall x\in A попадает в некоторый класс эквивалентности из A/R ,
•    классы эквивалентности либо не пересекаются, либо совпадают.

20) Предпорядок на множестве  A – это выполнение рефлексивности и транзитивности отношения на  A.

21) Частичный порядок на множестве A – это выполнение рефлексивности, транзитивности и антисимметричности отношения на множестве  A.

22) Линейный порядок на множестве A  – это выполнение рефлексивности, транзитивности и антисимметричности отношения на множестве  A, удовлетворяющее условию дихотомии

23) Пусть \leq  – бинарное отношение порядка на множестве A , тогда:
•    минимальный элемент x множества A – это элемент для которого\exists y, y<x   ,
•    максимальный элемент x множества A – это элемент для которого \exists y, x<y   ,
•    наименьший элемент x множества A – это элемент для которого\forall y, x\leq y ,
•    наибольший элемент x множества A – это элемент для которого\forall y, y\leq x.

24) Если между множеством A и множеством натуральных чисел N можно установить взаимно однозначное соответствие, то множество A – счётное множество.

 

     Из этой статьи Вы узнали:

  • декартово произведение множеств
  • бинарное отношение
  • свойства бинарного отношения: рефлексивность, симметричность, транзитивность
  • классы эквиволентности и их свойства

 

Рекомендуем прочитать