Отношения и функции

Найти dom r, rang r, r^-1, r · r, r · r^-1, r^-1 · r для отношений:

1.1. r = {(x, y) | x, y ÎN и x делит y};

1.2. r={(x, y)|х,у ÎN и у делит х};

1.3. r={(x, y)|х,у ÎR и х+у £ 0};

1.4. r={(x, y) | х,у ÎR и 2х ³ зу};

1.5. r={(x, y)| х,у Î[-p/2, p/2] и у ³ sin x}.

2. Доказать, что для любых бинарных отношений справедливы утверждения:

2.1. dom r= Æ Û r= Æ Û rang r = Æ;

2.2. dom r^-1 = rang r, rang r^-1=dom r;

2.3. dom (r₁ · r₂ )= r₁^-1(dom r₂ Ç rng r₁).

ª r₁· r₂ ={(x,y)| $z: х r₁ z, z r₂ у} , следовательно, в образовании пар отношения r₂ могут участвовать только такие значения z, для которых выполняется включение z Î dom r₂ Ç rng r_{1 .} Так как область определения композиции отношений r₁ · r₂ является подмножеством dom r₁, то в это подмножество будут включены только те элементы х, для которых определены образы в множестве dom r₂ Ç rng r₁ . Поэтому искомое множество определяется как множество прообразов множества dom r₂ Ç rng r₁ по отношению r₁^-1. Таким образом ,

dom (r₁ · r₂ ) = r₁^-1(dom r₂ Ç rng r₁). §

2. 4. rng (r₁ · r₂)= r₂(rng r₁ Ç dom r ₂ ).

2.5. Пусть r - бинарное отношение на А. Доказать, что r = i_A тогда и только тогда, когда r · r₁ = r₁ · r = r₁ для любого отношения r₁ не А.

ª Пусть r · r₁ = r для всех r₁. Тогда $ z: (xz) Î r, (zy) Î r₁ и (х,у) Î r₁. Это возможно только тогда, когда "х: z=x, т.е. r = i_A. Аналогично можно доказать, что r₁ · r = r₁ тогда и только тогда, когда r = i_A. Обратно, если r = i_A, то

" r₁:r · r₁ = r₁ · r = r₁ в силу определения операции композиции. §

3. Доказать, что для любых бинарных отношений

3.1. (r^-1)^-1 = r;

ª Пусть (х,у) Î( r^-1)^-1. Тогда по определению обратного отношения можно записать цепочку включений: (у,х) Î r^-1 Þ (х,у) Î r. Таком образом,

(r^-1)^-1 Í r. Аналогично доказывается обратное включение. Из существования двух включений делается вывод о тождественном равенстве. §

3.2. (r₁ È r₂)^-1 = r₁^-1 È r₂^-1;

3.3. (r₁ Ç r₂)^-1 = r₁^-1 Ç r₂^-1;

3.4.

ª Пусть (х,у) Î (r^-1), тогда по определению дополнения отношения

3.5. (х,у) Ï r^-1 и (у,х) Ï r. Следовательно, (у,х) Î `r и (х,у) Î (`r )^-1 . Следовательно, (r^-1) Í (`r )^-1. Обратное включение доказывается аналогично. §

3.6.

4. Для каких бинарных отношений справедливо r^-1 = `r ?

ª Если r Í А´В, А ¹ Æ и В ¹ Æ, то таких отношений не существует. §

5. Пусть А и В - конечные множества, содержащие m и n элементов соответственно.

5.1. Сколько существует бинарных отношений между элементами множеств

А и В?

ª Число бинарных отношений между элементами множеств А и В равно мощности булеана множества А´В. Так как |А´В | = m*n, то искомое число равно 2^m*n. §

5.2. Сколько имеется функций из А в В?

ª Если мощность А равна n, то любое функциональное отношение содержит n элементов, каждый из которых начинается с х ÎА, а второй элемент у может быть любым элементом В. Следовательно надо определить число различных способов дописать второй элемент в каждую из пар, т.е. число размещений с повторениями из n элементов по m, равное (n^m). §

5.3. Сколько имеется 1-1 функций из А в В?

ª Рассуждая аналогично доказательству задачи 5.2, и учитывая что 1-1 функция есть взаимно однозначное соответствие между А и В, приходим к выводу, что число таких функций равно числу размещений без повторений, А_n^m , если n ³m. Если n<m, таких функций не существует. §

5.4. При каких m, n существует взаимно однозначное соответствие между А и В?.

6. Доказать, что для любых бинарных отношений

6.1. r₁ · (r₂ · r₃) = ( r₁ · r₂) · r₃; как называется это свойство?

6.2. ( r₁ · r₂)^-1 = r₂^-1 · r₁^-1;

6.3.

ª Пусть (х,у) Î Тогда $ z: х (È r_i)z, zqy. Тогда $i ÎI $z:

x r_i z, zqy Þ $i: (x,y) Î (È r_i ) ·q Þ(х,у) Î Обратное включение доказывается аналогично. §

6.4.

6.5.

6.6.

6.7. в пунктах 6.5 и 6.6 включения нельзя заменить равенствами.

ª Пусть r₁ ={(11)}, r₂={(10)}, q ={(01), (11)}. Тогда пересечение r₁ Ç r₂= Æ, и композиция

q Ç Æ = Æ Ç q = Æ. Тогда как §

7. Доказать, что если r₁ Í r₂, то

_7.1 q ·r₁ Í q · r_2;

7.2 r₁ ·q Í r₂ · q;

7.3 r₁^-1 Í r₂^-1.

8. Доказать, что если f: A®B и g: B®C, то (f ·g):А®С.

9. Пусть f и g - функции. При каких условиях

9.1. f^—1 является функцией?

9.2. f ·g является 1-1 - функцией?

Функция f называется 1-1 - функцией, если "х₁х₂ (у=f(x₁) и y= f(x₂)) Þ х₁₌х₂.

1. Пусть f: A®B -взаимно однозначное соответствие. Показать, что

10.1. f ^-1 · f =i_B;

10.2. f ·f ^-1 = i_A.

11. Доказать, что для того , чтобы отношение r Í А´В было взаимно однозначным соответствием между А и В, необходимо и достаточно, чтобы

r · r^-1 = i_A и r^-1 · r = i_B.

12. Доказать, что для любой функции f:

12.1. f(А È В) = f(А) È f(В);

12.2.

12.3. f(А Ç В) Í f(А) Ç f(В);

12.4.

13. Доказать, что f(А Ç В) Í f(А) Ç f(В) для любых А и В тогда и только тогда, когда f есть

1-1 - функция.

14. Доказать, что f(А)\f(В) Í f(А/В) для любой функции f.