Бинарное отношение между \(X\) и \(Y\) задаётся как подмножество \(X\times Y\). Отношение эквивалентности на \(X\) характеризуется рефлексивностью, симметричностью и транзитивностью. Каждый элемент определяет свой класс эквивалентности, а классы либо совпадают, либо не
Частичный порядок имеет другие свойства: рефлексивность, антисимметричность и транзитивность. Сравнимость любых двух элементов для частичного порядка не обязательна. Если любые два элемента сравнимы, порядок называется
Что важно запомнить
- Отношение \(R\) между \(X\) и \(Y\) — подмножество \(X\times Y\).
- Эквивалентность требует рефлексивности, симметричности и транзитивности.
- Класс эквивалентности элемента \(a\) состоит из всех элементов, эквивалентных \(a\).
- Пересекающиеся классы эквивалентности совпадают.
- Частичный порядок требует рефлексивности, антисимметричности и транзитивности.
- Если любые два элемента сравнимы, частичный порядок становится линейным.
Отношение \(R\) между множествами \(X\) и \(Y\) — это подмножество \(X\times Y\). Если обе компоненты берутся из \(X\), получаем отношение на \(X\). Запись \(xRy\) означает, что пара \((x,y)\) принадлежит
Отношение эквивалентности
Если \(R\) является отношением эквивалентности, вместо \(xRy\) часто пишут \(x\sim y\). Такое отношение обладает тремя свойствами. Рефлексивность означает \(x\sim x\). Симметричность означает, что из \(x\sim y\) следует \(y\sim x\). Транзитивность означает, что из \(x\sim y\) и \(y\sim z\) следует
Класс эквивалентности элемента \(a\) состоит из всех \(x\in X\), для которых \(x\sim a\). Если два класса имеют общий элемент, они совпадают. Поэтому \(X\) является объединением попарно непересекающихся классов. Множество всех классов называется фактор-множеством. Обратно, любое разбиение \(X\) на непустые попарно непересекающиеся части задаёт отношение эквивалентности: эквивалентными объявляют элементы одной
Частичный порядок
Отношение частичного порядка на \(X\) должно быть рефлексивным, антисимметричным и транзитивным. Здесь \(\preceq\) обозначает нестрогий частичный порядок. Антисимметричность означает, что из \(x\preceq y\) и \(y\preceq x\) следует
Примером служит включение подмножеств. Не все подмножества обязаны быть сравнимы. Если для любых \(x,y\) выполняется \(x\preceq y\) или \(y\preceq x\), частичный порядок называется
Пример простыми словами
На множестве \(\{0,1,2,3,4\}\) отношение «иметь одинаковый остаток при делении на 2» является отношением эквивалентности. Возникают два класса: \(\{0,2,4\}\) и \(\{1,3\}\).
Включение подмножеств множества \(\{1,2\}\) задаёт частичный порядок. Множества \(\{1\}\) и \(\{2\}\) несравнимы по включению. Для обычных чисел отношение \(\le\), напротив, является линейным порядком.
Частые ошибки
- Путать симметричность с антисимметричностью.
- Считать, что разные классы эквивалентности могут частично пересекаться.
- Требовать от частичного порядка сравнимости каждой пары элементов.
- Забывать, что разбиение состоит из непустых попарно непересекающихся частей, объединение которых даёт всё исходное множество.
