Что такое творческие
кладовые по дискретной математике
портала "Русский след"?
12.Отношения эквивалентности.
Отношение - это одна из форм всеобщей взаимосвязи всех предметов, явлений,
процессов в природе, обществе и
мышлении. Спектр отношений на
множествах многоаспектен, начиная с определения понятия множества,
аксиоматики и
заканчивая разбором парадоксов. Различных отношений на
множестве бесконечно. Но, когда говорят об бинарных
отношениях, то
подразумевают отношения между двумя величинами, объектами,
высказываниями.
Обычно отношения обозначают латинской буквой R.
Если
хRх
для любого х из поля отношения
R то такое отношение называют рефлексивным,
где х и х - объекты
мысли , а R
- это знак о том или ином виде отношения между объектами мысли.
Если хRу ® уRх, то такое отношение называется симметричным, где ® - знак импликации, сходный с союзом "! если..., то..."
Если (xRy Ùy R z) ® xRz, то такое отношение называется транзитивным, где Ù - знак конъюнкции.
Бинарное отношение, которое одновременно рефлексивно, симметрично и транзитивно называется отношением Э К В И В А Л Е Н Т Н О С Т И.
Бинарное отношение f называют функцией, если из <х, у> Î f и <х, z > Î f следует y = z. Бинарная функция применима к двум аргументам, взятым в определённом порядке, и только в этом случае она даёт значение функции для этих двух аргументов, взятых в данном порядке.
Бинарные функции называются тождественными , если они имеют одну и ту же область определения и если для каждой упорядоченной пары аргументов. лежащих в этой области, они имеют одно и тоже значение.
Бинарная функция называется симметричной, если она совпадает со своей конверсией, то есть когда меняются местами предыдущий и последующий члены высказывания..
Принято говорить, что f отображает Х на У если f есть функция, с областью определения Х и областью значений У.
Когда же f отображает Х на У и У Í Z то говорят. что f отображает Х в Z. Например, если f(x) = 2x для любого целого х , то можно сказать что f отображает множество всех целых чисел в множество всех целых чётных чисел.
Как отмечалось выше,
бинарное отношение, которое одновременно рефлексивно, симметрично и транзитивно называется отношением эквивалентности.Таким образом, отношение эквивалентности бинарных отношений характеризуется следующими свойствами:
1) рефлексивностью: (M ~ N);
2)симметричностью: если M ~ N, то N ~ M;
3) транзитивностью: если M ~ N и N ~ P то M ~ P.
Рассмотрим эти свойства подробнее.
Рефлексивность - это одно из свойств некоторых отношений, когда каждый элемент множества находится в данном отношении к самому себе. Например отношения между числами а = с и а ³ с рефлексивны, так как всегда а = а, с = с, а ³ а, с ³ с. Но отношение неравенства а > с антирефлексивно, так как неравенство а > а невозможно.
Аксиома рефлексивности записывается так: aRc ® aRa Ù cRc , здесь ® означает слово "влечёт" ("имплицирует"), а знак Ù - союз "и" (конъюнкция).
Из этой аксиомы следует: если суждение aRc истинно. то истинны и суждения aRa и cRc.
Симметричное отношение - это такое отношение между объектами, когда наличие этого отношения влечёт за собой наличие этого отношения и в том случае, если объекты поменять местами; иначе говоря при счимметричном отношении перестановка объектов не ведёт к изменению вида отношения. Например, отношение равенства а = с симметрично, так как оно эквивалентно (равносильно) отношению с = а , симметрично и отношение а ¹ с , так как оно эквивалентно отношению с ¹ а.
Транзитивное множество - это такое множество, например множество х, если выполняется следующее требование: у Î х, z Î y ® z Î x где ® это знак, представляющий слова: " если ..., то ..." Читается формула так: Если у принадлежит х, z принадлежит у, то z принадлежит х".