Бинарные отношения
Рассмотрим важные логические понятия, связанные с отношениями, которые, в частности, используются в любой аксиоматике геометрии.
Прямое произведение множеств
Упорядоченной парой называется совокупность, состоящая из двух элементов и , взятых в определенном порядке: элемент считается в паре первым, а элемент — вторым. Две упорядоченные пары и называются равными тогда и только тогда, когда и .
Прямым (декартовым) произведением множеств и называется множество всех упорядоченных пар таких, что и . Прямое произведение обозначается , а в случае — просто , т.е. .
Аналогично определяются упорядоченные тройки, четверки и т.д., а также прямые произведения трех, четырех и т.д. множеств. Например, прямым произведением множеств действительных чисел называется множество всех упорядоченных наборов из действительных чисел .
Пример В.1. Для числовых множеств и найти: .
Решение. По определению находим:
Заметим,что .
Отношение эквивалентности
Бинарным отношением р на множестве называется подмножество этого множества упорядоченных пар . Если пара принадлежит отношению , то пишут или . Если , то отношение , т.е. подмножество множества , называют бинарным отношением на множестве .
Бинарное отношение на множестве называется:
— рефлексивным, если для любого ;
— симметричным, если для любых из следует, что ;
— транзитивным, если для любых из и следует, что .
Рефлексивное, симметричное и транзитивное отношение на множестве называется отношением эквивалентности на множестве и обозначается символом .
Пример В.2. Даны бинарные отношения:
а) отношение — " равен ") на множестве действительных чисел;
б) отношение — " меньше ") на множестве действительных чисел;
в) отношение — " не больше ") на множестве действительных чисел;
г) отношение — " брат ") на множестве людей;
д) отношение — "многоугольник подобен многоугольнику ") на множестве правильных многоугольников;
е) отношение на множестве целых чисел: "число сравнимо с числом по модулю ", т.е. остатки от деления чисел и на натуральное число равны.
Установить, являются ли заданные отношения рефлексивными, симметричными, транзитивными, отношениями эквивалентности.
Решение:
а) Так как для любого действительного числа , то отношение рефлексивное. Поскольку из следует, что , то отношение симметричное. Так как из равенств и следует, что , то отношение транзитивное. Таким образом, отношение равенства является отношением эквивалентности.
б) Отношение "меньше" не является рефлексивным (неравенство неверно) и симметричным (из не следует но является транзитивным (так как из неравенств и следует ). Это отношение не является отношением эквивалентности.
в) Отношение "не больше" является рефлексивным (неравенство справедливо для любых действительных чисел) и транзитивным (из неравенств и следует ), но не является симметричным (например, из не следует, что ). Это отношение не является отношением эквивалентности.
г) Отношение "братства" не является рефлексивным (любой человек не является братом для самого себя), симметричным (утверждение, если брат , то брат неверно, поскольку может оказаться сестрой для ), транзитивным (например, если для трех людей имеем и , то отсюда не следует, что , поскольку может оказаться сестрой для ). Это отношение не является отношением эквивалентности.
д) Каждый многоугольник подобен самому себе . Поэтому отношение подобия рефлексивное. Из подобия многоугольников следует, что , значит отношение симметричное. Так как из подобия многоугольников и следует, что , то отношение транзитивное. Таким образом, отношение подобия многоугольников является отношением эквивалентности.
е) Сравнение равносильно условию: разность делится на (без остатка). Так как число нуль делится без остатка на любое натуральное число , то , значит отношение рефлексивное. Если делится на , то и делится на , следовательно, отношение симметричное. Наконец, если числа и делятся на число , то и их сумма делится на , т.е. из и следует, что . Поэтому отношение транзитивное. Таким образом, отношение сравнения целых чисел по модулю является отношением эквивалентности.
Разбиение множества на классы эквивалентности
Говорят, что множество разбито на классы, если оно представлено тем или иным способом в виде объединения своих попарно непересекающихся подмножеств. Например, множество всех студентов вуза разбивается на учебные группы (а множество учеников школы разбивается на классы). Любое разбиение множества на классы определяет на отношение: — " находится в том же классе, что и ". Покажем, что это отношение, обозначенное символом , действительно является отношением эквивалентности. В самом деле, оно рефлексивное: , симметричное: (если находится в том же классе, что и , то и находится в том же классе, что и ), транзитивное (из и следует, что все три элемента принадлежат одному классу, тогда и ). Следовательно, рассматриваемое отношение является отношением эквивалентности.
Справедливо и обратное утверждение. Любое отношение эквивалентности , заданное на множестве X, позволяет разбить это множество на непустые классы.
Классом эквивалентности, порожденным элементом , называется подмножество множества , состоящее из тех элементов , для которых . Любой класс — непустое множество, так как, в силу рефлексивности , он содержит по крайней мере один элемент .
Таким образом, отношение эквивалентности на множестве определяет разбиение множества на непустые классы эквивалентности относительно этого отношения. Каждый класс эквивалентности однозначно определяется любым своим элементом. Совокупность классов эквивалентности называется фактор-множеством множества .
Например, отношение подобия (см. пункт "д" примера В.2) разбивает множество правильных многоугольников на классы эквивалентности: множество правильных треугольников, множество квадратов и т.д. Отношение сравнения целых чисел по модулю (см. пункт "е" примера В.2) разбивает множество целых чисел на классов эквивалентности, поскольку при делении на количество различных остатков равно .
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|