Отношение эквивалентности. Фактормножество множества по отношению.

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 7Следующая ⇒

Отношение -произвольное подмножество R множества Aⁿ всех кортежей (упорядоченных наборов) вида (a₁,..., a_n), где a₁,..., a_n -элементы некоторого множества A; в этом случае говорят, что R есть n -мерное отношение на A.

Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Отношение R называется рефлексивным, если для любого элемента имеет место aRa.

Отношение R называется симметричным, если для любой пары из отношения aRb следует bRa.

Отношение R называется транзитивным, если для любых a, b, c из отношений aRb и bRc следует aRc.

Пусть на множестве M задано отношение эквивалентности R. Осуществим следующее построение. Выберем элемент и образуем класс C1 (подмножество M), состоящий из элемента a1 и всех элементов, эквивалентных ему в рамках данного отношения. Затем выберем элемент и образуем класс C2, состоящий из a2 и эквивалентных ему элементов. Продолжая эти действия, получим систему классов C1,C2,… (возможно, бесконечную) такую, что любой элемент из множества M входит хотя бы в один класс, то есть . Эта система обладает следующими свойствами: она образует разбиение множества M, то есть классы попарно не пересекаются; любые два элемента из одного класса эквивалентны; любые два элемента из разных классов не эквивалентны.

Построенное разбиение, то есть система классов – подмножеств множества M, называется системой классов эквивалентности по отношению R. Множество классов эквивалентности называется фактормножеством множества A по отношению R.

13. Отношение предпорядка, упорядоченности, строгой упорядоченности. Отношение частичного и полного порядка.

Отношение -произвольное подмножество R множества Aⁿ всех кортежей (упорядоченных наборов) вида (a₁,..., a_n), где a₁,..., a_n -элементы некоторого множества A; в этом случае говорят, что R есть n -мерное отношение на A.

Бинарное отношение (двухмерное) R в множестве М, обладающее следующими свойствами: рефлексивности: (" aÎ M) ((a, a)Î R); антисимметричности: (" a, bÎ M) (((a, b)Î R) и (b, a)Î R)╚ a=b); транзитивности: (" a, b, cÎ M) (((a, b)Î R) и (b, c)Î R)(r) (a, c)Î R) называется отношением упорядоченности и может быть обозначено: ¸.

Бинарное отношение R в множестве М, обладающее следующими свойствами: антирефлексивности: (" aÎ M) ((a, a) Ï R); антисимметричности: (" a, bÎ M) (((a, b)Î R) и (b, a)Î R)╚ a=b); транзитивности: (" a, b, cÎ M) (((a, b)Î R) и (b, c)Î R)(r) (a, c)Î R) называется отношением строгой упорядоченности и может быть обозначено: <.
Бинарное отношение R в множестве М, обладающее следующими свойствами: рефлексивности: (" aÎ M) ((a, a)Î R); транзитивности: (" a, b, cÎ M) (((a, b)Î R) и (b, c)Î R)(r) (a, c)Î R) называется отношением предпорядка. Отношение r называется отношением полного порядка, если оно транзитивно, антисимметрично и антирефлексивно (либо транзитивно и ассиметрично). Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные. Примеры: а) Отношения “ ” и “ ” являются отношениями нестрогого порядка, отношения “<” и “>” – отношениями строгого порядка (на всех основных числовых множествах). Оба отношения полностью упорядочивают множества и . б) Отношение подчинённости в трудовом коллективе создаёт строгий частичный порядок. В нём, например, несравнимыми являются сотрудники различных структурных подразделений (отделов и т. п.). в) На системе подмножеств множества отношение включения “ ” задаёт нестрогий частичный порядок, а отношение строгого включения “ ” задаёт строгий частичный порядок. Например, , а и не сравнимы.

14. Диаграмма Хассе как способ задания отношения частичного порядка на множестве.

Отношения частичного порядка рефлексивность: (" aÎ M) ((a, a)Î R); транзитивность: (" a, b, cÎ M) (((a, b)Î R) и (b, c)Î R)(r) (a, c)Î R) антисимметричность: (" a, bÎ M) (((a, b)Î R) и (b, a)Î R)╚ a=b);

Отношение «какой элемент более предпочтителен» определено не для каждой пары.

Пусть aRb и a<b (b предпочтительней, чем а) Уровни иерархии: Нижн. уровни: эл-ты, являющиеся наименее предпочтительными. Выше уровнии: эл-ты, которые над ними доминируют. A={a,b,c} Множество булеан (множество всех подмножеств данного множества). Мощность булеана определяется как: . В данном случае она равна 8. Отношение быть подмножеством: транзитивное и антисимметричное (следовательно отношение порядка).

Диаграммы Хассе используют для наглядного представления ЧУМ. На а этих диаграммах изображают элементы ЧУМ, причем если элемент a предшествует элементу b, то a рисуют ниже b, и соединяют отрезком, если a непосредственно предшествует b.

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров