Контрольные вопросы и задания

1. Доказать, что если отношение R транзитивно, то R^–1 также является транзитивным.

2. Доказать, что из асимметричности отношения R следует асимметричность R^–1.

3. Доказать, что из антисимметричности отношения R следует антисимметричность R^–1.

4. Доказать, что из рефлексивности отношения R следует рефлексивность R ^–1.

5. Доказать, что для симметричности отношения R необходимо и достаточно, чтобы R^d было симметрично.

6. Отношение R симметрично тогда и только тогда, когда R = R^-1.

7. Доказать, что если отношения R₁ и R₂ рефлексивны, то рефлексивны отношения R₁  R₂ , R₁  R₂ , R₁^–1.

8. Доказать, что если отношения R₁ и R₂ антирефлексивны, то антирефлексивны и отношения R₁  R₂, R₁  R₂, R₁^–1. Показать, что композиция R₁ o R₂ антирефлексивных отношений может не быть антирефлексивной.

9. Доказать, что если отношения R₁ и R₂ симметричны, то симметричныны отношения R₁  R₂, R₁  R₂, R₁^–1, R₁ o R₁^–1.

10. Доказать, что если отношения R₁ и R₂ антисимметричны, то антисимметричны также R₁  R₂ и R₁^–1.

11. Пусть отношения R₁, R₂ – симметричны. Доказать, что для того чтобы R₁ o R₂ было симметрично необходимо и достаточно, чтобы выполнялось равенство R₁ o R₂ = R₂ o R₁.

12. Пусть отношения R₁ и R₂ антисимметричны. Объединение R₁ R₂ антисимметрично тогда и только тогда, когда R₁ R₂^-1 .

13. Доказать, что если отношение R асимметрично, то R  R₁ асимметрично для любого отношения R₁.

14. Доказать, что объединение R₁R₂ асимметричных отношений R₁ и R₂ асимметрично тогда и только тогда, когда R₁R₂^-1= = .

15. Доказать, что если отношение транзитивно, то его симметричная и асимметричная части тоже транзитивны.

16. Пусть отношения R₁, R₂ транзитивны и R₁ транзитивно относительно R₂. Доказать, что тогда R₁  R₂ также является транзитивным.

17. Какими свойствами должно обладать бинарное отношение R, чтобы выполнялось равенство R^–1 =R ?

18. Доказать, что отношение R асимметрично тогда и только тогда, когда R = ( R^d)^a.

19. Доказать, что для того чтобы отношение R было полным необходимо и достаточно, чтобы выполнялось тождество

R^a= R^d.

20. Доказать, что если отношения R₁, R₂ рефлексивны, то их композиция тоже рефлексивна.

21. Доказать, что отношения R  (R  R^d ) = R  (R )^s полны.

22. Доказать, что если отношение R полно, тоR  R^–1 и R^–1 ==R  (R  R^–1).

23. Доказать, что если отношение R асимметрично, то R^–1 R иR = R^–1(R R^d).

24. Доказать, что композиция полных отношений R₁ и R₂ является полным отношением.

25. Отношение Р негатранзитивно тогда и только тогда, когда xPy   zА, xPz или zPy.

26. Доказать, что если R рефлексивно, то R^d антирефлексивно, если R антирефлексивно, то R^d рефлексивно.

27. Доказать, что полное отношение рефлексивно.

28. Доказать, что асимметричное отношение антирефлексивно.

29. Доказать, что отношение R негатранзитивно тогда и только тогда, когда R^d транзитивно.

30. Пусть отношение R симметрично, транзитивно и для любого x существует такой y, что (x, y)R. Доказать, что оно рефлексивно.

31. Доказать, что ацикличное отношение асимметрично.

32. Доказать, что если отношение антирефлексивно и транзитивно, то оно ациклично.

33. Доказать, что асимметричное и негатранзитивное отношение транзитивно.

34. Доказать, что если отношение антирефлексивно, транзитивно и слабо полно, то оно негатранзитивно.

35. Доказать, что дополнение и двойственное отношение к антисимметричному и рефлексивному отношению R являются слабо полными.

36. Доказать, что любое отношение R симметричное и антисимметричное одновременно, является транзитивным.

37. Доказать, что для того чтобы отношение R было асимметричным необходимо, чтобы R^d иR были полными.

38. Построить бинарное отношение:

а) рефлексивное, симметричное, не транзитивное;

б) рефлексивное, антисимметричное, не транзитивное;

в) рефлексивное, не симметричное, транзитивное;

г) не рефлексивное, антисимметричное, транзитивное;

д) симметричное, транзитивное, но не рефлексивное.

39. Доказать: а) I_уп  P_уп  P^–1 _уп = AA;

б) I_уп = R^s_уп; P_уп = R^a_уп.

40. Доказать свойства 1), 2), 3), 6) отношения слабого порядка и производных от него отношений.

41. Доказать следующие свойства:

а) R_кач – полное негатранзитивное отношение;

б) отношение, не различающее близко расположенные точки

(т.е. xRy, если х  у – 1) является качественным порядком;

в) R_кач не является транзитивным, а, следовательно, R_кач  R_сл ;

г) I_кач – рефлексивно, симметрично, но не всегда транзитивно;

д) I_кач = R^s_кач и R^d_кач = Р_кач.

42. Какие из следующих отношений являются отношениями эквивалентности:

а) равенства двух чисел;

б) подобия двух треугольников;

в) порядка на вещественной прямой;

г) линейной зависимости в пространстве Rⁿ (n > 1);

д) параллельности прямых на плоскости;

е) перпендикулярности прямых на плоскости.

43. Доказать, что если отношение R транзитивно и симметрично и _R  _R = A, то R – отношение эквивалентности.

44. Доказать, что композиция эквивалентностей R₁ и R₂ является отношением эквивалентности тогда и только тогда, когда R₁ o R₂ = R₂ o R₁.

Доказать, что R является отношением эквивалентности (45–49).

45. R = { (a, b) | a, bNN , a₁ + b₂ = b₁ + a₂}.

46. R = { (a, b) | a, bN , a – b делится на m }.

47. R = { (a, b) | a, bNN , a₁b₂ = a₂b₁ , если a₂b₂  0,

a₁= b₁ , если a₂b₂ = 0 }.

48. R = { (, ) | , R ,  – Q }.

49. R={ (x, y)  | x, yR , f(x) = f(y) }, функция f – фиксирована.

50. Доказать, что следующие отношения являются эквивалентностями. Построить для них фактор-множества.

а) R = { (x, y) | x, yR³ , x₁² +x₂² +x₃² = y₁² +y₂² +y₃² };

б) R = { (x, y) | x, yR² , x₁ = y₁ };

в) R = { (x, y) | x, yR² , x₂ = y₂ };

г) R = { (x, y) | x, yR  , x – [x] = y – [y] }.

51. Доказать, что R является отношением эквивалентности тогда и только тогда, когда (R o R^–1)   = R .

51. Доказать, что если R – отношение эквивалентности, то и обратное отношение также является отношением эквивалентности.

52. Пусть R₁ и R₂ – отношения эквивалентности. Доказать, что

а) R₁ o R₁ = A²  R₁ = A²;

б) R₁ o R₂ = A²  R₂ o R₁ = A².

53. Доказать, что объединение R₁  R₂ эквивалентностей R₁ и R₂ является эквивалентностью тогда и только тогда, когда R₁  R₂ = R₁ o R₂.

54. Доказать, что отношение R на множестве A является одновременно эквивалентностью и частичным порядком в том и только в том случае, когдаR = .

55. Показать, что следующие отношения являются частичным порядком:

а) A  B в универсальном множестве S;

б) x(t)  y(t) для любого t в пространстве C[a,b];

в) m делит n на множестве N .

56. Пусть отображение   : AAA обладает свойствами:

а)  (x, y) = (y, x);

б)  (x, (y, z)) = ((x, y), z);

в)  (x, x) = x.

Доказать, что отношение R={ (x, y) | (x, y) = x } является частичным порядком.

57. Пусть функции f₁ и f₂ определены на [0,1]. Будем говорить, что f₁Rf₂, если .

Показать, что R – отношение частичного порядка.

58. Пусть множества X, Y – частично упорядочены. Введем на XY отношение: (x₁, y₁)  (x₂, y₂), если x₁  x₂, y₁  y₂. Доказать, что это отношение является частичным порядком.

59. Доказать, что если R – частичный порядок, то R^-1 также частичный порядок.

60. Доказать, что отношение R на множестве A есть предпорядок тогда и только тогда, когда R = (R o R)  .