41. Iloczyn kartezjański zbiorów. Własności, przykłady.

Iloczyn kartezjański zbiorów

Rozważmy zbiór dwuelementowy {a, b} gdzie ab. 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

(a₁,b₁)=(a₂,b₂) a₁=a₂ i b₁=b₂

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:

1. A x (B
   C) = (A x B)
   (A x C)

2. (B
   C) x A = (B x A)
   (C x A)

3. A x (B
   C) = (A x B)
   (A x C)

4. (B
   C) x A = (B x A)
   (C x A)

5. A x(B \C) = (A x B)\(A x C)

6. (B\C) x A = (B x A) \(C x A)

7. 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 ξ₁⊂XxY i ξ₂⊂XxY to określamy relację ξ =df ξ₁ ºξ₂⊂XxY następującym warunkiem:

xξzIstn. y∈Y(xξ₁y i yξ₂z)

Tak zdefiniowaną relację ξ nazywamy złożeniem relacji ξ ₁ i ξ₂ .

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ść:

(ξ₁ º ξ ₂) º ξ₃ = ξ₁ º (ξ₂ º ξ₃ )

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,y₁)∧(x,y₂)∈ ξ, to y₁=y₂

c) jeżli y∈Y oraz (x₁,y)∧(x₂,y)∈ ξ, to x₁=x₂.

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ą.

---