Отношения на множестве
Бинарным отношением на множестве называется подмножество . Тот факт, что находится в отношении с , обозначается следующим образом: 
Областью определения бинарного отношения на множестве называется множество
,
а областью значений – множество
.
Пример 2. Примеры отношений:
– отношение равенства «=» на множестве состоит из всех пар вида , Если элемент находится в отношении равенства к элементу , то пишут ;
– отношение неравенства « » на множестве R: ;
– отношение делимости «|»на множестве : .
Так как отношения определяются как подмножества, то над ними можно производить теоретико-множественные операции.
Дополнением бинарного отношения на множестве считается множество
.
Например, если – отношение «=», то =« », а « ».
Обратным отношением(обращением) для бинарного отношения называется множество
.
Произведением отношений и называется отношение
.
Всякое подмножество называют -местным отношением на множестве .
Совокупность всех отношений на множестве , для которых заданы операции суммы, произведения, разности, дополнения и обращения, образуют алгебру отношений (исчисление отношений) множества . В частности, последняя находит применение при разработке реляционных баз данных.
Свойства отношений. Отношения делятся на различные виды в зависимости от того, обладают или не обладают некоторыми свойствами.
1. Рефлексивность: . Например, рефлексивно на множестве прямых отношение «прямая пересекает прямую ».
2. Симметричность: . Например, симметрично отношение параллельности на множестве прямых плоскости.
3. Транзитивность: . Например, транзитивно на множестве отрезков отношение «отрезок длиннее отрезка ».
Среди различных бинарных отношений выделяются два специальных типа, играющих важную роль в разнообразных математических конструкциях и доказательствах.
Отношение эквивалентности. Отношение на множестве называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности и транзитивности. Отношение эквивалентности часто обозначают: .
Пример 3. Примеры отношения эквивалентности:
– отношение «одного роста» на множестве людей;
– отношение подобия на множестве треугольников;
– отношение принадлежности двух студентов к одной студенческой группе.
Смежным классом (классом эквивалентности) элемента по эквивалентности называется множество
.
Любой элемент называется представителем этого класса.
Множество классов эквивалентности элементов множества по эквивалентности называется фактор-множеством по и обозначается .
С каждым отношением эквивалентности связано разбиение множества на непересекающиеся подмножества, которое лежит в основе всевозможных классификаций.
Разбиением множества называется всякое представление этого множества в виде суммы непересекающихся подмножеств:
, .
Здесь – множество индексов, которое может быть конечным, счетным или несчетным. Множества называют слоями разбиения.
Имеет место следующая теорема.
Теорема 2. Для того чтобы отношение позволяло разбить множество на классы, необходимо и достаточно, чтобы было отношением эквивалентности.
Пример 4. Плоскость разбита на прямые
.
Этому разбиению соответствует отношение такое, что если .
Покажем, что каждая эквивалентность отвечает некоторому разбиению множества .
Для каждого обозначим через класс всех элементов, эквивалентных :
.
Из рефлексивности следует, что . Далее, если , то есть , то . Из транзитивности имеем, что , то есть . Таким образом, . В силу симметричности отношения , то есть . Повторяя рассуждения, получим, что . Следовательно, . Таким образом, каждый элемент входит в некоторый класс и различные классы не пересекаются, то есть классы образуют разбиение множества , отвечающее отношению эквивалентности .
Приведем примеры использования отношения эквивалентности для образования математических понятий.
1. Понятие вектора. Сначала вводится понятие направленного отрезка, как пары точек . Два отрезка и объявляются эквивалентными, если середины отрезков и совпадают. Далее проверяется, что это отношение между направленными отрезками рефлексивно, симметрично и транзитивно. Класс эквивалентных отрезков и есть вектор.
2. Построение рациональных чисел из целых. Рассмотрим всевозможные пары из целых чисел такие, что . Пары и объявляются эквивалентными, если . Далее проверяется рефлексивность, симметричность и транзитивность. Класс эквивалентных пар – рациональное число.
Отношение порядка. Бинарное отношение на множестве называется отношением порядка, если оно рефлексивно, транзитивно и антисимметрично. Последнее свойство означает: .
Пример 5. Примеры отношений порядка:
– отношение « » на множестве действительных чисел. Отношение « » порядком не является, так как оно не рефлексивно;
– отношение « » на множестве подмножеств некоторого множества;
– на множестве двоичных слов длины можно ввести отношение порядка следующим образом. Пусть и – двоичные слова. Положим , если для , 1, 2, …, .
Пусть – отношение порядка на множестве . Элементы называются сравнимыми, если или , в противном случае – несравнимыми.
Порядок называется линейным, если любые два элемента сравнимы. В противном случае говорят о частичном порядке. Множество с заданным на нем порядком (частичным или линейным) называется упорядоченным (частично или линейно). Первое отношение в примере 5 задает линейный порядок, два других отношения порядка – частичные. Например, двоичные слова 011 и 110 несравнимы.
Элемент частично упорядоченного множества называется максимальным (минимальным), если из того, что следует . Элемент называется наибольшим (наименьшим), если ( ) для всех .
Верхней (нижней) гранью подмножества частично упорядоченного множества называется такой элемент , что
( ).
Точной в ерхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани обозначаются соответственно и .
Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.
Частично упорядоченное множество называется решёткой, или структурой, если для любых двух элементов существует точная нижняя и точная верхняя грани.
Пример 6. Примеры решёток:
– множество всех подмножеств данного множества, упорядоченное по включению;
– всякое линейно упорядоченное множество; причем, если , то .
|