41. Iloczyn kartezjański zbiorów. Własności, przykłady.
Iloczyn kartezjański zbiorów
Rozważmy zbiór dwuelementowy {a, b} gdzie ab. Z określenia równości zbiorów wynika, że {a, b}={b, a}. Jeśli jednak jeden z elementów tego zbioru np. a uznamy za pierwszy element, a b za drugi, to otrzymamy parę uporządkowaną (a, b)
a - pierwszy element pary nazywamy poprzednikiem
b - drugi element - następnikiem.
Warunek charakterystyczny pary uporządkowanej
(a1,b1)=(a2,b2) a1=a2 i b1=b2
Niech X i Y będą dowolnymi zbiorami. Iloczynem kartezjańskim zbiorów X i Y nazywamy zbiór: X x Y={(x,y): x∈X y∈Y} tj. zbiór wszystkich par uporządkowanych (x,y) o poprzedniku x∈X i następniku y∈Y.
Przykład:
Niech dane będą zbiory A={1, 3, 7} i B={2, 5} wówczas:
{(1, 2); (1, 5); (3, 2); (3, 5); (7, 2); (7, 5)}
oraz
{(2, 1); (2, 3); (2, 7); (5, 1); (5, 3); (5, 7)}
łatwo zauważyć, że
Własności:
1. nieprzemienność,
2. rozdzielność względem sumy,
3. rozdzielność względem iloczynu,
4. rozdzielność względem różnicy zbiorów,
Dla dowolnych zbiorów A, B, C, zachodzą następujące prawa rozdzielczości iloczynu kartezjańskiego względem sumy, iloczynu, dzielenia:
A x (B
C) = (A x B)
(A x C)
(B
C) x A = (B x A)
(C x A)
A x (B
C) = (A x B)
(A x C)
(B
C) x A = (B x A)
(C x A)
A x(B \C) = (A x B)\(A x C)
(B\C) x A = (B x A) \(C x A)
Jeśli C ≠ 0, to A ⊂ B A x C ⊂ B x C i A ⊂ B C x A ⊂ C x B
Przykładem iloczynu kartezjańskiego są R E L A C J E
RELACJE
Def. Relacją w zbiorze XxY nazywamy dowolny podzbiór zbioru ξ tego iloczynu kartezjańskiego
ξ⊂XxY, xξy (x,y)∈ ξ w szczególności:
XxY jest relacją w XxY- pełną
p=XxY
θ=Ø jest relacją w XxY-pustą(nie zachodzi nigdy)
xpy(x,y)∈p=XxY, relacja xpy ≡1 dla dow.(x,y)∈XxY, xpy - zachodzi zawsze w XxY
xθy(x,y)∈θ=Ø, relacja xθy≡0 dla dow.(x,y)∈XxY xθy- nie zachodzi nigdy w XxY.
W przypadku, gdy X=Y dowolną relację ξ⊂XxY =XxX będziemy nazywać relacją w X lub XxX.
Niech ξ⊂XxY będzie dow. relacja w XxY wówczas definiujemy dziedzinę relacji ξ jako zbiór:
D-1(ξ)={x∈X:
(x,y)∈ ξ(lub równ. x ξy)}
Jeśli ξ⊂XxY jest dowolną relacją odwrotną do relacji ξ definiujemy jako zbiór:
ξ-1⊂XxY, gdzie ξ-1={(y,x):
(x,y)∈ ξ (lub równ. x ξy)}
yξ-1xxξy dla dow. x∈X, y∈Y
Jeśli dane są relacje ξ1⊂XxY i ξ2⊂XxY to określamy relację ξ =df ξ1 ºξ2⊂XxY następującym warunkiem:
xξzIstn. y∈Y(xξ1y i yξ2z)
Tak zdefiniowaną relację ξ nazywamy złożeniem relacji ξ 1 i ξ2 .
TWIERDZENIE
Operacja składania relacji (tj. tworzenia złożenia relacji) spełnia następujący warunek łączności:
Jeśli ξ⊂XxY i ξ⊂XxZ i ξ ⊂ZxU to zachodzi równość:
(ξ1 º ξ 2) º ξ3 = ξ1 º (ξ2 º ξ3 )
Def. Relację ξ⊂XxY nazywamy korespondencją (dokł. korespondencją między zbiorami X i Y) jeśli spełnione są następujące warunki:
a) D(ξ)-X, D-1(ξ)=Y
b) jeśli x∈X oraz (x,y1)∧(x,y2)∈ ξ, to y1=y2
c) jeżli y∈Y oraz (x1,y)∧(x2,y)∈ ξ, to x1=x2.
Wniosek
Każda korespondencja jest funkcją ale na ogół funkcja nie musi być korespondencją.
UWAGA
Korespondencję ξ⊂XxY będziemy często zapisywać tak jak funkcję, czyli w formie: ξ: X->Y lub też w specjalny sposób: ξ: X↔Y.
Korespondencję taką nazywamy również funkcją wzajemnie jednoznaczną (ze zbioru X na zbiór Y)
Wniosek
Każda funkcja jest relacją ale nie każda relacja jest funkcją.
Własność
Relacją ξ∈XxY będąca funkcją a funkcję odwrotną wtedy i tylko wtedy gdy jest korespondencją.
Definicja. Relacją w zbiorze X nazywamy relację w zbiorze XxX, czyli dowolny podzbiór zbioru XxX ξ - relacja w X, czyli ξ⊂XxX. W szczególno-ści można mówić o relacja pustej w X, zbiór Ø⊂XxX.
Relacja pusta to taka relacja, która nie zachodzi między żadnymi elementami, czyli zdanie xØy jest fałszywe dla dowolnych x,y∈X.O relacji pustej możemy mówić również w przypadku ogólnym gdy Y na ogół różne od X, Ø⊂XxY.
Relacja pełna w zborze X, П-symbol relacja pełnej, П=dfXxX⊂XxX. Z kolei dla relacji П jest widoczne, że dowolne dwa elementy ze zbioru X pozostają w tej relacji tj. xПy jest zdaniem prawdziwym dla dowolnych x,y∈X. Możemy mówić o relacji pełnej gdy Y≠X na ogół wtedy П=XxY. Wówczas także zdanie xПy pozostaje prawdziwe dla dowolnych x∈X i y∈Y.
X=Y przypadek iloczynu kart. XxX, rozważamy wyłącznie dalej relacja w zbiorze X.
Definiujemy relacja tożsamości ∆ w zbiorze następująco:
∆={(x,y); x∈X}⊂XxX z
def. widać że x∆yx=y (x,y∈X)
Różne rodzaje relacja w zb. X:
(R1) Relację ξ w X naz. zwrotną jeśli xξx dla każd.x∈X lub równ. ∆⊂ξ.
(R2) Relację ξ w X naz. przeciwzwrotną jeśli ~(xξx) dla każd. x∈X lub ξ∧∆=Ø
(R3) Relację ξ w X naz. symetryczną jeśli (xξy=>yξx) dla każd. x,y∈X lub ξ⊂ξ-1
(R4) Relację ξ w X nazywamy przeciwsymetr. jeśli (xξy=>~yξx) dla każd. x,y∈X lub równ. ξ∧ξ-1= Ø
(R5) Relacja ξ w X naz. antysym. Jeśli (xξy∧ yξx=>x=y)dla każd. x,y∈X lub ξ∧ξ-1⊂∆
(R6) Relacja ξ w X naz. przechodnią jeśli (xξy∧yξz=> xξz)dla każd. x,y,z∈X lub ξ°ξ ⊂ξ.
Własność I. Jeśli relacja ξ jest symetryczna, to relacja odwrotna ξ-1 do ξ też jest symetryczna.
Wniosek. Releacja ξ jest symetryczna, wtedy i tylko wtedy, gdy ξ= ξ-1.(gdy jest identyczna ze swoją relacją. odwrotną)
Tw. Każda relacja ξ zawarta w X x X przeciwzwrotna i przechodznia jest przeciwsymetryczna. (R2)i(R6)=>(R4).
Relacja zwr nie jest przeciwsym.
Def. Relację ξ zawartą X x X nazywamy relacją równoważności w X, jeśli ξ jest jednocześnie relacją zwrotną, symetryczną i przechodnią.