Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Бинарные отношения

Бинарные отношения


Рассмотрим важные логические понятия, связанные с отношениями, которые, в частности, используются в любой аксиоматике геометрии.


Прямое произведение множеств


Упорядоченной парой \langle{x,y}\rangle называется совокупность, состоящая из двух элементов x и y, взятых в определенном порядке: элемент x считается в паре первым, а элемент y — вторым. Две упорядоченные пары \langle{x_1,y_1}\rangle и \langle{x_2,y_2}\rangle называются равными тогда и только тогда, когда x_1=x_2 и y_1=y_2.


Прямым (декартовым) произведением множеств X и Y называется множество всех упорядоченных пар \langle{x,y}\rangle таких, что x\in X и y\in Y. Прямое произведение обозначается X\times Y, а в случае Y=X — просто X^2, т.е. X\times X=X^2.


Аналогично определяются упорядоченные тройки, четверки и т.д., а также прямые произведения трех, четырех и т.д. множеств. Например, прямым произведением \overbrace{\mathbb{R}\times \mathbb{R}\times \cdots\times \mathbb{R}}^{n}=\mathbb{R}^n множеств \mathbb{R} действительных чисел называется множество всех упорядоченных наборов \langle x_1,x_2,\ldots,x_n \rangle из n действительных чисел x_1,x_2,\ldots,x_n.




Пример В.1. Для числовых множеств X=\{1;2\} и Y=\{3;4\} найти: X\times Y,~Y\times X,~X^2,~Y^2.


Решение. По определению находим:


\begin{aligned}X\times Y&=\{\langle 1;3 \rangle,\langle 1;4 \rangle,\langle 2;3 \rangle,\langle 2;4 \rangle \}\\[3pt]Y\times X&=\{\langle 3;1 \rangle,\langle 3;2 \rangle,\langle 4;1 \rangle,\langle 4;2 \rangle \}\\[3pt]X^2=X\times X&=\{\langle 1;1 \rangle,\langle 1;2 \rangle,\langle 2;1 \rangle,\langle 2;2 \rangle \}\\[3pt]Y^2=Y\times Y&=\{\langle 3;3 \rangle,\langle 3;4 \rangle,\langle 4;3 \rangle,\langle 4;4 \rangle \}\\[3pt]\end{aligned}

Заметим,что X \times Y \ne Y \times X.




Отношение эквивалентности


Бинарным отношением р на множестве X \times Y называется подмножество \rho этого множества упорядоченных пар \langle x,y \rangle,~x \in X,~y \in Y. Если пара \langle x,y \rangle принадлежит отношению \rho, то пишут \langle x,y \rangle \in \rho или x\,\rho\,y. Если Y=X , то отношение \rho, т.е. подмножество множества X^2, называют бинарным отношением на множестве X.


Бинарное отношение \rho на множестве X называется:


— рефлексивным, если x\,\rho\,x для любого x \in X ;


— симметричным, если для любых x,y \in X из x\,\rho\,y следует, что y\,\rho\,x;


— транзитивным, если для любых x,y,z \in X из x\,\rho\,y и y\,\rho\,z следует, что x\,\rho\,z.


Рефлексивное, симметричное и транзитивное отношение на множестве X называется отношением эквивалентности на множестве X и обозначается символом \sim.




Пример В.2. Даны бинарные отношения:


а) отношение =~(x=y — "x равен y") на множестве действительных чисел;


б) отношение <~(x<y — "x меньше y") на множестве действительных чисел;


в) отношение \leqslant~(x \leqslant y — "x не больше y") на множестве действительных чисел;


г) отношение \mathbf{B}~(x\mathbf{B}y — "x брат y") на множестве людей;


д) отношение \sim~(M \sim N — "многоугольник M подобен многоугольнику N") на множестве правильных многоугольников;


е) отношение m=n\pmod{p}на множестве целых чисел: "число m сравнимо с числом n по модулю p", т.е. остатки от деления чисел m и n на натуральное число p равны.


Установить, являются ли заданные отношения рефлексивными, симметричными, транзитивными, отношениями эквивалентности.


Решение:


а) Так как x=x для любого действительного числа x, то отношение = рефлексивное. Поскольку из x=y следует, что y=x, то отношение симметричное. Так как из равенств x=y и y=z следует, что x=z, то отношение транзитивное. Таким образом, отношение равенства является отношением эквивалентности.


б) Отношение "меньше" не является рефлексивным (неравенство x<x неверно) и симметричным (из x<y не следует y<x но является транзитивным (так как из неравенств x<y и y<z следует x<z). Это отношение не является отношением эквивалентности.


в) Отношение "не больше" является рефлексивным (неравенство x \leqslant x справедливо для любых действительных чисел) и транзитивным (из неравенств x \leqslant y и y \leqslant z следует x \leqslant z), но не является симметричным (например, из 1\leqslant 2 не следует, что 2\leqslant 1). Это отношение не является отношением эквивалентности.


г) Отношение "братства" не является рефлексивным (любой человек не является братом для самого себя), симметричным (утверждение, если x брат y~(x\mathbf{B}y), то y брат x~(x\mathbf{B}y) неверно, поскольку y может оказаться сестрой для x), транзитивным (например, если для трех людей x,y,z имеем x\mathbf{B}y и y\mathbf{B}z, то отсюда не следует, что x\mathbf{B}z, поскольку z может оказаться сестрой для x). Это отношение не является отношением эквивалентности.


д) Каждый многоугольник подобен самому себе M \sim M. Поэтому отношение подобия рефлексивное. Из подобия многоугольников M \sim N следует, что N \sim M, значит отношение симметричное. Так как из подобия многоугольников M \sim N и N \sim K следует, что M \sim K, то отношение транзитивное. Таким образом, отношение подобия многоугольников является отношением эквивалентности.


е) Сравнение m=n\pmod{p} равносильно условию: разность m-n делится на p (без остатка). Так как число нуль m-m=0 делится без остатка на любое натуральное число p, то m=m\pmod{p}, значит отношение рефлексивное. Если m-n делится на p, то и n-m делится на p, следовательно, отношение симметричное. Наконец, если числа m-n и n-k делятся на число p, то и их сумма (m-n)+(n-k)=m-k делится на p, т.е. из m=n\pmod{p} и n=k\pmod{p} следует, что m=k\pmod{p}. Поэтому отношение транзитивное. Таким образом, отношение сравнения целых чисел по модулю p является отношением эквивалентности.




Разбиение множества на классы эквивалентности


Говорят, что множество X разбито на классы, если оно представлено тем или иным способом в виде объединения своих попарно непересекающихся подмножеств. Например, множество всех студентов вуза разбивается на учебные группы (а множество учеников школы разбивается на классы). Любое разбиение множества X на классы определяет на X отношение: x \sim y — "x находится в том же классе, что и y". Покажем, что это отношение, обозначенное символом \sim, действительно является отношением эквивалентности. В самом деле, оно рефлексивное: x \sim x, симметричное: x \sim y \Rightarrow y \sim x (если x находится в том же классе, что и y, то и y находится в том же классе, что и x), транзитивное (из x \sim y и y \sim z следует, что все три элемента x,y,z принадлежат одному классу, тогда и x\sim z). Следовательно, рассматриваемое отношение является отношением эквивалентности.


Справедливо и обратное утверждение. Любое отношение эквивалентности \sim, заданное на множестве X, позволяет разбить это множество на непустые классы.


Классом эквивалентности, порожденным элементом x, называется подмножество K_x множества X, состоящее из тех элементов y \in X, для которых x \sim y. Любой класс K_x — непустое множество, так как, в силу рефлексивности x \sim x, он содержит по крайней мере один элемент x.


Таким образом, отношение эквивалентности на множестве X определяет разбиение множества X на непустые классы эквивалентности относительно этого отношения. Каждый класс эквивалентности однозначно определяется любым своим элементом. Совокупность классов эквивалентности называется фактор-множеством множества X.


Например, отношение подобия (см. пункт "д" примера В.2) разбивает множество правильных многоугольников на классы эквивалентности: множество правильных треугольников, множество квадратов и т.д. Отношение сравнения целых чисел по модулю p (см. пункт "е" примера В.2) разбивает множество целых чисел на p классов эквивалентности, поскольку при делении на p количество различных остатков (0;1;\ldots;p-1) равно p.

Перейти на форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved