Niech f : X → Y będzie dowolną funkcją. Wówczas dla dowolnych zbiorów A, B ⊂ X:
a) f (A ∪ B) = f (A) ∪ f (B),
b) f (A ∩ B) ⊂ f (A) ∩ f (B),
c) f (A) \ f (B) ⊂ f (A \ B),
oraz dla dowolnych zbiorów C, D ⊂ Y :
a) f −1(C ∪ D) = f −1(C) ∪ f −1(D),
b) f −1(C ∩ D) = f −1(C) ∩ f −1(D),
c) f −1(C \ D) = f −1(C) \ f −1(D).
1
2
Relacją n-argumentową nazywamy podzbiór % ⊂ X1×X2×. . .×Xn.
Jeśli % ⊂ X × Y jest relacją dwuargumentową (binarną), to za-miast (x, y) ∈ % piszemy x%y.
Relacją binarną określoną w zbiorze X nazywamy podzbiór % ⊂
X × X.
Funkcje jako relacje. Funkcją nazywamy relację binarną % ⊂
X × Y taką, że dla każdego elementu x ∈ X jest jeden i tylko jeden element y ∈ Y spełniający warunek (x, y) ∈ %:
∀x∈X∃!y∈Y (x, y) ∈ %.
3
Rozważmy relację binarną % określoną w zbiorze X: % ⊂ X × X.
Mówimy, że relacja % jest:
– zwrotna, jeśli ∀x∈Xx%x,
– przeciwzwrotna, jeśli ∀x∈X ∼ x%x,
– symetryczna, jeśli ∀x,y∈Xx%y ⇒ y%x,
– asymetryczna (antysymetryczna), jeśli ∀x,y∈Xx%y ⇒∼ y%x,
– słabo antysymetryczna, jeśli ∀x,y∈Xx%y ∧ y%x ⇒ x = y,
– spójna, jeśli ∀x,y∈Xx%y ∨ y%x ∨ x = y,
– przechodnia, jeśli ∀x,y,z∈Xx%y ∧ y%z ⇒ x%z.
4
Rozważmy następujące relacje binarne w zbiorze R:
„ x < y”,
„ x 6 y”,
„ |x| = |y|”
oraz następujące relacje binarne w zbiorze N1:
„ x i y są tej samej parzystości”,
„ y = x2”,
„ x | y”.
5
x < y
x 6 y |x| = |y|
zwrotność
−
+
+
przeciwzwrotność
+
−
−
symetria
−
−
+
asymetria
+
−
−
słaba antysymetria
+
+
−
spójność
+
+
−
przechodniość
+
+
+
relacja w N1
x i y stsp
y = x2
x | y
zwrotność
+
−
+
przeciwzwrotność
−
−
−
symetria
+
−
−
asymetria
−
−
−
słaba antysymetria
−
+
+
spójność
−
−
−
przechodniość
+
−
+
6
Rozważmy relację binarną % określoną w zbiorze skończonym X. Możemy narysować graf, którego wierzchołki są oznaczone elementami tego zbioru. Krawędź grafu o początku x i końcu y (strzałkę prowadzącą z x do y) rysujemy wtedy i tylko wtedy, gdy x%y.
7
Przy
każdym
wierzchołku
jest pętla.
przeciwzwrotność
Przy
żadnym
wierzchołku
nie ma pętli.
symetria
Na
każdej
krawędzi
są
strzałki w obie strony.
asymetria
Na
każdej
krawędzi
jest
strzałka tylko w jedną stro-
nę. Nie ma pętli.
słaba antysymetria
Na
każdej
krawędzi
jest
strzałka tylko w jedną stro-
nę. (Mogą być pętle.)
spójność
Każde dwa (różne) wierz-
chołki są połączone krawę-
dzią.
8
Macierz relacji % tworzymy w ten sposób, że wiersze i kolumny oznaczamy elementami zbioru X. Na przecięciu wiersza oznaczo-nego elementem x i kolumny oznaczonej elementem y stawiamy 1, jeśli x%y, a 0 w przeciwnym wypadku.
Przykłady.
Niech X = {1, 2, 3, 4, 5}.
9
x | y
x\y
1 2 3 4 5
x\y
1 2 3 4 5
1
0 1 1 1 1
1
1 1 1 1 1
2
0 0 1 1 1
2
0 1 0 1 0
3
0 0 0 1 1
3
0 0 1 0 0
4
0 0 0 0 1
4
0 0 0 1 0
5
0 0 0 0 0
5
0 0 0 0 1
y = x2
x i y stsp
x\y
1 2 3 4 5
x\y
1 2 3 4 5
1
1 0 0 0 0
1
1 0 1 0 1
2
0 0 0 1 0
2
0 1 0 1 0
3
0 0 0 0 0
3
1 0 1 0 1
4
0 0 0 0 0
4
0 1 0 1 0
5
0 0 0 0 0
5
1 0 1 0 1
10
Na głównej przekątnej są same je-
dynki.
przeciwzwrotność
Na głównej przekątnej są same ze-
ra.
symetria
Macierz jest symetryczna (wzglę-
dem głównej przekątnej).
asymetria
Na
miejscach
symetrycznych
(względem
głównej
przekątnej)
nie
ma
dwóch
jedynek.
Na
głównej przekątnej są same zera.
słaba antysymetria
Na
miejscach
symetrycznych
(względem
głównej
przekątnej)
nie ma dwóch jedynek.
spójność
Na
miejscach
symetrycznych
(względem
głównej
przekątnej)
nie ma dwóch zer.
11
12
Relację binarną % określoną w zbiorze X nazywamy relacją po-rządkującą (lub relacją częściowego porządku), jeśli jest zwrotna, słabo antysymetryczna i przechodnia. Zbiór X z określoną w nim relacją porządkującą nazywamy zbiorem częściowo uporządkowanym.
Relację porządkującą oznaczamy zazwyczaj symbolem „ 4”. Mó-
wimy wówczas, że (X, 4) jest zbiorem częściowo uporządkowanym. Mamy zatem warunki:
∀x∈Xx 4 x, ∀x,y∈Xx 4 y ∧ y 4 x ⇒ x = y,
∀x,y,z∈Xx 4 y ∧ y 4 z ⇒ x 4 z.
13
Jeśli „ 4” jest relacją częściowego porządku, to możemy określić relację „ ≺” następująco:
x ≺ y ⇔ x 4 y ∧ x 6= y.
Jeśli x ≺ y, to mówimy, że element x jest mniejszy od y, a y jest większy od x. Jeśli x 4 y, to mówimy, że element x jest mniejszy lub równy y, a y jest większy lub równy x.
14
Niech (X, 4) będzie zbiorem częściowo uporządkowanym. Element x ∈ X nazywamy:
– najmniejszym, jeśli jest mniejszy od pozostałych elementów:
∀y∈Xx 4 y;
– największym, jeśli jest większy od pozostałych elementów:
∀y∈Xy 4 x;
– minimalnym, jeśli nie ma elementów od niego mniejszych:
∀y∈Xy 4 x ⇒ y = x;
– maksymalnym, jeśli nie ma elementów od niego większych:
∀y∈Xx 4 y ⇒ y = x.
15
el. minimalne
el. maksymalne
({1, 2, 3, 4, 5}, 6)
1 – najmniejszy
5 – największy
({1, 2, 3, 4, 5}, |)
1 – najmniejszy
3, 4, 5
(N1, |)
1 – najmniejszy
nie ma
(N2, |)
liczby pierwsze
nie ma
(2{a,b,c}, ⊂)
∅
{a, b, c}
(2{a,b,c} \ {∅, {a, b, c}}, ⊂)
{a}, {b}, {c}
{a, b}, {a, c}, {b, c}
Zadanie. Narysuj kilka diagramów zbiorów częściowo uporządkowanych, wskaż elementy minimalne, maksymalne, najmniejsze, największe.
16
Uwaga. Element najmniejszy (jeśli istnieje) jest jedynym elementem minimalnym. Analogicznie, element największy jest jedynym maksymalnym. (Jedyny element minimalny nie musi być elementem najmniejszym.)
17
Definicja.
Relację porządkującą, która jest spójna, nazywamy relacją porządku liniowego. Oznacza to, że spełniony jest warunek
∀x,y∈Xx 4 y ∨ y 4 x.
Przykłady:
(R, 6), ({1, 2, 4, 8}, |), ({{a}, {a, b}, {a, b, c}}, ⊂).
W zbiorze liniowo uporządkowanym istnieje co najwyżej jeden element minimalny. Jeśli taki element istnieje, to jest elementem najmniejszym. Analogiczna własność zachodzi oczywiście dla elementów maksymalnych.
18
Niech (A, 4) będzie zbiorem liniowo uporządkowanym. W zbiorze słów nad alfabetem A określamy relację porządku leksykograficz-nego „ 4lex” w sposób następujący:
a
1 ≺ b1
∨
a1a2 . . . am 4lex b1b2 . . . bn ⇔
a1 = b1, . . . , ak−1 = bk−1, ak ≺ bk
∨
a1 = b1, . . . , am = bm, m 6 n.
Relacja „ 4lex” jest porządkiem liniowym w zbiorze A∗.
19
Definicja. Porządek liniowy „ 4” w zbiorze X nazywamy dobrym, jeśli w każdym niepustym podzbiorze A ⊂ X istnieje element najmniejszy.
Przykłady zbiorów z porządkowanych w sposób dobry: N z relacją „ 6”, dowolny zbiór skończony liniowo uporządkowany.
Przykłady zbiorów z porządkiem liniowym, który nie jest dobry: Z, Q R, R+, [0, +∞) z relacją „ 6”.
Twierdzenie Zermelo (bez dowodu). Każdy zbiór można dobrze uporządkować.
20