licencjat - opracowania (wszystkie


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

(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:

0x01 graphic
{(1, 2); (1, 5); (3, 2); (3, 5); (7, 2); (7, 5)}

oraz

0x01 graphic
{(2, 1); (2, 3); (2, 7); (5, 1); (5, 3); (5, 7)}

łatwo zauważyć, że 0x01 graphic

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 0x01 graphic
    C) = (A x B)0x01 graphic
    (A x C)

  2. (B0x01 graphic
    C) x A = (B x A)0x01 graphic
    (C x A)

  3. A x (B0x01 graphic
    C) = (A x B)0x01 graphic
    (A x C)

  4. (B0x01 graphic
    C) x A = (B x A) 0x01 graphic
    (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(ξ)={xX: 0x01 graphic
(x,y) ξ(lub równ. x ξy)}

Jeśli ξXxY jest dowolną relacją odwrotną do relacji ξ definiujemy jako zbiór:
ξ
-1XxY, gdzie ξ-1={(y,x): 0x01 graphic
(x,y) ξ (lub równ. x ξy)}

-1xxξy dla dow. xX, yY

Jeśli dane są relacje ξ1XxY i ξ2XxY to określamy relację ξ =df ξ1 ºξ2XxY następującym warunkiem:

xξzIstn. yY(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 xX oraz (x,y1)(x,y2) ξ, to y1=y2

c) jeżli yY 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,yX.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, П=dfXxXXxX. 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,yX. Możemy mówić o relacji pełnej gdy YX na ogół wtedy П=XxY. Wówczas także zdanie xПy pozostaje prawdziwe dla dowolnych xX i yY.

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); xX}XxX z
def. widać że x∆y
x=y (x,yX)

Różne rodzaje relacja w zb. X:

(R1) Relację ξ w X naz. zwrotną jeśli xξx dla każd.xX lub równ.ξ.

(R2) Relację ξ w X naz. przeciwzwrotną jeśli ~(xξx) dla każd. xX lub ξ∆=Ø
(R3) Relację
ξ w X naz. symetryczną jeśli (xξy=>yξx) dla każd. x,yX lub ξξ-1
(R4) Relację
ξ w X nazywamy przeciwsymetr. jeśli (xξy=>~yξx) dla każd. x,yX lub równ. ξξ-1= Ø

(R5) Relacja ξ w X naz. antysym. Jeśli (xξy yξx=>x=y)dla każd. x,yX lub ξξ-1

(R6) Relacja ξ w X naz. przechodnią jeśli (xξyyξz=> xξz)dla każd. x,y,zX 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ą.



Wyszukiwarka

Podobne podstrony:
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie

więcej podobnych podstron