Математическое толкование символа O

3. Пусть  и  – бинарные отношения на некотором множестве. Докажите, что
()^–1 = ^–1  ^–1.
Решение.
Пусть <х,у>()^–1 <х,у><х,у> и <х,у><х,у>^–1 и <х,у>^–1  ^–1  ^–1.


4. Найдите композиции  и , где ={<x,y>RR|x+y=0}, = {<x,y>RR|xy>0}, R – множество вещественных чисел.
Решение.
={<х,у> | существует z такой, что <х,z> и }={<х,у> | существует z такой, что х+z=0 и zу>0}.
(х+z=0 в том случае, если х и z равны по модулю, но противоположны по знаку, либо х=z=0.
zу>0 в том случае, если z и у оба положительны, либо z и у оба отрицательны, но не один из них не равен нулю.)
Если у0, то такое z найдется. Поэтому = R(R\{0}).
={<х,у> | существует z такой, что <х,z> и }={<х,у> | существует z такой, что хz>0 и z+у=0}.
(xz>0 в том случае, если x и z оба положительны, либо x и z оба отрицательны, но не один из них не равен нулю.
z+у=0 в том случае, если z и у равны по модулю, но противоположны по знаку, либо х=z=0.)
Если х0, то такое z найдется. Поэтому = (R\{0})R.


5. Доказать тождество для любой функции f и произвольных множеств A и B:
f(A)\f(B) f(A\B).
Решение.
х f(A)\f(B) f(х)А и f(х)В f(х) f(A\B).


6. Является ли отношением эквивалентности отношение: иметь одну и ту же мать.
Решение.
Рефлексивное, симметричное и транзитивное отношение  на множестве х называется отношением эквивалентности на множестве х.
<х,у> «х имеет одну и ту же мать с у»
Рефлексивность: хх («х имеет одну и ту же мать с х»). Отношение рефлексивно.
Симметричность: ху «х имеет одну и ту же мать с у» ух. Отношение симметрично.
Транзитивность: ху и уz  «х имеет одну и ту же мать с у» и «у имеет одну и ту же мать с z»  «х имеет одну и ту же мать с z» хz. Отношение транзитивно.
Поэтому отношение является отношением эквивалентности.


7. Докажите, что M ={{1},{2},{3}} – разбиение множества A={1,2,3}. Перечислите все элементы отношения эквивалентности, соответствующего разбиению M.
Решение.
Каждый элемент из А принадлежит какому-то элементу из М, причем только одному, следовательно, М – разбиение.
={<1,1>, <2,2>,<3,3>}.