Множества
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.50 (1 Голос)

Отношения

Пусть заданы множества M1,M2,…,Mn. Тогда подмножество RÍM1´M2´…´Mn называется N-местным отношением на множествах M1,M2,…,Mn. Многоместные отношения используются, например, в теории баз данных. Поэтому и название «реляционная» база данных происходит от Relation (отношение). Говорят, что m1ÎM1, m2ÎM2,…, mnÎMn находятся в отношении R, если (m1,m2,…,mn)ÎR. Одноместное отношение R - просто подмножество M, т. е. . Такое отношение называется признаком: M обладает признаком R, если mÎM и RÍM. Свойства одноместных отношений это свойства подмножеств множества M.

Наиболее часто используются Бинарные отношения. Рассмотрим прямое произведение множеств A´B

.

Назовем бинарным отношением R из A в B множество пар (a, b), для которых высказывание, связывающее a и b, и определяющее отношение R истинно. В этом случае пишем aRb, (a, b)ÎR или <a, b>ÎR.

Областью определения бинарного отношения R называется множество

Область значений бинарного отношения R называется множество

.

Очевидно, что DRÍA и GRÍB.

Например, если A - множество жителей Украины, B - множество населенных пунктов Украины, отношение R можно задать высказыванием “быть жителем”, которое определяет пары (a, b)ÎR, aÎA, bÎB такие, что высказывание “ живет в населенном пункте ” является истинным.

Рассмотрим множества A={1,2,3}, B={3,4,5,6}и определим отношение R следующим образом:

AÎA, BÎB, ARb ÛA+B<7.

Соответствующее отношению множество RÌA´B имеет состав:

R={(1,3),(1,4),(1,5),(2,3),(2,4),(3,3)}.

Графическое представление бинарного отношения на конечных множествах можно осуществить с помощью графа или таблицы. Для демонстрации последнего примера на рис.1.23.представлен граф отношения, в котором участвующие в R пары указанны дугами. Таблица отношения имеет два входа, и элементы отношения выделяются единицами (табл. 1.1). Таким образом, бинарное отношение R на конечных множествах A={a1,…,am}, B={b1,…,bn} может быть задано матрицей C=êêсij çç размером m´n, в которой:

Рис.1.23. Граф отношения, где дуга есть в графе, если

и отсутствует, если

Табл. 1.1 Таблица отношения


3

4

5

6

1

1

1

1

 

2

1

1

   

3

1

     
Отметим, что пустое множество ÆÌA´B определяет особое отношение, называемое Пустым и которому не соответствует ни одна из пар (A, b)ÎA´B. В противовес можно говорить и об отношении R=A´B, которое содержит любую пару (A, b),AÎA, BÎB.

Если задано отношение RÍA´B, то для любого A1ÌA определяется отношение R1, называемое Сужением R на A1, которое получается из R удалением всех пар, содержащих элементы, на принадлежащие M1, те R1=RÇ(A1´B)

Так как отношение R задается на множестве A´B и RÍA´B, т. е. R есть подмножество, то для него обычным образом определены теоретико-множественные операции объединения, пересечения и т. д. Например, отношение £ является объединением отношений < и = .

Если определено отношение R из A в B, то Обратное отношение из B в A, обозначаемое , определяется тождеством

BAÛaRb, aÎA, bÎB,

Или

={(b, a)êaRb}.

Пример 1.10.

А) Если aRb означает “a является родителем b”, то обратное отношение bA означает, что b имеет родителем a;

Б) если XRY, где X и Y-множества и отношение заданно выражением XÍY, то обратное отношение YX задается выражением YX;

В) Для отношения > обратным является < .

По определению , что вполне очевидно.

Так как отношения являются по своей сути соответствиями, то для них определены операции Композиции отношений. Например, если заданы отношения

,

,

То композицией отношений, обозначаемой , называется отношение

,

Если R1=R2, то можно писать .

Пример 1.11. Рассмотрим множества A={3,4.5}, B={2,3,4}, C={5,6,7,8} и отношение

,

и B является делителем C}.

Композицию отношений изобразим графом (рис.1.24). Из него видно, что R={(3,6),(3,8),(4,6),(4,8)},где в каждой паре (A,C) для элемента A Найдется элемент B, такой, что он является делителем c.

Важным типом бинарных отношений являются те, в которых исходное множество A и конечное B совпадают, т. е. A=B. Тогда говорят об отношении из A в A или просто бинарным отношением R на A:

RÛ((a, b)êa, bÎA, aRb}.

Используя такие отношения, можно задать, например, действительную функцию f:

Которая в обычной записи имеет вид Y = X+X+1.

Рис.1.24. Композиция отношений

Для отношения R на A: , кроме обратного отношения можно ввести следующие понятия:

–  Дополнение отношения ;

–  Тождественное отношение ;

–  Универсальное отношение .

A)  Если R – отношение на множестве А, то степенью отношения R на А называется его n-композиция с самим собой

,

Отметим, что,, … , .

Теорема 1.1. Если некоторая пара (a, b), принадлежащая какой-либо степени отношения R на множестве А таком, что , то эта пара принадлежит и степени R не выше n-1 :

Доказательство. Для запишем и . Тогда , где K изменяется до .

Как следствие, можем записать

и .

Если – отношение из в , то называется Ядром отношения. Ядро отношения из в является отношением на .

Пример 1.20.

Пусть задано множество . Рассмотрим отношение из булеана в множестве целых чисел . Тогда , где . Ядро отношения будет являться отношением равномощности.

Для бинарных отношений R на множестве A можно отметить ряд возможных их свойств:

А) рефлективность, которая означает, что:

"aÎA®aRa; (1.58)

Б) антирефлексивность, которая требует, чтобы

"aÎAÞ(a, a)ÏR; (1.59)

В) симметричность, означающая, что

("(a, b)ÎêaRb)ÞbRa; (1.60)

Г) антисимметричность

("a, bÎAêaRb и bRa)Þa=b (1.61)

Д) транзитивность, определяемая так:

("a, b,cÎAêaRb и bRc)ÞaRc. (1.62)

Е) полнота Или Линейность

или (1.63)

Относительно свойств отношений справедлива

Теорема 1.2. Пусть – отношение на . Тогда

А) рефлексивно ;

Б) симметрично ;

В) транзитивно ;

Г) антисимметрично ;

Д) антирефлексивно ;

Е) полно .

Доказательство. Из определения свойств отношений имеем:

А. Прямо: .

Обратно: .

Б. Прямо:

Обратно:

.

В. Прямо:

& .

B) Обратно:

.

Г. Прямо: от противного. .

Обратно:

Д. Прямо: от противного.

.

Обратно: .

е. Прямо:

C) Обратно:

Для примера рассмотрим отношение Í для множества P(A), являющегося множеством всех подмножеств множества A:

"XÎP(A)ÞXÍX, следовательно, данное отношение рефлексивно;

("X, YÎP(A)êXÍY и YÍX)ÞX=Y, следовательно, отношение антисимметрично;

("X, Y,ZÎP(A)êXÍY и YÍZ)ÞXÍZ, т. е. отношение является транзитивным.

Другим примером отношения, заданного на множестве людей является “быть ребенком”. Таким образом, ARb означает, что “а является ребенком В”. Тогда очевидно, для "AÎA,(a, a)ÏR, т. е. отношение антирефлексивно. Поскольку ни условие в), ни условие г) не выполняются, но из (a, b)ÎRÞ(b, a)ÏR следует свойство, которое иногда называют несимметричностью. Анализируя транзитивность, заметим, что

"A,B,CÎA,(A,B)ÎR И (B,C)ÎRÞ(A,C)ÏR,

А следовательно отношение R не транзитивно.

Используя свойства отношений, выделим некоторые их виды.

Рефлексивное, симметричное и транзитивное отношение R на множестве A называется Отношением эквивалентности на A, то есть:

Таковыми являются отношения равенства на множестве целых чисел, подобия геометрических фигур. Однако на множестве прямых на плоскости отношение “перпендикулярна к” не является отношением эквивалентности.

Если на А задано отношение эквивалентности , то, выбрав любой элемент ÎA, построим подмножество из элементов ,,…, таких, что Подмножество называется Классом эквивалентности, порожденным элементом , и обозначается зачастую ([]=Ci) или в общем случае обозначаем класс, порожденный элементом :

[a]={bêbÎA и aRb}

Очевидно, что, если A, bÎA И aRbÞ[A]=[B].

Разбиением множества A по отношению R называется множество попарно непересекающихся подмножеств А таких, что каждый элемент множества А принадлежит одному и только одному из этих подмножеств.

Очевидно, что для разбиения характерны свойства:

1.

2.

3.

4.

5.

Построенное разбиение называется системой Классов эквивалентности по отношению R. Мощность системы разбиения называется Индексом системы. Например, для множества натуральных чисел N определим отношение эквивалентности:

имеют ту же четность, что и .

Очевидно, что возможно набрать два класса на заданном R:

(четные числа)={2,4,6,…}=A1,

(нечетные числа)={1,3,5,…}=A2,

Причем

Теорема 1.3 Любое разбиение множества А является характеристическим свойством отношения эквивалентности, определенном на А.

Доказательство. Пусть семейство множеств Ai является разбиением, тогда определим отношение R на A:

"XÎA И "YÎAêXRyÛ$AiÎP(A)êXÎAi И yÎAi.

Из последнего следует, что отношение R является отношением эквивалентности, так как оно:

1. Рефлексивно: .

2.Симметрично:

.

3.Транзитивно:

.

Точно также, каждое отношение эквивалентности R задает разбиение множества А. Чтобы выразить тот факт, что пара (X, y) находится в отношении эквивалентности R, используется такая запись

Xºy(modR),

Которая читается как ”X эквивалентно Y по модулю R”, а классы эквивалентности, определяемые отношением R, называется классами по модулю R.

Другое важное для нас отношение на множестве А, обладающее свойствами рефлексивности, антисимметричности и транзитивности, называется Отношением порядка, т. е.:

Множество А, на котором задано отношение порядка, называется Упорядоченным множеством.

Например, на множестве действительных чисел отношения £ “меньше чем или равно” является отношением порядка, т. к. оно обладает требуемыми свойствами:

X £ x;

X £ y И y £ xÞX=y;

X £ y И y £ zÞX £ z.

На множестве P(A) подмножеств А отношение включения Í тоже является отношением порядка:

AÍA;

AÍB и BÍAÞA=B;

AÍB и BÍCÞAÍC.

Отношение порядка R между элементами множества А является Отношение полного порядка, если:

"(x, y)Î ÞXRy или YRx.

В противном случае отношение называется отношением Частичного порядка. Например, схема организации подчинения в учреждении является отношением частичного порядка.

Отношение порядка, обладающее свойствами антирефлексивности, антисимметричности и транзитивности, называется отношением Строгого порядка, т. е.

Примером такого отношения на множестве действительных чисел является отношение < “меньше чем”.

Отношение порядка R на множестве А, для которого любые два элемента «сравнимы», т. е.:

"X, yÎAÞXRy Или yRx.

Называют также отношением Линейного порядка.

Если на множестве А задано отношение порядка R, то на множестве =A´A определим отношение порядка П условием

(x, y)П(U,N)ê(x, y)Î , (U,N)Î ÛXRU и yRN.

Отношение П является отношением порядка и называется Отношением Парето.

Множество А с заданным на ней отношением линейного порядка называется Линейно упорядоченным.

Рассмотрим непустое конечное множество А, на котором задано отношение частичного порядка, которое запишем как . Будем писать , если и . Говорят, что элемент Y покрывает элемент , если и не существует такого элемента u, что . Тогда равносильно тому, что , где покрывает .

Любое частично упорядоченное множество может быть представлено в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если Y покрывает X, то точки X и Y соединяются отрезком, причем точку, соответствующую X, располагают ниже Y. Такие схемы называются Диаграммами Хассе. На рис.1.25 показаны диаграммы Хассе, причем вторая соответствует линейно упорядоченному множеству.

а б

Рис.1.25. Диаграммы Хассе

Пример 1.13. Рассмотрим три отношении порядка и построим для них диаграммы Хассе:

1. Пусть A={1,2,3}. На множестве P(A) рассмотрим отношение Í “быть подмножеством”. Тогда P(A)={Æ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. Диаграмма отношения изображена на рис 1.26а.

2. Пусть X={1,2,3,5,6,10,15,30}. На множестве X рассмотрим отношение порядка « делится на x». Диаграмма Хассе для этого отношения представлена на рис.1.26б.

3. На множестве Y={1,2,3,4,5,6,7,8} рассмотрим отношение линейного порядка £. Его диаграмма представлена на рис.1.26в.

Рис.1.26 Диаграммы Хассе

Отметим, что диаграммы первых двух отношений совпадают. Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, отличную от линейного упорядоченного множества для третьего отношения.

Более точно общность структуры определяется понятием изоморфизма. Два частично упорядоченных множества X и Y называется Изоморфными, если существует биекция j:X®Y, сохраняющая отношение частичного порядка. Т. е. x1 X2, тогда и только тогда, когда j(x1)J(x2), где и - отношения порядка, заданные на X и на Y соответственно.

Всякое частично упорядоченное множество X изоморфно некоторой системе подмножеств множества X, частично упорядоченной отношением включения.

Действительно для "AÎX рассмотрим . Тогда и - совокупность всех таких подмножеств. Докажем, что эта система подмножеств, упорядоченная отношением включения, изоморфна X.

Рассмотрим отображение такое, что . Тогда j-биекция. Действительно, если , то, поскольку в силу рефлексивности £ , имеем и . Аналогично получаем , и в силу антисимметричности £ имеем , т. е. отображение j инъективно. Кроме того, j сюръективно, так как у любого подмножества есть прообраз . Докажем, что отображение сохраняет отношение порядка. Пусть . Тогда из в силу транзитивности отношения £ следует , а значит, и . Если , то, поскольку , имеем , откуда .

Отношения множеств - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить