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

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

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

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

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


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

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


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


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


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


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


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




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


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


[math]\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}[/math]

Заметим,что [math]X \times Y \ne Y \times X[/math].




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


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


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


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


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


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


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




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


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


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


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


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


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


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


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


Решение:


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


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


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


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


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


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




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


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


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


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


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


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


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


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

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