Zakład Logiki i Epistemologii
Instytut Filozofii i Socjologii UKW
w Bydgoszczy
ul. Ogińskiego 16
Wykład 15
Rachunek zbiorów i relacji (3)
Ponieważ pojęcie pary uporządkowanej zakłada aksjomat wyboru, więc tym samym pojęcie iloczynu kartezjańskiego też go zakłada.
Uogólnienie pojęcia iloczynu i sumy dwóch zbiorów na iloczyn i sumę rodziny zbiorów
Pojęcie sumy i iloczynu dwóch zbiorów można uogólnić na dowolne zbiory (klasy) zbiorów.
Zamiennie będą używane następujące terminy: zbiór zbiorów, klasa zbiorów, rodzina zbiorów.
Def. 1 Uogólnienie pojęcia sumy zbiorów
x ∈ ∪A∈K h(A) ≡ VA∈K x ∈ h(A)
h – zmienna reprezentująca funktory, które wraz z jednym argumentem "A"
tworzą wyrażenia tej samej kategorii składniowej, co zmienna "A"
reprezentująca nazwy zbiorów.
Symbol ∪A∈K h(A) oznacza sumę wszystkich zbiorów h(A) takich, że A ∈ K. W
myśl tej definicji sumą jest zbiór złożony tylko z tych ele,mentów , które należą do przynajmniej jednego zbioru h(A), takiego, że A ∈K.
Ex.
h – dopełnienie zbioru
x ∈ ∪A∈K –A ≡ VA∈K x ∈ –A
W myśl definicji, sumą dopełnień elementów rodziny K jest zbiór złożony tylko z tych przedmiotów , które należą do dopełnienia przynajmniej jednego elementu rodziny K.
Ex.
h – I(A)=A, stałą I podstawiamy za zmienną I i zastępujemy I(A) przez A.
1
Zatem zbiór ∪A∈K A składa się tylko z tych przedmiotów, które należą przynajmniej do jednego elementu rodziny K.
Def. 2 Uogólnienie pojęcia iloczynu zbiorów.
x ∈ ∩ A∈K h(A) ≡ ΛA∈K x ∈h(A)
Wg tej definicji iloczynem wszystkich zbiorów h(A), takich, że A ∈ K, jest zbiór złożony z tych i tylko tych przedmiotów, które należą do każdego zbioru h(A), takiego, że A ∈ K.
Ex.
Analogicznie jak wyżej
h – dopełnienie zbioru
x ∈ ∩A∈K –A ≡ ΛA∈K x ∈ –A
Iloczyn dopełnień elementów rodziny zbirów K jest to zbiór złożony tylko z tych przedmiotów, które należą do dopełnienie każdego elementu rodziny K.
Ex.
h – I(A)=A, stałą I podstawiamy za zmienną I i zastępujemy I(A) przez A.
x ∈ ∩A∈K A ≡ ΛA∈K x ∈A
Iloczyn elementów rodziny zbiorów K, czyli po prostu iloczyn rodziny zbiorów K, jest to zbiór złożony tylko z tych przedmiotów, które należą do każdego elementu rodziny K, a więc do każdego zbioru tej rodziny.
Widzimy więc, że suma i iloczyn dwóch zbiorów jest przypadkiem szczególnym sumy i iloczynu rodziny zbiorów, na którą to rodzinę składają się tylko te dwa zbiory.
Dla uogólnionych sum i iloczynów zbiorów można udowodnić pewne prawa będące uogólnieniami odpowiednich praw podanych dla sumy i iloczynu dwóch zbiorów.
Twierdzenie
Każdy element rodziny K jest zawarty w sumie zbiorów tej rodziny.
A ∈ K → A ⊂ ∪A∈K A
Dowód
2
A ∈ K
z.
1.1
x ∈ A
z.d.
1.2
VA∈K x ∈ A
doł. kw. szczeg. o ogr. zakresie 1, 1.1 (DK: 1, 1.1) 1.3 x ∈ ∪A∈K A
def. ∪, 1.2
2.
x ∈ A → x ∈ ∪A∈K A
1.1 → 1.3
3.
Λx (x ∈ A → x ∈ ∪A∈K A)
DΛ: 2
A ⊂ ∪A∈K A
df ⊂, 3
Twierdzenie
Iloczyn zbiorów rodziny K jest zawarty w każdym z tych zbiorów Λ ∩
A∈K
A∈K A ⊂ A
Dowód
1.
A ∈ K
z. (zob. kw. ogólny o ogran. zakresie)
1.1
x ∈ ∩A∈K A z.d.
1.2
ΛA∈K x ∈A
def.∩ 1.1
1.3
A ∈ K → x ∈A
opuszcz. kw. og pgr. zakresie 1.2
1.4
x ∈ A
1.3, 1
x ∈ ∩A∈K A 1.1 → 1.4, DΛ, Def. ∩
Przypadkiem szczególnym powyższych definicji uogólnionej sumy i uogólnionego iloczynu zbiorów są działania nieskończone 1 :
Niech
(*)
A1, ... An, ....
będzie dowolnym zbiorem ciągów i niech
Y=ϕ(K)
będzie funkcją określoną dla każdego wyrazu ciągu (*), której wartościami są zbiory.
Def. 3 (Przypadek szczególny Def. 1)
∞
x ∈ ϕ ( X ) ⇔ ∃
x
∈
∈ ϕ { X }
i
i N
i
n=1
Def. 4 (Przypadek szczególny Def. 2)
1
Słupecki, Borkowski, Elementy logiki matemtycznej i teorii mnogości, s. 158-159, D4.1, D4.2, D4.3, D4.4
3
x ∈ ϕ ( X ) ⇔ ∀
x
∈
∈ ϕ { X }
i
i N
i
i=1
Zbiór
∞ ϕ ( X )
i
n 1
=
nazywamy sumą wyrazów ciągu
ϕ(X1), ... , ϕ(X2), ...
Zbiór
∞ ϕ ( X )
i
i= 1
nazywamy iloczynem wyrazów ciągu
ϕ(X1), ... , ϕ(X2), ...
Należą do niego tylko te elementy, które należą do każdego ze zbiorów.
Twierdzenie
Jeśli x ≠ y, to zbiór {x,y} jest parą nieuporządkowaną (gdyż zbiór {x,y}={y,x}) Dowód
z ∈{x,y} ≡ z=x ∨ z=y ≡ z=y ∨ z=x ≡ z ∈{y,x}
prawo p ≡ p ∨ p
Relacje
Relacje Borkowski, Logika formalna, s. 173.
Iloczyn kartezjański
Def. <x,y> ∈ A × B ≡ (x ∈ A ∧ x ∈ B) Relacja 2-członowa jest to zbiór pewnych par uporządkowanych.
4
Czyli relacją R między elementami zbiorów A i B, niekoniecznie równych, nazywamy każdy podzbiór iloczynu kartezjańskiego A × B, Jako zmiennych reprezentujących nazwy relacji będziemy używali liter R, S, Q,
... .
Kontekst wskazuje, czy mamy do czynienia z relacją n-członową.
Zamiast wyrażenia <x,y> ∈ R będziemy używać wyrażenia xRy.
xRy = <x,y> ∈ R
xRy = R(x,y)
R ⊂ A × B
Dziedzina
x ∈ D(R) ≡ Vy xRy
dziedzina relacji R jest zbiór wszystkich przedmiotów, które są w jakiejśc relacji R przynajmniej do jednego przedmiotu Przeciwdziedzina
x ∈ (R) ≡ Vx xRy
zbiór wszystkich przedmiotów do których, jakiś przedmiot pozostaje w relacji R.
Pole relacji R
C(R) = D(R) ∪ (R)
Jeśli
R ⊂ X1 × ... × Xn
D( R) = V
R( y ,..., y , y ,..., y ) 1
i− 1
i+ 1
n
y ,.
1 .., yi− ,
1 yi= ,
1 yn
Def. iloczynu względnego
xR Sy ≡ ∃ ( zRx ∧ zSy) z
Ex.
x jest ojcem z
y jest matką z
5
Warunki bycia relacją równoważności 1) Zwrotność refl(R,A) relacji
Λx∈A xRx
2) Symetria sym(R,A) relacji
Λx,y ∈A (xRy → yRx)
3) Przechodniość trans(R,A) relacji
Λx,y,z ∈A (xRy ∧ yRz → xRz)
Relacja R na zbiorze A jest relacją równoważności aeq(R.A) ≡ refl(R,A) ∧ sym(R,A) ∧ trans(R,A) Klasa abstrakcji
[x]R,A = {y ∈ A : yRx}
Element x wyznacza klasę abstrakcji
Każda relacja równoważności rozbija dany zbiór na klasy abstrakcji. Każdy zbiór klas wyznacza relację równoważności.
1) Zasada abstrakcji
Rodzina klas abstrakcji relacji równoważności R w zbiorze A jest podziałem zbioru A (tzn, klasy abstrakcji są niepuste, rozłączne, suma jest róna temu zbiorowi.
2) Definicje przez abstrakcję
Istnieje możliwość definiowania pewnych własności jako klas abstrakcji jakiejś relacji równoważności.
Ex
Długość odcinka x – wspólna własnośćprzysługująca odcinkom przystającym do x.
Długość odcinka – klasa abstrakcji relacji przystawania w zbiorze odcinków wyznaczona przez odcinek x.
Ogólnie: długości odcinków są to klasy abstrakcji relacji przystawania w zbiorze odcinków.
Ex
Kierunek prostej x na płaszczyźnie – klasa abstrakcji relacji równoległości, wyznaczona przez element x w zbiorze prostych.
6
Liczba kardynalna zbioru A – jest to ilość elementów w zbiorze A.
Mamy tu do czynienia z podwójną abstrakcją:
- abstrakcja od porządku
- abstrakcja od jakości elementów
Stąd dwie kreski nad zbiorem
= A
a) Wspólna własność wszystkich zbiorów które są z nim równoliczne b) klasa abstrakcji relacji równoliczności wyznaczona przez zbiór A w rodzinie zbiorów.
Liczby kardynalne zbiorów – to klasy abstrakcji relacji równoliczności w zbiorze zbiorów
Liczby naturalne są liczbami kardynalnymi zbiorów skończonych.
Pojęcie równoliczności jest wcześniejsze od pojęcia liczby (np. pasterz liczył owce odkładając kamienie na stos).
Relacje porządkujące
Relacja tworzy częściowy porządek, gdy jest zwrotna, antysymetryczna i przechodnia
1) Asymetria as(R,A)
Λx,y ∈A (xRy → ~yRx)
2) Antysymetria antys(R,A)
Λx,y ∈A (xRy ∧ yRx → x=y)
3) spójność con(R,A)
Λx,y ∈A (xRy ∨ yRz → xRz)
Ex. Relacja podzielności w zbiorze
Def.
Relacja R liniowo porządkuje zbiór A wttw, gdy relacja jest zwrotna, antysymetryczna, przechodnia i spójna
Ex. W zbiorze liczb rzeczywistych R liniowo porządkuje relacja ' ≤ '
7
^
R
x y ⇔ yRx
Twierdzenie
Konwers konwersu relacji jest równy tej relacji Twierdzenie
Dziedzina konwersu relacji jest równa przeciwdziedzinie relacji Uwagi historyczne
Po raz pierwszy o uporządkowaniu zbioró mówił Cantor a) Cantora relacja porządkująca
1.
~zRx
2.
xRy → ~yRx
3.
Λx,y,z ∈A (xRy ∧ yRz → xRz)
4.
x=y ∨ xRy ∨ yRx
b) Pojęcie relacji porządkującej i częściowo porządkującej
- porzadkująca: 1-4
- cz. porządkująca: 1-3
8