Множества. Соответствия.

Отношения.

Определение 7.1: Декартовым произведением множеств А и В называется множество всех упорядоченных пар < x,y > таких, что xA и yB. Обозначается ArB.

  1. Сколько элементов содержит множество:
a). A=X r Y, если число элементов в X равно n, а в Y - m.
b).  A=X1r X2r ...r Xn, где nN и для любого 1k n число элементов Xk равно mk.
  1. Доказать или опровергнуть:
a).  A r B = B r A
b).  A r (B r C) = (A r B)r C, если <<a,b>, c>=<a,b,c>=<a,<b,c>>
c).  (AB)r C = (A r C) (B r C)
d).  (A\B)r C = (A r C)\(B r C), если BA
e).  для каких множеств A,B и С верно: (AB)r C ~ (A r C).
  1. Доказать:
a).  N2 ~ N (N2=N r N) b).  Nn ~ N
c).  (N r [0,1]) ~ [0,1] d).  (A r B) ~ (B r A).
  1. Справедливо ли утверждение (ArB) ~ A если:
a).  А и В - конечны b).  А - конечно, В - счетно
c).  А - счетно, В - конечно d).  А и В - счетны.

Определение 7.2: Бинарным отношением на множестве А называется множество R такое, что R(ArA). Про элементы x,yA говорят, что они находятся в отношении R, если <x,y>R.

  1. Нарисовать на координатной плоскости следующие бинарные отношения на множестве всех чисел (объяснить построения):
a). x < y b). x = -y
c). x2 < y d). на Z     xy
e). записать для них множество R, если А={0,1,2,3,4,5}

Определение 7.3: Соответствием между множествами А и В называется множество R(ArB). Про элементы xA и yB говорят, что они находятся в соответствии R, если <x,y>R. Обозначается: R:AB или R:xy,   xA,yB.

Если <x,y>R, то y называют образом x, а x - прообразом y. Через y=R(x) обозначается множество всех образов x, а через x=R-1(y) множество всех прообразов y.

Область определения соответствия R (обозначается D(R)) - множество таких xA, для которых существует образ.

Область значений соответствия R (обозначается E(R)) - множество таких yB, для которых существует прообраз.

Взаимно-однозначное соответствие - соответствие, в котором для каждого элемента xA существует и единственен образ и для каждого элемента yB существует и единственен прообраз. Очевидно, что для такого соответствия D(R)=E(R).

Отображение (функция) - соответствие, в котором у каждого элемента x из А не более одного образа. При записи f:XY для отображения полагают обычно, что D(f)=X.

 

  1. Сколько существует:
a).  соответствий
b).  отображений (D(f)=X)
c).  взаимно-однозначных соответствий (m=n)

XY, если в X - n, а в Y - m элементов.

  1. Доказать: xR-1(R(x)).

Определение 7.4: Бинарное отношение ‘~ ‘ (R) на А называется отношением эквивалентности, если для любых x,y,zA верно:

1. x~ x или <x,x>R
2. (x~ y)(y~ x) или (<x,y>I R) (<y,x>R)
3. ((x~ y)&(y~ z))(x~ z) или ((<x,y>I R)&(<y,z>R))(<x,z>R).
  1. Являются ли следующие отношения - отношениями эквивалентности:
a).  A=B (для множеств)
b).  ab (a,bZ)
c).  x < y (x,yQ)
d).  a || b (прямые на плоскости)
e).  R= (на N) (может ли существовать такое отношение эквивалентности)
f).  R – конечно (на N) (то же)
  1. Введите неэлементарное отношение эквивалентности на следующих множествах (элементарным отношением эквивалентности называется такое о. э., в котором существует конечное число эквивалентных пар):
a).  N
b).  N r N
c).  [0,1]
d).  на множестве всевозможных цепочек с алфавитом {a,b,c,..,z}
e).  докажите счетность множества из пункта d)

Определение 7.5: Бинарное отношение ‘<‘ (R) на А называется отношением порядка, если для любых x,y,zA верно:

1. (x<x) или <x,x>R
2. (x<y)&(y<x) или ((<x,y>R)&(<y,x>R))
3. ((x<y)&(y<z)) (x<z) или ((<x,y>R)&(<y,z>R))(<x,z>R)
  1. Введите отношение порядка на следующих множествах:
a).  N b).  N r N
c).  [0,1] d).  на координатной плоскости
e).  на поверхности сферы f).  в языке логики высказываний

[Вернутся к оглавлению]