Отношение на множествеВсякое множество ГÌАхА декартово произведение множества А самого на себя называется отношением на множестве А. Отношение Г называется рефлексивным, если для всех а ÎА верно а Г а. Отношение Г называется симметричным, если для всех а, b ÎА, верно а Г b Þ b Г а. Отношение Г называется транзитивным, если для любого а,b, с ÎА, а Г b, b Г с Þ а Г с. Отношение Г называется антирефлексивным, если для любого а ÎА а Г а никогда не выполняется. Отношение Г называется антисимметричным, если для любого а ÎА и b ÎА а Г b и b Г а одновременно невозможно. Отношение Г называется асимметричным, если для любых а, b ÎА из а Г b и b Г а Þ а=b. Если отношение Г рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности. Теорема. Если на множестве А задано отношение эквивалентности Г, то множество А распадается на объединение непересекающихся классов эквивалентности. Отношение Г называется отношением нестрогого порядка, если оно рефлексивно, асимметрично, транзитивно. Отношение Г называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно. Множество с заданным на нем отношением порядка называют упорядоченным множеством.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1. На множестве людей L задано отношение Г – «жить на одной улице». Проверить, является ли оно отношением эквивалентности. Решение. Для того чтобы отношение Г было отношением эквивалентности, необходимо, чтобы оно было рефлексивным, симметричным, транзитивным. 1. Так как каждый человек живет сам с собой на одной улице, то l Г l выполняется, а значит отношение Г – рефлексивно. 2. Так как из того, что человек l 1 живет на одной улице с человеком l 2 следует, что и l 2 живет на одной улице с l 1, т.е. из l 1Г l 2 Þ l 2Г l 1, то значит отношение Г – симметрично. 3. Очевидно, что из l 1Г l 2 и l 2Г l 3 следует l 1Г l 3. Таким образом, отношение Г – отношение эквивалентности. Задача 2. Пусть А=R – множество действительных чисел. Введем на R отношение Г: х Г у, если х £ у. Проверить, является ли отношение Г отношением порядка. Решение. 1. Проверим на рефлексивность. Так как хГх выполняется, т.е. х£х, то Г – рефлексивно. 2. Проверим на симметричность. Так как из хГуÞуГх только в случае, когда х=у (х£у, у£х Þх=у), то отношение Г – асимметрично. 3. Проверим на транзитивность. Так как из хГу, уГzÞхГz (х£у, у£zÞх£z), то отношение Г – транзитивно. Из 1.-3. следует, что Г – отношение нестрогого порядка, а значит, отношение Г является отношением порядка.
|
