Rozdział Relacje binarne I funkcje



Pobieranie 412,14 Kb.
Strona1/5
Data16.04.2018
Rozmiar412,14 Kb.
  1   2   3   4   5

Rozdział 3. Relacje binarne i funkcje


Obecnie, w §1, wprowadzimy istotne dla opisu relacji binarnych, kolejne dwa pojęcia teoriomnogościowe: pary uporządkowanej i produktu kartezjańskiego dwóch zbiorów. Umożliwiają one zdefiniowanie jednego z najważniejszych typów obiektów teoriomnogościowych: relacji binarnej. W §2 omawiamy operacje konwersu i złożenia na relacjach binarnych. Następny paragraf poświęcony jest relacjom binarnym określonym na danym zbiorze. Kolejne paragrafy: 4, 5, zawierają elementarną teorię funkcji jako relacji binarnych. Wreszcie, ostatnie dwa paragrafy dotyczą pojęć teoriomnogościowych związanych z pojęciem funkcji: obrazu i przeciwobrazu zbioru według danej funkcji oraz rodziny indeksowanej zbiorów i jej produktu kartezjańskiego.


§1. Produkt kartezjański, relacja binarna


Według Tw.10, kolejność wymienienia nazw zbiorów będących elementami pary zbiorów nie odgrywa żadnej roli w określaniu tej pary. Wprowadzamy pojęcie uporządkowanej pary zbiorów <x,y> takiej, że <x,y>  <y,x>, gdy x y.



Definicja. Dla dowolnych zbiorów x, y: <x,y> = {{x},{x,y}}.

Twierdzenie 25. <x,y> = <u,v>  (x = u y = v) .
Dowód: Załóżmy, że <x,y> = <u,v>. Wówczas z definicji pary uporządkowanej otrzymujemy:

  1. {{x},{x,y}} = {{u},{u,v}}.

Oczywiście x = y lub x y. Gdy x = y, to {{x},{x,y}} = {{x}}. Zatem z (1): {{x}} = {{u},{u,v}}, co oznacza, iż zachodzi:

  1. {x} = {u} oraz

  2. {x} = {u,v}.

Z (2) otrzymujemy: x = u, zaś z (3): x = u = v, zatem skoro x = y, więc y = v.

Załóżmy, że x y. Wtedy



  1. {x}  {x,y}. Wówczas na podstawie (1): ({x} = {u} lub {x} = {u,v}) oraz ( {x,y} = {u}

lub {x,y} = {u,v}). Mamy zatem następujące dwa przypadki:

  1. {x} = {u} i {x,y} = {u,v},

  2. {x} = {u,v} i {x,y} = {u}.

Jednakże przypadek (6) nie zachodzi. Gdyby bowiem zachodził, to wówczas byłoby: x = u oraz y = u, co implikuje: x = y. Zatem zachodzi przypadek (5). Stąd x = u, a ponadto, skoro y x, czyli y u, więc y = v. 

Na podstawie Tw.25 wnosimy, iż kolejność wymienienia nazw zbiorów w parze uporządkowanej jest istotna:



Wniosek. <x,y> = <y,x>  x = y.

Wykorzystamy aksjomat podzbiorów, aby dowieść istnienia zbioru wszystkich par uporządkowanych, w których pierwszy element należy do jednego danego zbioru, a drugi element pary - do drugiego danego zbioru. W tym celu wykazujemy najpierw następujący fakt pomocniczy:



Lemat. (u av b)  <u,v>  P(a b).
Dowód: Załóżmy, że u a oraz v b. Wówczas {u}  a a b oraz {u,v}  a b. Zatem {u},{u,v}  P(a b), czyli {{u},{u,v}}  P(a b), a więc z definicji pary uporządkowanej: <u,v>  P(a b). 

Połóżmy w aksjomacie podzbiorów formułę (x) postaci: uv(u a vbx = <u,v>) oraz odłączmy kwantyfikator uniwersalny wiążący zmienną z dla termu: PP(a b), otrzymując wyrażenie:


ab(x(uv(u a vbx = <u,v>)  xPP(a b)) 

yx(x y  uv(u a vbx = <u,v>))).


Dla dowolnych ustalonych zbiorów a, b poprzednik powyższej implikacji jest na mocy lematu prawdziwy, zatem odrywamy następnik i w konsekwencji uzyskujemy następującą definicję produktu kartezjańskiego a b dwóch zbiorów:

Definicja. Dla dowolnych zbiorów a, b: x(x a b  uv(u a vbx = <u,v>)) lub a b = {x: uv(u a vbx = <u,v>)} = {<u,v>: u a vb}. Produkt kartezjański a b zbiorów a, b jest zbiorem wszystkich par uporządkowanych, których pierwszy element należy do zbioru a, zaś drugi do zbioru b. Produkt a a bywa oznaczany jako a2.

Ostatnia równość występująca w definicji produktu kartezjańskiego dwóch zbiorów została napisana na mocy konwencji notacyjnej, w myśl której sekwencja symboli: {t(x1,x2,...,xn): (x1,x2,...,xn)}, gdzie t(x1,x2,...,xn) jest termem, w którym x1, x2, ..., xn są wszystkimi jego zmiennymi nazwowymi oraz (x1,x2,...,xn) jest dowolną formułą, w której x1, x2, ..., xn są zmiennymi wolnymi, oznacza zbiór: {x: x1x2...xn(x = t(x1,x2,...,xn)  (x1,x2,...,xn))}. Zastosowano tu tę konwencję dla zmiennych u, v w miejsce x1, x2 oraz dla termu t(u,v) postaci: <u,v>, i formuły (u,v) postaci: u a vb.

Używać będziemy również zapisu: {x a: (x)}, na oznaczenie zbioru: {x: x a  (x)}. Ponadto, często będziemy używać tzw. kwantyfikatorów o ograniczonym zakresie: dla dowolnej formuły , ciąg symboli: x a (), oznacza formułę: x(x a  ), zaś ciąg x a (), oznacza formułę: x(x a  ). Wreszcie, zamiast pisać: xy oraz x ay a, piszemy odpowiednio: x,y , x,y a.

Definicja. Dla dowolnych zbiorów a, b, dowolny podzbiór r a b nazywamy relacją binarną na zbiorach a, b. Mówimy, ze zbiór r jest relacją binarną (określoną) na zbiorze a, gdy r a a. Produkt a a nazywamy relacją pełną na zbiorze a, natomiast zbiór   a a relacją pustą.

Niech r a b będzie dowolną relacją binarną. Zbiór D(r) = {x a: y b (<x,y>  r)} nazywamy dziedziną relacji r, natomiast zbiór D-1(r) = {y b: x a (<x,y>  r)} nazywamy przeciwdziedziną relacji r.

Naturalnie istnienie dziedziny i przeciwdziedziny danej relacji binarnej gwarantowane jest przez aksjomat podzbiorów.


§2. Operacje konwersu i złożenia relacji

Definicja. Niech r a b będzie dowolną relacją binarną. Przez konwers relacji r lub relację odwrotną do r rozumiemy relację binarną r b a określoną następująco: ybx a (<y,x>  r  <x,y>  r), tzn. r = {<y,x>  b a: <x,y>  r}.

Niech ponadto s b c. Przez złożenie (superpozycję) relacji r, s rozumiemy relację binarną r s a c określoną następująco: x az c (<x,z>  r s  yb (<x,y>  r  <y,z>  s)).

Dla dowolnego zbioru a, relację id(a) a a określoną następująco: x,y a (<x,y>  id(a)  x = y) lub id(a) = {<x,x>: x a}, nazywamy relacją identycznościową (identyczności lub tożsamościową) na zbiorze a.


Przykład. Niech r = {<x,x>,<x,y>,<z,y>} będzie relacją binarną określoną na zbiorze a = {x,y,z}, x y, x z, y z. Wówczas
r = {<x,x>,<y,x>,<y,z>},

r r = {<x,x>,<x,y>},

r r = {<x,x>,<x,z>,<z,x>,<z,z>},

id(a) = {<x,x>,<y,y>,<z,z>}.

Twierdzenie 26. Niech r a b, s b c oraz t c d. Wówczas


  1. r (s t) = (r s) t,

  2. r id(b) = id(a) ◦ r = r,

  3. (r s) = s r.


Dowód: Dla (1): Naturalnie s t b d, zaś r s a c, zatem r (s t)  a d oraz (r s) t a d.

(): Niech dla x a, ud: <x,u>  r (s t). Wówczas dla pewnego y b:



  1. <x,y>  r oraz

  2. <y,u>  s t.

Z (5) dla pewnego z c zachodzi:

  1. <y,z>  s oraz

  2. <z,u>  t.

Zatem z (4) i (6): <x,z>  r s, stąd i z (7) otrzymujemy: <x,u>  (r s) t.

(): Dowód analogiczny.

Dla (2): Wykazujemy, że r id(b) = r. Niech x a oraz y b.

(): Załóżmy, że <x,y>  r id(b). Wówczas dla pewnego y1 b: <x,y1>  r oraz <y1,y>  id(b). Stąd y1 = y, czyli <x,y>  r.

(): Załóżmy, że <x,y>  r. Ponieważ <y,y>  id(b), więc z definicji złożenia relacji otrzymujemy: <x,y>  r id(b).

Analogicznie wykazuje się, że id(a) ◦ r = r.

Dla (3): Naturalnie (r s) c a (bo r s a c) oraz s rc a (bo sc b i rb a).

(): Niech z c oraz x a. Załóżmy, że <z,x>  (r s). Wówczas <x,z>  r s, zatem dla pewnego y b: <x,y>  r oraz <y,z>  s. Czyli, <z,y>  s oraz <y,x>  r. Ostatecznie, <z,x>  s r.

(): Rozumowanie odwrotne do powyższego. 

Twierdzenie 27. Niech r1, r2 a b oraz s b c. Wówczas


  1. r1 r2 r1 s r2 s,

  2. (r1 r2) = r1 r2,

  3. (r1 r2) = r1 r2.


Dowód: Dla (1): Załóżmy, że r1 r2. Niech dla x a oraz z c: <x,z>  r1 s. Wówczas dla pewnego y b zachodzi: <x,y>  r1 oraz <y,z>  s. Wobec założenia otrzymujemy: <x,y>  r2 i ostatecznie, <x,z>  r2 s.

Dla (2): Następujący ciąg równoważności: <y,x>  (r1 r2)  <x,y>  r1 r2  (<x,y>  r1  <x,y>  r2)  (<y,x>  r1  <y,x>  r2)  <y,x>  r1 r2, dowodzi, w oparciu o aksjomat identyczności, iż (r1 r2) = r1 r2.

Dla (3): Dowód analogiczny jak dla (2). 



  1   2   3   4   5


©operacji.org 2017
wyślij wiadomość

    Strona główna