Раздел 2. Отношения и функции

Раздел 2. Отношения и функции

Определение 2.1: Любое подмножество r прямого произведения A1´A2´....´An называется n-местным (n-арным) отношением, определенным на множествах A1, A2, .... An.

rÍ A1 ´A2 ´...´An.

Отношения принято обозначать малыми буквами греческого алфавита a, b, g, ...r, s, t.

Определение 2.2: Любое подмножество a прямого произведения aÍ A1 ´ A2 называется бинарным отношением, определенным на множествах A1 и A2.

Определение 2.3: Для любого множества A определим тождественное отношение tA и универсальное отношение xA следующим образом:

tA = {(a, a) | " a ÎA} xA = {(a, b) | " aÎA, bÎA}

Т. к. Æ Í A2, то Æ является отношением на A и называется пустым отношением.

Определение 2.4: Свяжем с каждым бинарным отношением r, определенным на множествах A и B, r Í A´ B, два множества - область определения D(r) и область значений R(r). Они определяются следующим образом.

D(r) = {x| (x, y)Îr}

R(r) = {у| (x, y) Îr}

Пример : A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

r = {(x, y) | x, yÎA, х - делитель y, x £ 5}.

Тогда: D(r) = {1, 2, 3, 4, 5} R( r ) = A

Определение 2.5: Пусть r - бинарное отношение. Определим обратное отношение r-1 cледующим образом r-1= {(x, y) | (y, x) Îr}.

Определение 2.6: Пусть r - бинарное отношение на множестве A. Тогда:

а) r - рефлексивно, если (х, х) Î r для " х Î A (главная диагональ матрицы содержит только единицы)

б) r - антирефлексивно, если (х, х) Ïr " х Î A

(главная диагональ матрицы содержит только нули)

в) r - симметрично, если из того, что (х, y) Î r следует, что (y, x) Î r " х, y Î A

( r = r-1 матрица отношения симметрична относительно главной диагонали)

г) r - антисимметрично, если из того, что (х, y) Î r и (y, x) Î r следует, что x = y " х, y Î A

Замечание: Отношение r антисимметрично тогда и только тогда, когда для любых " х, y Î A

( (x, y) Î r и x¹y ) Þ (x, y)Ïr.

д) r - транзитивно, если из того, что

(х, y) Î r и (y, z) Î r следует, что (х, z) Î r " х, y, z Î A

Замечание: Антисимметричность есть следствие антирефлексивности и транзитивности.

Пример: r = {(x, y) | x, y Î N и yx т. е. x - делитель y}

а) рефлексивно, т. к. х х " х ÎN

б) несимметрично, т. к. 2 - делитель 4 по 4 не является делителем 2.

в) транзитивно, т. к., если y x и z y, то z x

г) антисимметрично, т. к. если x y и y x, то x = y.

Пусть A¹Æ, A2 = A ´ A и a, b, g, Í A2 - некоторые бинарные отношения, определенные на множестве A . A2 = A ´ A = {(x, y)| x, y ÎA}.

Операции над бинарными отношениями:

1)  aÈb={(x, y)|(x, y)Îa или (x, y)Îb}

2)  aÇb={(x, y)|(x, y)Îa и (x, y)Îb}

3)  a\b={(x, y)|(x, y)Îa и (x, y)Ïb}

4)  a¢={(x, y)|(x, y)Ï a и (x, y)ÎA2}

5)  a-1={(x, y)|(y, x)Î a}

6)  ab={(x, y)|$zÎA,(x, z)Îa и(z, y)Îb}- произведение отношений a и b

Относительно введенных операций имеют место следующие свойства:

1)  aÇa=aÈa=a

2)  a(bg)=(ab)g

3)  a(bÇg)=abÇag (bÇg)a=baÇga

4)  a(bÈg)=abÈag (bÈg)a=baÈga

5)  (a-1)-1=a

6)  (aÈb)-1=a-1Èb-1 (aÇb)-1=a-1Çb-1

7)  (ab)-1=b-1a-1

8)  (a¢) -1=(a-1)¢

Определение 2.7: Пусть A - непустое множество и {Ai} - cовокупность подмножеств Ai (i=1, 2, ..., n, n Î N) таких, что Ai Í A, . Совокупность таких подмножеств называется покрытием A.

Определение 2.8: Пусть A - непустое множество и {Ai} - cовокупность подмножеств Ai (i=1, 2, ..., n, n Î N) таких, что Ai Í A, и . Совокупность таких подмножеств называется разбиением множества A.

Определение 2.9: Бинарное отношение на множестве А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Определение 2.10: Пусть r-отношение эквивалентности на множестве A. Определим класс эквивалентности [x] для хÎA

[x]={y|(х, y)Îr}, такой что

1) любые 2 элемента одного и того же класса эквивалентны друг другу

2)никакие два элемента разных классов не эквивалентны между собой.

Определение 2.11: Бинарное отношение a, определенное на множестве A, называется отношением предпорядка, если оно рефлексивно и транзитивно.

Определение 2.12: Бинарное отношение a, определенное на множестве A, называется отношением порядка, если оно транзитивно и антисимметрично.

Определение 2.13: Отношение порядка a, определенное на множестве A, называется строгим, если a антирефлекcивно.

Определение 2.14: Отношение порядка a, определенное на множестве A, называется нестрогим (частичным) если a рефлекcивно.

Определение 2.15: Элементы x и y сравнимы по отношению порядка a, если выполняется (x, y)Îa или (y, x) Îa. В противном случае элементы x и y не сравнимы.

Определение 2.16: Множество A, на котором задано отношение порядка, называется полностью упорядоченным, если любые два элемента x, yÎA сравнимы, и частично упорядоченным в противном случае.

Определение 2.17: Частичный порядок на множестве A называется линейным, если любые два элемента из множества сравнимы:

"x, y Î A, x £ y или y £ x

Определение 2.18: Множество A с заданным на нем частичным или линейным порядком называется частично или линейно упорядоченным.

Определение 2.19: Пусть заданы множества A, B, С и отношения s между A и B и r между B и С. Определим отношение между A и С следующим образом, оно действует из A в B посредством s, а затем из B в С посредством r. Такое отношение называют составным и обозначают rs, т. е. (rs)(а)= r (s(а))

Следовательно, rs ={(x, y) | $ zÎB такой, что (x, z)Îs и (z, y)Îr}.

Практические задания

2.1. Найдите и при:

1) A={1,2}, В={1,3,4};

2) A={3}, B={1,2,3,4}.

2.2. Изобразите на декартовой плоскости следующие мно­жества:

1) 

2) 

3) 

4) 

5) 

6) 

7) 

8) 

2.3. Докажите, что при любых множествах X, Y, Z:

1)

2)

3)

4)

5)

6)

7)

2.4. Докажите, что для любых множеств А, В, С, D

Справедливо ли аналогичное равенство для объединения множеств?

2.5. Докажите, что для любых отношений и между эле­ментами множеств X и Y:

1)

2)

3)

4)

5)

2.6. Докажите, что:

1) отношение рефлексивно ;

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

3) отношение симметрично ,

4) отношение антисимметрично (- тождественное отношение).

2.7. Укажите, какими свойствами (рефлексивностью, анти­рефлексивностью, симметричностью, антисимметричностью, транзитивностью) обладает каждое из следующих отношений:

1) «||» на множестве прямых плоскости;

2) «^» на множестве прямых плоскости;

3) «=» на множестве R;

4) «<» на множестве R;

5) «» на множестве R;

6) «Пересечения» на множестве прямых плоскости;

7) «Подобия» на множестве треугольников плоскости;

8) «» на семействе подмножеств универсального мно­жества.

9) «» на семействе подмножеств универсального мно­жества;

2.8. Найдите область определения и область значений каждого из следующих отношений, заданных на множестве Х={1,2,...,10}, и укажите, какими свойствами (рефлексивностью, антирефлексивностью, симметричностью, антисиммет­ричностью, транзитивностью) оно обладает:

1)

2)

3)

4)

2.9. На множестве N для каждого из следующих отноше­ний найдите область определения и область значений и укажите, какими свойствами (рефлексивностью, антирефлек­сивностью, симметричностью, антисимметричностью, транзитив­ностью) оно обладает:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

2.10. Найдите область определения и область значений каждого из следующих отношений, заданных на множестве R, и укажите, какими свойствами (рефлексивностью, антиреф­лексивностью, симметричностью, антисимметричностью, транзи­тивностью) оно обладает:

1)

2)

3)

4)

5)

2.11. Что можно сказать об отношениях и , если : 1) рефлексивно; 2) антирефлексивно; 3) симметрично; 4) антисимметрично; 5) транзитивно?

2.12. Докажите, что объединение и пересечение двух рефлексивных отношений рефлексивно. Докажите или опровергните аналогичные утверждения для пар антирефлексивных, симметричных, антисимметричных, транзитивных отношений.

2.13. Докажите, что при любом отношении на множестве X отношения и симметричны.

2.14. Докажите, что отношение включения является отноше­нием порядка.

2.15. Можно ли сказать, что множество N разбито на классы семейством подмножеств {К, L}, если:

1)  K - множество четных чисел, L - множество нечетных чисел;

2)  K - множество простых чисел, L - множество составных
чисел?

2.16. Пусть А={1, 2, 3, 4, 5, 6}. Покажите, что подмножества A1={1, 2}, A2={3}, A3={4, 5, 6} образуют разбиение А. Запи­шите множество пар из принадлежащих соответствующе­му отношению эквивалентности.

2.17. Пусть и - отношения эквивалентности на множе­стве X. Докажите или опровергните, что , являются отношениями эквивалентности. Решите аналогичную задачу, когда и - отношения порядка.

2.18. Докажите, что если - рефлексивное и транзитивное отношение на множестве X, то - отношение эквивалент­ности.

2.19. Определите, какие из следующих отношений являются отображениями; какие из отображений взаимно-однозначны, ка­кие - обратимы:

1)  1)

2) 

3) 

4) 

5) 

6) 

7) 

8) 

9) 

10) 

11) 

12) 

13) 

14) 

2.20. Пусть f - отображение X в У. Докажите, что - отображение У в X тогда и только тогда, когда f - взаимно-од­нозначное отображение X на Y. При этом - взаимно-одно­значное отображение У на X.

2.21. Пусть f - отображение X на У. Докажите, что следую­щие утверждения эквивалентны:

1)

2)

3) для любых отображений и

2.22. Докажите, что если f - взаимно-однозначное отобра­жение X на Y, a g - взаимно-однозначное отображение У на Z, то:

1) - взаимно-однозначное отображение X на Z;

2) .

2.23. Пусть f - преобразование конечного множества X. Докажите, что следующие утверждения эквивалентны:

1) отображение f взаимно-однозначно;

2) f - отображение X на X.

2.24. Пусть - отношения на множестве N. Найдите если:

1)

2)

3)

2.25. Докажите, что отношение транзитивно тогда и только тогда, когда .

2.26. Пусть и - отношения. Докажите, что .

2.27. Пусть и - отношения эквивалентности. Докажите, что - отношение эквивалентности тогда и только тогда, когда .

2.28. Пусть - отношение на множестве X. Докажите, что отношение симметрично.

2.29. Пусть - отношения линейного порядка на мно­жестве X. Докажите, что - отношение линейного порядка тогда и только тогда, когда .

2.30. Пусть - симметричные отношения на множестве X. Докажите, что .