5. Бинарные отношения. Отношения эквивалентности и теорема о разбиении множества
Определение 5.1
Бинарным отношением между элементами множеств \(Х\) и \(У\) называют подмножество \(R\) в прямом произведении этих множеств. Обозначение: \(𝑥𝑅𝑦\)
Виды бинарных отношений
- Рефлексивное: если \(Х\) и \(У\) совпадают: \(\forall x \in X \quad xRx\)
- Симметричное: если \(X \rightarrow Y\) и \(Y \rightarrow X\) совпадают: \(\forall x \in X, y \in Y \quad xRy \Rightarrow yRx\)
- Транзитивное: \(xRy\) и \(yRz \Rightarrow xRz\). Суперпозиции бинарных отношений совпадают
Определение 5.2
Отношения эквивалентны, если данные отношения одновременно рефлексивны, симметричны, транзитивны. Обозначение: \(X \sim Y\) (В след. билетах мы скажем другое определение)
Определение 5.3
Классом эквивалентности \(R\) называют \(A \subset X\), образованное всеми элементами \(Х\), эквивалентными некоторому элементу \(х\)
Лемма
Любые два класса эквивалентности либо совпадают, либо не пересекаются
Доказательство
Исходя из определения 5.3 можно говорить о том, что данное отношение одновременно симметрично, рефлекторно и транзитивно \(\Rightarrow\) при любых элементах двух отношений эти элементы либо совпадают, либо не совпадают в том случае, если в двух классах эквивалентности сравниваются различные элементы множеств