Iloczyn kartezjański i relacje binarne
Wstęp 2
1. Para uporządkowana i iloczyn kartezjański zbiorów 3
2. Relacje binarne 7
3. Rodzaje relacji binarnych 14
Bibliografia 18
Wstęp
Moduł czwarty przedstawi podstawowe pojęcia teorii mnogości potrzebne między
innymi do opisu i modelowania systemów informatycznych.
Temat pierwszy dotyczy pojęcia pary uporządkowanej oraz definicji iloczynu kar-
tezjańskiego zbiorów. Zostaną omówione i  w większości  udowodnione pod-
stawowe własności iloczynu kartezjańskiego.
Temat drugi zaprezentuje pojęcie relacji binarnej, reprezentacji graficznej relacji
i działań na relacjach wraz z ich podstawowymi własnościami.
W temacie trzecim zawarte są definicje własności relacji binarnych, przykłady oraz
zależności między nimi.
2
1. Para uporzÄ…dkowana
i iloczyn kartezjański zbiorów
Para uporządkowana i iloczyn kartezjański zbiorów są podstawowymi pojęciami nauki
o zbiorach, na których opiera się pojęcie relacji.
Para uporządkowana (a, b) to dowolny, złożony z dwóch elementów obiekt, speł-
niający poniższe założenia:
çÅ‚ jeÅ›li a `" b , to (a, b) `" (b, a).
çÅ‚ jeÅ›li (a, b) = (c, d), to a = c oraz b = d.
Jeżeli (a, b) jest parą uporządkowaną, to element a nazywamy poprzednikiem pary,
zaś element b następnikiem pary.
Jedną z popularniejszych definicji pary uporządkowanej podał w 1920 roku polski
matematyk Kazimierz Kuratowski: (a, b) =df.{{a}, {a, b}}. A
atwo można udowod-
nić, że tak zdefiniowana  za pomocą pojęcia zbioru  para uporządkowana speł-
nia podane wyżej wymagania.
Pojęcie pary uporządkowanej służy do zdefiniowania pojęcia iloczynu kartezjań-
skiego zbiorów. Niech A oraz B będą dowolnymi zbiorami. Iloczynem kartezjań-
skim zbiorów A i B nazywamy zbiór wszystkich takich par uporządkowanych
(a, b), że a " A oraz b " B. Iloczyn kartezjański zbiorów A oraz B oznaczamy sym-
bolem A × B.
Rozważmy zbiory A = {1, 2, 3} oraz B = {a, b}. Iloczynem kartezjańskim tych
zbiorów jest, zgodnie z definicją, zbiór wszystkich par uporządkowanych (a, b) ta-
kich, że a " A oraz b " B. Mamy zatem A × B = {(1, a), (2, a), (3, a), (1, b),
(2, b), (3, b)}.
Jeżeli zbiór A ma n elementów, a zbiór B ma k elementów, to iloczyn kartezjański
A × B ma n Å" k elementów.
Przykład 1
Znanym przykładem iloczynu kartezjańskiego jest płaszczyzna, rozumiana jako
zbiór punktów o współrzędnych rzeczywistych.
Twierdzenie 1
Zachodzą następujące własności dla iloczynu kartezjańskiego:
(a) (A × B `" B × A) Ô! (A `" B '" A `" " '" B `" "),
(b) (A × B = B × A) Ô! (A = B (" A = " (" B = "),
(c) A × (B *" C) = (A × B) *" (A × C) (iloczyn kartezjaÅ„ski jest rozdzielny wzglÄ™dem
sumy zbiorów),
(d) A × (B )" C) = (A × B) )" (A × C) (iloczyn kartezjaÅ„ski jest rozdzielny wzglÄ™dem
iloczynu zbiorów),
(e) A × (B  C) = (A × B)  (A × C) (iloczyn kartezjaÅ„ski jest rozdzielny wzglÄ™dem
różnicy zbiorów),
3
(f) A × B `" " Ô! (A `" " '" B `" ")
(g) A × B = " Ô! (A = " (" B = "),
(h) A × " = ",
(i) " × A = ",
(j) " × " = ".
Dowód (c)
Aby udowodnić powyższą równość, musimy  zgodnie z definicją równości zbio-
rów  wykazać prawdziwość następującego warunku:
" (x " A × (B *" C) Ô! x " (A × B) *" (A × C))
x
Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporządko-
waną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność jest
oczywista (obie strony fałszywe, obiekt niebędący parą uporządkowaną nie może
należeć do iloczynu kartezjańskiego).
Jeśli zaś x = (a, b), to:
L : x " A × (B *" C) Ô!1 (a, b) " A × (B *" C) Ô!2 a " A '" b " (B *" C) Ô!3
Ô! a " A '" (b " B (" b " C) Ô!4 (a " A '" b " B) (" (a " A '" b " C) Ô!
Ô! (a, b) " (A × B) (" (a, b) " (A × C) Ô!
Ô! x " (A × B) (" x " (A × C) Ô! x " (A × B) *" (A × C) : P
Dowód (e)
Mamy wykazać, że " (x " A × (B  C) Ô! x " (A × B)  (A × C)).
x
Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowanÄ…, albo x jest parÄ… uporzÄ…dkowanÄ….
W pierwszym przypadku równoważność jest oczywista.
W drugim przypadku, jeśli x = (a, b), to:
L : x " A × (B  C) Ô!5 (a, b) " A × (B  C) Ô!6 a " A '" b " (B  C) Ô!7
Ô! a " A '" (b " B '" b " C) (*)
P : x " (A × B)  (A × C) Ô! x " (A × B) '" x " (A × C) Ô!
Ô! (a, b) " (A × B) '" (a, b) " (A × C) Ô! (a, b) " (A × B) '" Ź[ (a, b) " (A × C) ] Ô!
Ô! (a " A '" b " B) '" Ź(a " A '" b " C) Ô! (a " A '" b " B) '" (Ź(a " A) (" Ź(b " C)) Ô!
Ô! (a " A '" b " B '" Ź(a" A)) (" (a " A '" b " B '" Ź(b " C)) Ô!8
Ô! a " A '" (b " B '" b " C) (*)
1
Ponieważ założyliśmy, że x = (a, b).
2
Z definicji iloczynu kartezjańskiego.
3
Definicja sumy zbiorów.
4
Prawo rozdzielności koniunkcji względem alternatywy.
5
Ponieważ założyliśmy, że x = (a, b).
6
Z definicji iloczynu kartezjańskiego.
7
Definicja różnicy zbiorów.
8
Lewy składnik alternatywy jest fałszywy, zatem alternatywa ta jest równoważna pozosta-
łemu składnikowi.
4
W rezultacie rozpisanie obu stron równoważności dało ten sam wynik (*), zatem
L Ô! P, czyli:
x " A × (B  C) Ô! x " (A × B)  (A × C).
Dowód (h)
Mamy wykazać, że " (x " A × " Ô! x " ").
x
Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.
W drugim przypadku, gdy x = (a, b), mamy:
L : x " A × " Ô! (a, b) " A × " Ô! a " A '" b " " Ô!9 x " " : P
Twierdzenie 2
W ogólnym przypadku nie zachodzą następujące własności iloczynu kartezjańskiego:
(a) A *" (B × C) = (A *" B) × (A *" C),
(b) A )" (B × C) = (A )" B) × (A )" C),
(c) A  (B × C) = (A  B) × (A  C).
Dowód (a)
Pokażemy, że dla zbiorów A = B = C = R nie zachodzi równość z podpunktu (a).
Mamy:
L = R *" (R × R).
Zbiór ten to suma zbioru liczb rzeczywistych oraz zbioru par uporządkowanych,
których elementami są liczby rzeczywiste.
Mamy na przykÅ‚ad 1 " R, co natychmiast daje 1 " R *" (R × R).
Rozważmy stronę prawą równości. Mamy:
P = (R *" R) × (R *" R) = R × R.
Oczywiście, do tego zbioru należą tylko odpowiednie pary uporządkowane, a za-
tem 1 " R × R.
Pokazaliśmy istnienie elementu, który należy do lewej strony równości, a nie nale-
ży do prawej, zatem zbiory powyższe nie są równe.
Dowód (b)
Pokażemy, że dla zbiorów A = B = C = R nie zachodzi równość z podpunktu (b).
Mamy:
P = (R )" R) × (R )" R) = R × R.
OczywiÅ›cie R × R `" ".
9
Ta równoważność jest prawdziwa, gdyż ma obie strony fałszywe (nic nie może należeć do
zbioru pustego).
5
L = R )" (R × R)
Zbiór ten to iloczyn dwóch rozłącznych zbiorów (R to zbiór liczb rzeczywistych,
a R × R to zbiór par uporzÄ…dkowanych), zatem jest on równy zbiorowi pustemu.
Mamy:
P `" " oraz L = ".
Oczywiście L `" P.
6
2. Relacje binarne
Na co dzień często dokonujemy porównań między pewnymi rzeczami, osobami,
zjawiskami (elementami danego zbioru lub danych zbiorów). Mówimy, że czło-
wiek A jest wyższy od człowieka B, produkt C jest tańszy od produktu D, liczba x
jest mniejsza od liczby y. Zauważamy więc (abstrahujemy z rzeczywistości) pewne
związki (zależności) między pewnymi obiektami. Zależności takie matematyka na-
zywa relacjami.
Relacje są również jednym z podstawowych narzędzi stosowanych w informatyce
między innymi do opisu (modelowania, charakteryzowania, specyfikacji) własno-
ści szeroko pojętych różnych systemów informatycznych, a przez to również syste-
mów oprogramowania.
Przykład 2
Rozważmy zależność między żołnierzami w jednostce wojskowej, nazy-
K
K
K
K
waną relacją  bycia podwładnym .
K
K
K
K
Niech P = {K, C, S, A, B, D} będzie patrolem wojskowym, gdzie:
K  kapitan,
C
C
C
C
C  chorąży,
C
C
C
C
S  sierżant,
A, B, D  szeregowi.
S
S
S
S
S
S
S
S
Oczywiste, że A jest podwładnym S, S jest podwładnym C i tak dalej. Za-
uważmy, że jeżeli zastanowimy się nad reprezentacją graficzną zależności
między elementami zbioru P, łatwo można narysować następujący dia-
A B D
A B D
A B D
A D
gram (rB
ysunek 1).
A B D
A B D
A B D
A B D
Nietrudno zauważyć, że każdą z elementarnych relacji między żołnierza-
Rysunek 1
mi patrolu P można reprezentować (specyfikować) przez odpowiednią parę upo-
rzÄ…dkowanÄ…. Mamy zatem pary: (A, S), (A, C), (A, K), (B, S), (B, C), (B, K), (D, S),
(D, C), (D, K), (S, C), (S, K), (C, K).
Możemy więc powiedzieć, że relację  bycia podwładnym określa pewien zbiór par
uporządkowanych. Zauważmy również, że ten zbiór jest podzbiorem iloczynu kar-
tezjaÅ„skiego P × P, przy czym jest to tylko jego podzbiór wÅ‚aÅ›ciwy (różny od caÅ‚e-
go iloczynu P × P).
Jak widać, relacje dwuargumentowe, czyli zachodzące między dwoma elementami,
można definiować jako pewne zbiory par uporządkowanych.
RelacjÄ… okreÅ›lonÄ… na iloczynie kartezjaÅ„skim A × B nazwiemy zatem dowolny pod-
zbiór tego iloczynu kartezjańskiego.
Relacją binarną określoną na zbiorze A nazywamy dowolny podzbiór iloczynu kar-
tezjaÅ„skiego A × A.
Jeżeli przyjmujemy taką definicję, to łatwo zauważyć, że elementami niepustych re-
lacji binarnych sÄ… pary uporzÄ…dkowane.
7
a b
c d
Relacje binarne określone na zbiorze A oznaczać będziemy symbolem
´ (´ Ä…" A × A). Fakt należenia pary uporzÄ…dkowanej (a, b) do relacji ´
bÄ™dziemy oznaczać przez (a, b) " ´. Zamiennie bÄ™dziemy też używali
zapisu  a ´ b (element a jest w relacji ´ z elementem b).
Nietrudno zauważyć, że skończone relacje binarne można łatwo inter-
pretować graficznie jako zbiór (graf) odpowiednich przejść (tranzycji)
między elementami odpowiedniego zbioru.
Przykład 3
Rysunek 2
a b c d
Rozważmy zbiór A = {a, b, c, d} i określoną na nim relację:
a 1 1 0 1
´ = {(a, a), (b, b), (a, b), (b, a), (c, d), (a, d), (d, a), (b, d)}.
b 1 1 0 1
Reprezentacja graficzna tej relacji jest przedstawiona na rysunku 2.
c 0 0 0 1
Oczywiste jest, że odpowiedni zbiór par uporządkowanych (relacja) deter-
minuje dokładnie jeden graf. Zachodzi również własność odwrotna: każdy
d 1 0 0 0
graf determinuje dokładnie jedną relację (odpowiedni zbiór par uporząd-
kowanych).
Relacje skończone reprezentować można również za pomocą macierzy,
wpisując w polach o odpowiednich współrzędnych jedynkę (jeżeli relacja
zachodzi między danymi współrzędnymi macierzy) lub zero (gdy relacja
nie zachodzi).
Rysunek 3
Relację z poprzedniego przykładu reprezentować można jako następującą
macierz (rysunek 3).
Oczywiste jest również w tym przypadku, że odpowiedni zbiór par uporząd-
kowanych (relacja) determinuje dokładnie jedną macierz (z dokładnością do
kolejności ustawienia elementów-współrzędnych) oraz każda macierz deter-
a b c d
minuje dokładnie jedną relację (odpowiedni zbiór par uporządkowanych).
a 0 0 1 1
b 1 1 0 1
Przykład 4
c 1 0 1 1
Rozważmy macierz przedstawioną na rysunku 4.
Reprezentuje ona oczywiście relację:
d 0 0 0 0
´ = {(a, c), (a, d), (b, a), (b, b), (b, d), (c, a), (c, c), (c, d)}.
Rysunek 4
Niech ´ Ä…" X × Y bÄ™dzie relacjÄ… dwuargumentowÄ… na zbiorach X, Y.
DziedzinÄ… relacji ´, oznaczanÄ… przez D(´), nazywamy zbiór wszystkich poprzedni-
ków par należących do relacji ´.
D(´) = {x " X : " (x, y) " ´}10.
y"Y
PrzeciwdziedzinÄ… relacji ´, oznaczanÄ… przez D*(´), nazywamy zbiór wszystkich na-
stÄ™pników par należących do relacji ´.
D*(´) = {y " Y : " (x, y) " ´}11.
x"X
10
W innej formie D(´) = {x " X : " x ´ y}.
y"Y
11
Inaczej D*(´) = {y " Y : " x ´ y}.
x"X
8
Niżej zdefiniujemy podstawowe operacje na relacjach binarnych: sumę, iloczyn,
konwers i złożenie (superpozycję relacji).
Niech A oraz B bÄ™dÄ… dowolnymi zbiorami. Niech ´1 bÄ™dzie dowolnÄ… relacjÄ… okre-
Å›lonÄ… na zbiorze A (´1 Ä…" A × A), zaÅ› ´2 bÄ™dzie dowolnÄ… relacjÄ… okreÅ›lonÄ… na zbiorze
B (´2 Ä…" B × B).
Zauważmy, że A ą" A *" B oraz B ą" A *" B.
Możemy zatem stwierdzić, że zarówno ´1 Ä…" (A *" B) × (A *" B), jak i ´2 Ä…" (A *" B)
× (A *" B). Możemy teraz dla danych relacji ´1 oraz ´2 zdefiniować sumÄ™ oraz
iloczyn tych relacji.
RelacjÄ™ (´1 *" ´2) okreÅ›lonÄ… na zbiorze A *" B ((´1 *" ´2) Ä…" (A *" B) × (A *" B)) speÅ‚-
niającą zależność:
a (´1 *" ´2) b Ô! a ´1 b (" a ´2 b,
nazywamy sumÄ… relacji ´1 oraz ´2.
Inaczej możemy zapisać:
(´1 *" ´2) =df. {(a, b) " (A *" B) × (A *" B) : (a, b) " ´1 (" (a, b) " ´2}.
RelacjÄ™ (´1 )" ´2) okreÅ›lonÄ… na zbiorze A *" B ((´1 )" ´2) Ä…" (A *" B) × (A *" B)), speÅ‚-
niającą zależność:
a (´1 )" ´2) b Ô! a ´1 b '" a ´2 b,
nazywamy iloczynem relacji ´1 oraz ´2.
Inaczej możemy zapisać:
(´1 )" ´2) =df. {(a, b) " (A *" B) × (A *" B) : (a, b) " ´1 '" (a, b) " ´2}.
Zauważmy, że jeżeli zbiór A )" B jest pusty, to i relacja (´1 )" ´2) jest zbiorem
pustym.
Przykład 5
Relację  d" , określoną na zbiorze liczb naturalnych, możemy traktować jako sumę
relacji  < oraz relacji  = określonych odpowiednio na zbiorze liczb naturalnych
(bo x d" y Ô! x < y (" x = y).
Relację  = , określoną na zbiorze liczb naturalnych, możemy traktować jako ilo-
czyn relacji  d" oraz relacji  e" określonych odpowiednio na zbiorze liczb natural-
nych (bo x = y Ô! x d" y '" x e" y).
Zachodzą następujące własności dotyczące dziedziny i przeciwdziedziny sumy
i iloczynu relacji.
Twierdzenie 3
Dla dowolnych relacji ´1, ´2 Ä…" A × B:
(a) D (´1 *" ´2) = D(´1) *" D(´2),
(b) D*(´1 *" ´2) = D*(´1) *" D*(´2 ),
(c) D(´1 )" ´2) Ä…" D(´1) )" D(´2),
(d) D*(´1 )" ´2) Ä…" D*(´1) )" D*(´2).
9
Szkic dowodu (a)
x " D(´1 *" ´2) Ô! " (x, y) " (´1 *" ´2) Ô! " (x ´1 y (" x ´2 y) Ô!
y"B y"B
Ô! " x ´1 y (" " x ´2 y Ô! x " D(´1) (" x " D(´2) Ô!
y"B y"B
Ô! x " D(´1) *" D(´2).
StÄ…d:
x " D(´1 *" ´2) Ô! x " D(´1) *" D(´2).
Szkic dowodu (c)
x " D(´1 )" ´2) Ô! " (x, y) " (´1 )" ´2) Ô! " (x ´1 y '" x ´2 y) Ò!12
d -1
y"B y"B
Ò! " x ´1 y '" " y Ô! x " D(´1) '" x " D(´2) Ô!
ax ´ b
y"B y"B 2
Ô! x " D(´1) )" D(´2).
d
StÄ…d:
x " D(´1 )" ´2) Ò! x " D(´1) )" D(´2).
Rozważmy relacjÄ™ ´ okreÅ›lonÄ… na zbiorze A(´ Ä…" A × A).
RelacjÄ™ ´ 1 okreÅ›lonÄ… na zbiorze A, speÅ‚niajÄ…cÄ… zależność:
a ´ 1 b Ô! b ´ a13
´  1
nazywamy konwersem (odwrotnoÅ›ciÄ…) relacji ´.
Inaczej możemy zapisać:
´
´ 1 = df.{(a, b) " A × A : (b, a) " ´}.
Rysunek 5
InterpretacjÄ™ graficznÄ… konwersu relacji przedstawia rysunek 5.
Przykład 6
Relacją odwrotną do relacji  <  , określonej na zbiorze liczb naturalnych, jest relacja
 > (okreÅ›lona na tym samym zbiorze), zachodzi bowiem zależność y < x Ô! x > y
(możemy też zapisać ( < ) 1 =  > ).
Relacją odwrotną do relacji  być żoną , określonej na zbiorze ludzi, jest relacja  być
mężem , określona na tym samym zbiorze, zachodzi bowiem zależność:  x jest
żonÄ… y Ô!  y jest mężem x .
Twierdzenie 4
Dla dowolnych relacji ´, ´1, ´2 Ä…" A × B jest:
(a) (a, b) " ´ 1 Ô! (b, a) " ´,
(b) D(´ 1) = D*(´) (dziedzina konwersu jest równa przeciwdziedzinie danej relacji),
(c) D*(´ 1) = D(´) (przeciwdziedzina konwersu jest równa dziedzinie danej relacji),
(d) (´ 1) 1 = ´ (konwers konwersu jest równy danej relacji),
(e) (´  ) 1 = (´ 1) (dopeÅ‚nienie konwersu równe jest konwersowi dopeÅ‚nienia),
12
Korzystamy z odpowiedniego prawa rozkładu kwantyfikatora szczegółowego względem
koniunkcji: " [Åš(x) '" ¨(x)] Ò! " Åš(x) '" " ¨(x).
x x x
13
Inaczej: (a, b) " ´ 1 Ô! (b, a) " ´.
10
(f) (´1 *" ´2) 1 = ´1 1 *" ´2 1 (konwers sumy relacji równy jest sumie konwersów),
(g) (´1 )" ´2) 1 = ´1 1 )" ´2 1 (konwers iloczynu relacji równy jest iloczynowi kon-
wersów).
Dowód (d)
Trzeba wykazać, że " (x " (´ 1) 1 Ô! x " ´).
x
Niech x będzie dowolny. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.
W drugim przypadku, jeśli x = (a, b), to:
L : x " (´ 1) 1 Ô! (a, b) " (´ 1) 1 Ô! (b, a) " (´ 1) Ô! (a, b) " ´ Ô! x " ´ : P
Szkic dowodu (e)
L : x " (´ ) 1 Ô! (a, b) " (´ ) 1 Ô! (b, a) " ´ Ô! (b, a) " ´ Ô!
Ô! (a, b) " ´ 1 Ô! (a, b) " (´ 1) Ô! x " (´ 1) : P
Szkic dowodu (f)
L : x " (´1 *" ´2) 1 Ô! (a, b) " (´1 *" ´2) 1 Ô! (b, a) " (´1 *" ´2) Ô!
Ô! (b, a) " ´1 (" (b, a) " ´2 Ô! (a, b) " ´1 1 (" (a, b) " ´2 1 Ô!
Ô! (a, b) " ´1 1 *" ´2 1 Ô! x " ´1 1 *" ´2 1 : P
Szkic dowodu (g)
L : x " (´1 )" ´2) 1 Ô! (a, b) " (´1 )" ´2) 1 Ô! (b, a) " (´1 )" ´2) Ô!
Ô! (b, a) " ´1 '" (b, a) " ´2 Ô! (a, b) " ´1 1 '" (a, b) " ´2  1 Ô!
Ô! (a, b) " ´1 1 )" ´2 1 Ô! x " ´1 1 )" ´2 1 : P
Niech ´1 Ä…" A × B oraz ´2 Ä…" B × C.
ZÅ‚ożeniem relacji (superpozycjÄ…) ´1 oraz ´2 nazywamy relacjÄ™ (´2 ż ´1) Ä…" A × C takÄ…, że:
a (´2 ż ´1) c Ô! "b"B (a ´1 b '" b ´2 c)14.
Symbolicznie:
´2 ż ´1 = {(a, c) " A × C : "b"B [(a, b) " ´1 '" (b, c) " ´2]}.
InterpretacjÄ™ graficznÄ… superpozycji relacji przedstawia rysunek 6.
Zachodzą poniższe własności operacji złożenia relacji.
14
Zwróćmy uwagÄ™ na  odwrotnÄ… notacjÄ™ . Jeżeli a ´1 b '" b ´2 c, to powiemy, że a jest w re-
lacji (´2 ż ´1) z elementem c.
11
c
Twierdzenie 5
Dla dowolnych relacji ´1, ´2, ´3 Ä…" A × A speÅ‚nione sÄ… warunki:
(a) (´2 ż ´1) 1 = ´1 1 ż ´2 1,
(b) ´3 ż (´2 ż ´1) = (´3 ż ´2) ż ´1 (operacja superpozycji relacji jest
Å‚Ä…czna),
(c) D*(´1) = D(´2) Ò! D(´2 ż ´1) = D(´1),
(d) D*(´1) = D(´2) Ò! D*(´2 ż ´1) = D*(´2).
Dowód (a)
Trzeba pokazać, że " (x " (´2 ż ´1) 1 Ô! x " (´1 1 ż ´2 1)).
x
Niech x będzie dowolny. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
Rysunek 6
jest oczywista.
W drugim przypadku mamy dla pewnej pary (a, b) : x = (a, b).
L : x " (´2 ż ´1)  1 Ô! (a, b) " (´2 ż ´1) 1 Ô! (b, a) " ´2 ż ´1 Ô!
Ô! " (b ´1 c '" c ´2 a) Ô! " (c ´1 1b '" a ´2 1c) Ô!
c c
Ô! " (a ´2 1c '" c ´1 1b) Ô! (a, b) " ´1 1 ż ´2 1 Ô! x " ´1 1 ż ´2 1 : P
c
d
1
d
1
a c a
a c
´1  1
d
2
d
1
o
d
d d 2
1

´2 21 o
d d
1 2
( d
b
Rysunek 7
b
Finalnie:
x " (´2 ż ´1)  1 Ô! x " (´1 1 ż ´2 1).
IntuicjÄ™ graficznÄ… dowodu przedstawia rysunek 7.
Szkic dowodu (c)
Załóżmy, że D*(´1) = D(´2).
d d
1 1 1
d
1 1
d dd1
 1
d1 d1 1
1 1
d1 d1 1
a c a c
c a c
a c aa c
a c a c
L : a " D(´2 ż ´1) Ô! " a(´2 ż ´1)c Ô!
a c a c
c
Ô! " "b (a ´1 b '" b ´2 c) Ò! " "b (a ´1 b) '" " "b (b ´2 c) Ô!
c c c
Ô! "b (a ´1 b) '" " (b ´2 c) Ò! "b (a ´1 b) Ô! a " D(´1) : P
c
-1 -1
d
2
-1oo -1
d d-1
-1
d2 d-1 22o d2d2 d1 o d2 d1-1 o d2-1 d2 -1 d2 -
2 odd2 o d 2
1 -1
d2 d d 2-1
1 d2-1 d
o d1 d-1 2
1
=
d d =
d1 o d2
1 2
=d1
d1o d2 =
=
o
( d d )-1 o 2
1 2 ( d d )-1
o 1
( d d )-1
( d1 o d )-1
1 22
( d1o d )-1
2
b b
b
b bb
b b
b b
12
Finalnie:
a " D(´2 ż ´1) Ò! a " D(´1), zatem D(´2 ż ´1) Ä…" D(´1).
P : a " D(´1) Ô! "b (b " D*(´1) '" a´1b) Ô!
Ô!15 "b (b " D(´2) '" a ´1 b) Ò! "b (a´1b '" " b´2c) Ô!
c
Ô! " "b (a´1b '" b´2c) Ô! " a(´2 ż ´1)c Ô! a " D(´2 ż ´1) : L
c c
Zatem a " D(´1) Ò! a " D(´2 ż ´1), czyli D(´1) Ä…" D(´2 ż ´1).
Finalnie  przy zaÅ‚ożeniu, że D*(´1) = D(´2)  mamy D(´1) = D(´2 ż ´1).
15
Wykorzystujemy tutaj zaÅ‚ożenie, że D*(´1) = D(´2).
13
3. Rodzaje relacji binarnych
Podamy teraz różne rodzaje relacji binarnych.
Rozważmy dowolnÄ… relacjÄ™ ´ okreÅ›lonÄ… na zbiorze A (´ Ä…" A × A).
a b
1. Jeżeli każdy element zbioru A jest w relacji sam ze sobą, to powiemy, że rela-
cja ´ jest zwrotna. Można to zapisać symbolicznie:
Relacja ´ jest zwrotna wtw, gdy " (x ´ x)16.
x"A
c d
Przykład 7
Przykładem relacji zwrotnej jest relacja równoległości prostych na płaszczyz
- Rysunek 8
nie: każda prosta jest równoległa do samej siebie.
W reprezentacji graficznej relacja jest zwrotna, jeżeli z każdego elementu istnieje
a b c d
przejście (tranzycja) do niego samego (tzw. tranzycja identycznościowa) (rysunek
1 1 0 1
a 1 1 0 1
8). Inne tranzycje nie majÄ… tu znaczenia.
0 1 0 1
b 0 1 0 1
W reprezentacji macierzowej relacja jest zwrotna, jeżeli na głównej przekątnej są same
jedynki. Macierz dla powyższej relacji została przedstawiona na rysunku 9. 0 0 1 1
c 0 0 1 1
d 0 0 0 1 0 0 0 1
2. Jeżeli żaden element zbioru A nie jest w relacji sam ze sobą, to powiemy, że rela-
cja ´ jest przeciwzwrotna. Można to zapisać symbolicznie:
Rysunek 9
Relacja ´ jest przeciwzwrotna wtw, gdy " Ź(x ´ x)17.
x"A
Przykład 8
a b
Przykładem relacji przeciwzwrotnej jest relacja prostopadłości prostych na płasz-
czyz
nie: żadna prosta nie jest prostopadła do samej siebie.
W reprezentacji graficznej relacja jest przeciwzwrotna, jeżeli żaden element zbio-
ru nie ma tranzycji do samego siebie (rysunek 10). Inne tranzycje nie majÄ… zna-
czenia.
3. Jeżeli dla każdych dwóch elementów x i y zbioru A z faktu, że element x jest
c d
w relacji z elementem y wynika, że również y jest w relacji z x, to powiemy, że
Rysunek 10
relacja ´ jest symetryczna.
Symbolicznie:
Relacja ´ jest symetryczna wtw, gdy " (x ´ y Ò! y ´ x).
x,y"A
Przykład 9
Przykładem relacji symetrycznej jest także relacja równoległości prostych na płasz-
czyz
nie: jeżeli prosta p jest równoległa do prostej q, to prosta q jest również rów-
noległa do prostej p.
16
Inaczej " (x, x) " ´.
x"A
17
Inaczej " (x, x) " ´.
x"A
14
W reprezentacji graficznej relacja jest symetryczna, jeżeli każda tranzycja
ma tranzycjÄ™ przeciwnÄ… (rysunek 11).
4. Jeżeli dla każdych dwóch elementów x i y zbioru A z faktu, że element x
jest w relacji z elementem y wynika, że y nie jest w relacji z x, to powie-
my, że relacja ´ jest asymetryczna.
Symbolicznie:
Relacja ´ jest asymetryczna wtw, gdy " [x ´ y Ò! Ź(y ´ x)].
x,y"A
Przykład 10 Rysunek 11
Przykładem relacji asymetrycznej jest relacja mniejszości liczb rzeczywi-
stych: jeżeli liczba x jest mniejsza od liczby y, to liczba y nie jest mniejsza od
a b
liczby x.
W reprezentacji graficznej relacja jest asymetryczna, jeżeli żadna tranzycja
nie ma tranzycji przeciwnej, nie ma też tranzycji identycznościowych (rysu-
nek 12).
5. Jeżeli dla każdych dwóch elementów x i y zbioru A, z faktu, że element x jest
w relacji z elementem y oraz y jest w relacji z x, wynika, że elementy x i y są
c d
identyczne, to powiemy, że relacja ´ jest antysymetryczna.
Symbolicznie:
Relacja ´ jest antysymetryczna wtw, gdy " [(x ´ y '" y ´ x) Ò! x = y]. Rysunek 12
x, y " A
Przykład 11
Przykładem relacji antysymetrycznej jest relacja  mniejsze lub równe
określona na liczbach rzeczywistych: jeżeli liczba x jest mniejsza lub rów-
na od liczby y oraz y jest mniejsze lub równe od x, to wynika z tego, że
x = y.
W reprezentacji graficznej relacja jest antysymetryczna, jeżeli żadna tranzy-
cja nie ma tranzycji przeciwnej. Tranzycje identycznościowe są dopuszczalne
(rysunek 13).
6. Jeżeli dla każdych trzech elementów x, y i z zbioru A, z faktu, że element
x jest w relacji z elementem y oraz y jest w relacji z elementem z wyni-
ka, że element x jest w relacji z elementem z, to powiemy, że relacja ´ jest
Rysunek 13
przechodnia.
Symbolicznie:
Relacja ´ jest przechodnia wtw, gdy " [(x ´ y '" y ´ z) Ò! x ´ z].
x,y,z"A
a b
Przykład 12
Przykładem relacji przechodniej jest relacja równoległości prostych na
płaszczyz
nie: jeżeli prosta p jest równoległa do prostej q oraz prosta q jest c
d
równoległa do prostej s, to prosta p jest również równoległa do prostej s.
Rysunek 14
15
a b
a
c
b
d
b
Na rysunku 14 pokazana jest reprezentacja graficzna relacji przechodniej. Rysunek
powstał z rysunku 13 przez dodanie odpowiednich (przerywanych) tranzycji, tak
d
c
aby finalna relacja spełniała warunek przechodniości.
7. Jeżeli dla każdych dwóch elementów x i y zbioru A, element x jest w relacji
z elementem y lub y jest w relacji z elementem x, to powiemy, że relacja ´ jest
spójna.
b
a
Można to zapisać symbolicznie:
Relacja ´ jest spójna wtw, gdy " (x ´ y (" y ´ x).
x,y"A
Przykład 13
Przykładem relacji spójnej jest relacja  mniejsze lub równe określona na
zbiorze liczb rzeczywistych: dla dowolnych dwóch liczb rzeczywistych x
i y liczba x jest mniejsza lub równa od liczby y lub liczba y jest mniejsza
lub równa od liczby x.
W reprezentacji graficznej relacja jest spójna, jeżeli między dwoma do-
wolnymi elementami istnieje co najmniej jedna tranzycja (w dowolnÄ…
stronę). Wszystkie tranzycje identycznościowe są również konieczne
(rysunek 15).
Rysunek 15
Oznaczmy przez id(A) relację identyczności na zbiorze A. Symbolicznie:
a b
id(A) = {(x, x) : x " A}.
Twierdzenie 6
Niech ´ Ä…" A × A bÄ™dzie relacjÄ… niepustÄ…. ZachodzÄ… nastÄ™pujÄ…ce wÅ‚asnoÅ›ci:
c d
(a) ´ jest zwrotna wtedy i tylko wtedy, gdy id(A) Ä…" ´,
(b) ´ jest przeciwzwrotna wtedy i tylko wtedy, gdy id(A) )" ´ = ",
(c) ´ jest symetryczna wtedy i tylko wtedy, gdy ´ = ´-1,
(d) ´ jest przechodnia wtedy i tylko wtedy, gdy ´ ż ´ Ä…" ´.
Dowód (a)
Należy wykazać, że jeżeli relacja ´ jest zwrotna, to id(A) Ä…" ´, oraz odwrotnie  że
jeżeli relacja ´ speÅ‚nia wÅ‚asność id(A) Ä…" ´, to jest zwrotna.
Ò!
JeÅ›li relacja jest zwrotna, to na podstawie definicji mamy: " (x ´ x). Zatem dla
x"A
dowolnego elementu x ze zbioru A mamy (x ´ x), czyli (x, x) " ´, zatem id(A) Ä…" ´.
Ð!
Załóżmy, że id(A) Ä…" ´. Dla dowolnego x " A mamy: (x, x) " ´, czyli relacja jest
zwrotna.
16
c d
a b
a b
c d
Szkic dowodu (b)
Ò!
Załóżmy nie wprost, że id(A) )" ´ `" ". Dla pewnej pary (x1, x1) mamy (x1, x1) " ´,
czyli x1 ´ x1. Otrzymujemy sprzeczność.
Ð!
Załóżmy nie wprost, że id(A) )" ´ = " oraz to, że relacja nie jest przeciwzwrotna.
Mamy dla pewnej pary: x1 ´ x1, czyli (x1, x1) " ´. Zatem id(A) )" ´ `" ". Otrzymuje-
my sprzeczność.
Szkic dowodu (c)
Ò!
Załóżmy, że relacja ´ jest symetryczna. Niech (x, y) " ´, mamy x ´ y. Z wÅ‚asnoÅ›ci
symetrii otrzymujemy y ´ x, czyli (y, x) " ´. Zatem (x, y) " ´-1. Mamy ´ Ä…" ´-1. In-
kluzji odwrotnej dowodzi siÄ™ analogicznie.
Ð!
Załóżmy, że ´ = ´-1.
Niech (x, y) " ´, wtedy z zaÅ‚ożenia (x, y) " ´-1, czyli (y, x) " ´.
Szkic dowodu (d)
Ò!
Załóżmy, że ´ jest przechodnia. Niech (x, y) " ´ ż ´, mamy x (´ ż ´) y. Z wÅ‚asno-
Å›ci zÅ‚ożenia relacji dla pewnego z mamy (x ´ z '" z ´ y). Z zaÅ‚ożonej przechodnioÅ›ci
mamy x ´ y, czyli (x, y) " ´. A wiÄ™c ´ ż ´ Ä…" ´.
Ð!
Załóżmy, że ´ ż ´ Ä…" ´. Niech x ´ y oraz y ´ z. Wtedy x(´ ż ´) z, a wiÄ™c (x, z) " ´ ż ´.
Z zaÅ‚ożenia (x, z) " ´, czyli x ´ z. Relacja ´ jest wiÄ™c przechodnia.
Twierdzenie 7
Prawdziwe są następujące własności niepustych relacji binarnych:
(a) zwrotność i przeciwzwrotność wykluczają się wzajemnie,
(b) symetria i asymetria wykluczajÄ… siÄ™ wzajemnie,
(c) każda relacja asymetryczna jest antysymetryczna,
(d) każda relacja spójna jest zwrotna,
(e) żadna relacja zwrotna nie jest asymetryczna.
Twierdzenie 8
Prawdziwe są następujące własności charakteryzujące związki między działaniami
na relacjach a ich rodzajami:
çÅ‚ suma i iloczyn dwóch relacji zwrotnych jest relacjÄ… zwrotnÄ…,
çÅ‚ suma i iloczyn dwóch relacji symetrycznych jest relacjÄ… symetrycznÄ…,
çÅ‚ suma i iloczyn dwóch relacji spójnych jest relacjÄ… spójnÄ….
17
Bibliografia
1. Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki
Częstochowskiej.
2. Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN, Warszawa.
3. Kuratowski K., Mostowski A., 1978: Teoria mnogości, PWN, Warszawa.
4. Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości
w zadaniach, PWN, Warszawa.
5. Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN, Warszawa.
6. Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria mnogości,
Warszawa.
Bibliografia stron WWW
7. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.
Witryna internetowa. http://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan
z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).
18