Logika i Teoria Mnogości

Wykład 3

1

Relacje

Tematem są relacje, czyli pewne związki pomiędzy obiektami. Mówimy, że elementy
są w relacji, jeśli jest między nimi pewna zależność. Relacje definiujemy jako
podzbiory iloczynu kartezjańskiego zbiorów.

Produkt – iloczyn kartezjański zbiorów

Def. 1. Parę uporządkowaną elementów a i b oznaczamy (a, b) lub ha, bi, a –
pierwsza współrzędna, b – druga współrzędna. Para uporządkowana ma własność:
(a, b) = (c, d) ⇔ a = c ∧ b = d.

Uwaga: Istotne jest rozróżnienie kolejności elementów. Można wprowadzić inną
definicję (Kuratowskiego): (a, b) = {{a}, {a, b}}.
Podobnie można zdefiniować n-tki uporządkowane (a

1

, a

2

, . . . , a

n

) jako obiekty

rozróżniające swoje kolejne współrzędne.

Def. 2. Iloczynem kartezjańskim (produktem) zbiorów A i B nazywamy zbiór

A × B =







{(a, b) : a ∈ A ∧ b ∈ B}, gdy A 6= ∅ ∧ B 6= ∅

∅,

gdy A = ∅ ∨ B = ∅

Fakt: Jeżeli A i B są zbiorami skończonymi, A ma m elementów, a B ma n
elementów, to A × B ma m · n elementów.

Własności produktu

• X × Y 6= Y × X

brak przemienności

• (X × Y ) × Z = X × (Y × Z)

łączność

• X × (Y ? Z) = (X × Y ) ? (X × Z),

? oznacza działanie ∪, ∩ lub \.

Określenie relacji

Def. 3. Relacją n-argumentową nazywamy zbiór R ⊆ X

1

×X

2

×. . .×X

n

. Zbiór

X

1

∪ X

2

∪ . . . ∪ X

n

nazywamy polem relacji. Jeśli X

1

= X

2

= . . . = X

n

= X, to

mówimy o relacji w zbiorze X.

Przypadki szczególne:

• n = 1, wtedy R ⊆ X, relacja 1-członowa jest podzbiorem zbioru X,

• n = 2, to R ⊆ X × Y nazywamy relacją binarną.

Relacje binarne

Niech R ⊆ X × Y . Stosujemy równoważne zapisy (x, y) ∈ R oraz x R y które
czytamy: x jest w relacji R z elementem y.
Wykresem relacji R ⊆ X ×Y nazywamy zbiór wszystkich par (x, y) będących
w relacji R.

Logika i Teoria Mnogości

Wykład 3

2

Definiujemy ponadto:

• zaprzeczenie relacji R: x 6R y ⇔ ¬ x R y;

• dziedzina relacji R to zbiór: domR = d

R

:= {x ∈ X : ∃ y ∈ Y x R y};

• przeciwdziedzina relacji R to zbiór: d

−1

R

:= {y ∈ Y : ∃ x ∈ X x R y};

• relacja odwrotna do R to relacja: R

−1

:= {(y, x) ∈ Y × X : (x, y) ∈ R},

y R

−1

x ⇔ x R y,

d

R

−

1

= d

−1

R

,

d

−1
R

−1

= d

R

;

• złożenie relacji R i S : jeśli R ⊆ X ×Y, S ⊆ Y ×Z, to S ◦R = U ⊆ X ×Z

x U z ⇔ ∃ y ∈ Y (x R y ∧ y S z). Składanie relacji nie jest przemienne, ale
jest łączne, to znaczy: R ◦ (S ◦ T ) = (R ◦ S) ◦ T .

Relacje szczególne

1. Relacja pełna (każdy x jest w relacji z każdym y) – R = X × Y ;

2. Relacja pusta (żadne elementy nie są w relacji) – R = ∅ ⊆ X × Y ;

3. Relacja identyczności (równości) – I

X

= id

X

:

I

X

⊆ X ×X, x I

X

y ⇔ x = y,

R

−1

◦R = I

X

, R◦R

−1

= I

Y

, R◦I

X

= R.

Podstawowe własności relacji

Def. 4. O relacji R ⊆ X ×Y mówimy, że jest:

1. zwrotna ⇔ ∀x ∈ X x R x

2. przeciwzwrotna ⇔ ∀x ∈ X ¬ x R x

3. przechodnia ⇔ ∀x, y, z [(x R y ∧ y R z) ⇒ x R z]

4. symetryczna ⇔ ∀x, y (x R y ⇒ y R x)

5. (słabo)antysymetryczna ⇔ ∀x, y [(x R y ∧ y R x) ⇒ x = y]

6. silnie antysymetryczna ⇔ ∀x, y (x R y ⇒ ¬ y R x)

7. spójna ⇔ ∀x, y (x R y ∨ y R x ∨ x = y).

Operacje na relacjach

Niech R

1

, R

2

⊆ X

2

– relacje. Definiujemy następujące operacje:

• suma relacji – R

1

∪ R

2

: x (R

1

∪ R

2

) y ⇔ x R

1

y ∨ x R

2

y;

• przecięcie relacji – R

1

∩ R

2

: x (R

1

∩ R

2

) y ⇔ x R

1

y ∧ x R

2

y;

• dopełnienie relacji – X

2

\ R

1

: x (X

2

\ R

1

) y ⇔ ¬ x R

1

y.

Logika i Teoria Mnogości

Wykład 3

3

Relacje równoważności

Relacje równoważności pozwalają utożsamiać (grupować) pewne obiekty mające
wspólną wybraną cechę.

Def. 5. Relacja % w zbiorze X jest relacją równoważności, jeśli jest zwrotna,
symetryczna i przechodnia.

Stosujemy oznaczenia: x ∼ y, x ≈ y, x ≡ y.

Def. 6. Niech % – relacja równoważności w zbiorze X 6= ∅.
Klasą abstrakcji elementu x ∈ X względem relacji % nazywamy zbiór:

[x]

%

= {y ∈ X : x % y},

a ∈ [x]

%

⇔ x % a

Każdy element a ∈ [x]

%

jest reprezentantem tej klasy abstrakcji.

Def. 7. Zbiorem ilorazowym relacji % nazywamy zbiór wszystkich klas abstrakcji
względem relacji %:

X/

%

:= {[x]

%

: x ∈ X}

Tw. 1. Jeżeli % jest relacją równoważności w zbiorze X, to:

1. ∀x ∈ X x ∈ [x]

%

2. ∀x, y ∈ X ([x]

%

= [y]

%

⇔ x % y)

3. ∀x, y ∈ X ([x]

%

6= [y]

%

⇒ [x]

%

∩ [y]

%

= ∅)

4.

S

x∈X

[x]

%

= X

5. ∀x, y ∈ X y ∈ [x]

%

⇒ x ∈ [y]

%

.

Def. 8. Niech X 6= ∅. Rodzinę A = {A

i

:

i ∈ I} ⊆ 2

X

nazywamy podziałem

zbioru X, jeśli spełnione są następujące warunki:

1. ∀A

i

∈ A A

i

6= ∅

2. ∀A

i

, A

j

∈ A A

i

6= A

j

⇒ A

i

∩ A

j

= ∅

3.

S

i∈I

A

i

= X.

Tw. 2. Jeżeli % jest relacją równoważności w zbiorze X, to zbiór ilorazowy X/

%

jest podziałem zbioru X, ponadto jeśli A jest podziałem zbioru X, to relacja %

A

na

zbiorze X określona następująco:

x %

A

y ⇔ ∃A

i

∈ A (x ∈ A

i

∧ y ∈ A

i

)

jest relacją równoważności.