Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Теория множеств: отношения на множестве, отношения порядка и эквивалентности

На главную Математический раздел Криптография и т.д. Новости

Что такое декартово произведение и отношения на множестве

Декартово произведение A x B множеств A и B - множество всевозможных пар вида (a, b), где a - элемент множества A, b - элемент множества B. В отличие от обычного произведения, перестановка "множителей" меняет результат. Заметим, что декартово произведение множества самого на себя - допустимая операция.

Пример декартова произведения. A = {-1, 1}, B = {0, 2}. A x B = {(-1, 0), (-1, 2), (1, 0), (1, 2)}.

Пусть |X| - количество элементов множества X. Тогда |A x B| = |A|*|B|.

Любое подмножество R декартова произведения A x A называется отношением на множестве A. Если некоторые элементы y, z из A находятся в отношении R, это обозначают как yRz. Небольшой пример. Пусть есть молодёжная компания K = {Вася, Маша, Катя, Лиза, Петя}. Допустим, R - отношение "живущие по одной улице". Маша и Катя живут по улице Дубовой, Лиза и Петя - по улице Липовой, Вася - по улице Кустарной. Тогда R = {(Маша, Катя), (Катя, Маша), (Лиза, Петя), (Петя, Лиза)}.

Простейшие виды отношений

Отношение R на множестве A рефлексивно, если любой элемент этого множества находится в отношении R с самим собой. Пример: A - числовое множество, R - отношение равенства. Ведь никто же не усомнится, что 1=1)))

Отношение антирефлексивно, если никакой элемент множества A не находится в этом отношении сам с собой. Яркий пример - неравенства < и > (то есть строгие неравенства). Другой пример: A - множество команд футбольной лиги, R - отношение "играть в одном матче в 1-ом туре". Ну не будет же никакая команда играть сама с собой? Как это - "команда играет с собой же"? Это типа её основной состав против дубля что ли?

Отношение симметрично, если всегда верно yRz => zRy, где y, z - элементы множества A. Пример про футбол из предыдущего абзаца подойдёт))) Ведь если ЦСКА играет матч с "Динамо", то "Динамо" же играет с ЦСКА)))

Если yRz и zRy возможно одновременно только при y=z, то отношение антисимметрично. Яркий пример - нестрогие неравенства для чисел ("больше или равно", "меньше или равно").

Отношение R асимметрично, если yRz и zRy вообще не может быть одновременно. Пример: A - множество граждан России, xRy - если y - жена x. Адекватный человек вряд ли здесь найдёт случаи симметрии)))

Если при yRz и zRt всегда верно, что yRt, то отношение транзитивно. Пример - всё те же числовые неравенства. Скажем, если y > z, z > t, то по-любому y > t. Другой яркий пример - параллельность прямых: если первая прямая параллельна второй, а вторая - третьей, то первая прямая параллельна третьей.

Отношение называется связным, если для любых несовпадающих элементов y, z yRz или zRy (допускается выполнение как одного, так и двух условий сразу). То есть любая пара элементов множества A содержит сравнимые элементы. Пример связного отношения следующий. A - множество команд футбольной лиги. Окончился очередной чемпионат, команды выстроились в итоговой турнирной таблице. Отношение yRz: команда y набрала не меньше очков, чем команда z. Если две команды набрали разное число очков, то отношение между ними выполняется в одну сторону, если одинаковое - и вовсе в обе (в последнем случае места в таблице определяются по дополнительным правилам). А теперь коварный второй пример, на этот раз отношение будет не связным. yRz: команда y набрала больше очков, чем команда z. Если две команды набрали очков одинаково, то отношения между ними нет.

Отношения эквивалентности и отношения порядка

Если отношение R на множестве A рефлексивно, симметрично и транзитивно одновременно, то это отношение эквивалентности. Пример отношения эквивалентности. A = {15, 319, 25, 29, 935, 939}. R - отношение "оканчиваться на одну цифру".

Ключевое свойство отношения эквивалентности: множество A разбивается на непересекающиеся классы эквивалентности, элементы внутри такого класса эквивалентны друг друга с точки зрения рассматриваемого отношения. Для примера выше - множество делится на классы {15, 25, 935} и {319, 29, 939}. Как видим, никакой элемент A не попадает одновременно в несколько классов.

Если отношение одновременно рефлексивно, антисимметрично, транзитивно, то оно является отношением нестрогого порядка. Пример - опять те же нестрогие неравенства, например, "больше или равно".

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

Заметим, что отдельно взятая пара элементов множества A, где введено отношение порядка R, может и не находиться в отношении порядка. Скажем, на множестве сотрудников организации введено отношение "быть начальником", причём управление устроено иерархически.

Пример по рисунку: t - начальник для z, а вот y и z вообще не состоят в отношении "начальник-подчинённый": может, статус y выше, но он в другом подразделении.

Если на множестве введено отношение порядка, это множество является упорядоченным. Если при этом нет пар элементов, не состоящих в отношении порядка, множество называется вполне упорядоченным, иначе частично упорядоченным.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X