Wst� do logiki i teorii mnogości, wyklad 9
ep
Marek Balcerzak
1
Relacje i ich wlasności
Definicja 1. Niech dane b� a zbiory X i Y . Relacja (dwuargumentow�
ed� � a)
mi� elementami zbiorów X i Y nazywamy dowolny podzbiór � �" X � Y .
edzy
Jeśli Y = X, to mówimy, że � jest relacj� na zbiorze X.
a
Uwaga 1. Dla relacji � �" X � Y stosuje si� cz� zapis x�y. Mówimy
e esto
wtedy, że element x zbioru X jest w relacji � z elementem y zbioru Y .
Funkcja f �" X � Y jest szczególnym rodzajem relacji.
Przyklad 1. " Relacja mniejszości < na R
x�y �! x < y;
Relacj� t� utożsamiamy ze zbiorem {(x, y) " R: x < y}.
e e
" Niech X = ". Rozważmy relacje �1, �2, �3 na P(X):

A�1B �! A )" B = "
A�2B �! A �" B
A�3B �! A B jest zbiorem skończonym.
" Relacja podzielności na N
m|n �! ("k " N) n = mk.
Definicja 2. (a) Niech dane b� a relacje S �" X � Y oraz T �" Y � Z.
ed�
Relacj� T ć% S dan� wzorem
e a
x(T ć% S)z �! ("y " Y )(xSy '" yT z)
nazywamy zlożeniem relacji S i T .
(b) Jeśli S �" X � Y jest dan� relacja, to relacj�
a � e
S-1 = {(y, x) " Y � X : (x, y) " S}
nazywamy odwrotn� do relacji S.
a
Definicja 3 (Rodzaje relacji). Niech � b� relacja na zbiorze X = ".
edzie �
Mówimy, że:
� jest zwrotna, gdy ("x " X) x�x
� jest przeciwzwrotna, gdy ("x " X) <" x�x
� jest przechodnia, gdy ("x, y, z " X) (x�y '" y�z) �! x�z
� jest symetryczna, gdy ("x, y " X) x�y �! y�x
� jest slabo antysymetryczna, gdy ("x, y " X) (x�y '" y�x) �! x = y
� jest przeciwsymetryczna, gdy ("x, y " X) (x�y �!<" y�x)
� jest spójna, gdy ("x, y " X) (x�y (" y�x)
2
rodzaj X - zbiór ludzi X = R P(X) P(X) X = N
relacji być ojcem d" A )" B = " A �" B m|n
zwrotna - + - + +
przeciwzwrotna + - - - -
przechodnia - + - + +
symetryczna - - + - -
slabo antysymetr. + + - + +
przeciwsymetr. + - - - -
spójna - + - - -
Definicja 4. Relacj� na zbiorze X, która jest zwrotna, symetryczna i prze-
e
chodnia, nazywamy relacj� równoważności.
a
3