Logika i teoria mnogości – Wykład 2
1
Teoria mnogo
ści
Teoria mnogości to dział matematyki zajmujący się badaniem ogólnych
własności zbiorów niezależnie od natury elementów, z których się składają.
Twórcą tej teorii był matematyk niemiecki Georg Cantor (1845 – 1918).
Pojęcia pierwotne tej teorii to zbiór oraz przynależność do zbioru.
Definiujemy następujące podstawowe pojęcia:
•
- zbiór pusty (nie ma żadnego elementu,
∅
∉
∀
x
x
)
•
Relacja inkluzji (zawierania) -
)
(
B
x
A
x
B
A
∈
⇒
∈
⇔
⊆
•
Równość zbiorów -
)
(
)
(
A
B
B
A
B
x
A
x
x
B
A
⊆
∧
⊆
⇔
∈
⇔
∈
∀
⇔
=
Uwaga: Zbiór pusty jest tylko jeden i jest on podzbiorem dowolnego zbioru.
Działania na zbiorach:
•
Suma -
}
:
{
B
x
A
x
x
B
A
∈
∨
∈
=
∪
;
•
Iloczyn -
}
:
{
B
x
A
x
x
B
A
∈
∧
∈
=
∩
;
•
Różnica -
}
:
{
}
:
{
\
B
x
A
x
B
x
A
x
x
B
A
∉
∈
=
∉
∧
∈
=
;
•
Dopełnienie – oznaczenia A’ = -A = X\A (
)
'
A
x
A
x
∉
⇔
∈
.
Uwaga: Elementy zbiorów mogą też być zbiorami.
Sposoby określania zbiorów
• Wypisanie elementów zbioru, np. {a
1
, a
2
, …,a
n
};
• Określenie zbioru przy pomocy funkcji zdaniowej – gromadzenie
elementów mających wspólną cechę opisaną pewną funkcją zdaniową.
Ogół elementów x, które mają własność W(x) oznaczamy
)}
(
:
{
x
W
x
.
Uwaga: Może się zdarzyć, że opisana w taki sposób klasa obiektów nie
jest zbiorem (przykład – antynomia Russela). Aby uniknąć takiej
sytuacji wybieramy elementy spełniające określoną własność spośród
ustalonego wcześniej zbioru X. Tworzymy nowy zbiór
)}
(
:
{
x
W
X
x
∈
.
• Określenie zbioru jako obraz zbioru wyznaczony przez funkcję -
}
:
)
(
{
)
(
A
a
a
f
x
A
f
∈
=
=
.
Logika i teoria mnogości – Wykład 2
2
W
łasności działań i relacji na zbiorach
Niech X – ustalony zbiór - przestrzeń (tzn. rozważamy tylko elementy i
podzbiory tego zbioru) oraz A, B, C
X.
• Własności relacji inkluzji
1. A
A
zwrotność
2. A
B B C A C przechodniość
3. A
B B A A = B
antysymetryczność
• Własności działań
1.
A
B
B
A
A
B
B
A
∩
=
∩
∪
=
∪
przemienność
2.
C
B
A
C
B
A
C
B
A
C
B
A
∩
∩
=
∩
∩
∪
∪
=
∪
∪
)
(
)
(
)
(
)
(
łączność
3.
)
(
)
(
)
(
)
(
)
(
)
(
C
A
B
A
C
B
A
C
A
B
A
C
B
A
∪
∩
∪
=
∩
∪
∩
∪
∩
=
∪
∩
rozdzielność
4.
)
\
(
)
\
(
)
(
\
)
\
(
)
\
(
)
(
\
B
C
A
C
B
A
C
B
C
A
C
B
A
C
∪
=
∩
∩
=
∪
, stąd
'
'
)'
(
'
'
)'
(
B
A
B
A
B
A
B
A
∪
=
∩
∩
=
∪
prawa de Morgana
5.
;
'
,
\
,
,
,
)'
'
(
,
'
,
\
,
,
∅
=
∩
=
∅
∅
=
∅
∩
=
∅
∪
=
=
∪
∅
=
=
∩
=
∪
A
A
A
A
A
A
A
A
A
X
A
A
A
A
A
A
A
A
A
A
6. Monotoniczność sumy i iloczynu:
∩
⊆
∩
∪
⊆
∪
⇒
⊆
∧
⊆
1
1
1
1
1
1
B
A
B
A
B
A
B
A
B
B
A
A
7.
'
'
\
\
A
B
A
C
B
C
B
A
⊆
∧
⊆
⇒
⊆
8.
B
A
A
B
A
∪
⊆
⊆
∩
9. Następujące warunki są równoważne:
∅
=
⇔
=
∩
⇔
=
∪
⇔
⊆
B
A
A
B
A
B
B
A
B
A
\
.
Zbiór pot
ęgowy
Def. 1. Niech A będzie dowolnym zbiorem. Zbiorem potęgowym zbioru A
nazywamy zbiór wszystkich jego podzbiorów. Stosujemy oznaczenia:
}
:
{
:
)
(
2
A
B
B
A
A
⊆
=
℘
=
.
Uwaga: Zawsze
).
(
,
A
A
℘
∈
∅
Fakt.
).
(
)
(
B
A
B
A
℘
⊆
℘
⇒
⊆
Logika i teoria mnogości – Wykład 2
3
Iloczyn kartezja
ński
Def. 2. Parę uporządkowaną elementów a i b oznaczamy <a,b> lub (a,b),
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-ki uporządkowane (a
1
, a
2
, …,a
n
) jako obiekty
rozróżniające swoje kolejne współrzędne.
Def. 3. Iloczynem kartezjańskim zbiorów A i B (produktem) nazywamy zbiór
∅
=
∨
∅
=
∅
∅
≠
∧
∅
≠
∈
∧
∈
=
×
B
A
gdy
B
A
gdy
B
b
A
a
b
a
B
A
}
:
)
,
{(
Fakt: Jeżeli X i Y są zbiorami skończonymi, X ma m elementów, a Y ma n
elementów, to X
Y jest skończony i ma mn elementów.
Własności produktu
•
X
Y
Y
X
×
≠
×
•
)
(
)
(
Z
Y
X
Z
Y
X
×
×
=
×
×
•
◊
×
◊
×
=
◊
×
),
(
)
(
)
(
Z
X
Y
X
Z
Y
X
- oznacza działanie
∩
∪
,
lub \.
Dzia
łania nieskończone – uogólnione sumy i iloczyny zbiorów
Niech
∅
≠
X
- dowolna przestrzeń,
∅
≠
T
- dowolny zbiór (zbiór indeksów).
Def. 4. Indeksowaną rodziną podzbiorów X nazywamy każdą funkcję
,
:
,
2
:
t
X
A
t
f
T
f
a
→
gdzie
X
A
T
t
t
⊆
∈
,
.
Oznaczenie rodziny indeksowanej:
}
:
{
)
(
:
)
(
}
{
T
t
A
T
f
A
A
t
T
t
t
T
t
t
∈
=
=
=
∈
∈
Def. 5. Uogólnioną sumą rodziny zbiorów
}
:
{
T
t
A
t
∈
nazywamy zbiór:
}
:
{
:
t
T
t
t
A
x
T
t
X
x
A
∈
∈
∃
∈
=
∈
U
.
Uogólnionym iloczynem rodziny zbiorów
}
:
{
T
t
A
t
∈
nazywamy zbiór:
}
:
{
:
t
T
t
t
A
x
T
t
X
x
A
∈
∈
∀
∈
=
∈
I
.
Uwaga:
t
T
t
t
A
x
T
t
A
x
∈
∈
∃
⇔
∈
∈
U
, zaś
t
T
t
t
A
x
T
t
A
x
∈
∈
∀
⇔
∈
∈
I
.
Logika i teoria mnogości – Wykład 2
4
Własności działań nieskończonych
Tw. Jeżeli
T
t
t
T
t
t
B
A
∈
∈
)
(
,
)
(
są indeksowanymi rodzinami podzbiorów zbioru X
i A
X, to prawdziwe są zależności:
1.
,
)
(
A
A
A
A
T
t
T
t
t
t
⊆
⇒
⊆
∈
∀
∈
U
2.
,
)
(
I
T
t
t
t
A
A
A
A
T
t
∈
⊆
⇒
⊆
∈
∀
3.
,
)
(
U
U
U
T
t
t
T
t
t
T
t
t
t
B
A
B
A
∈
∈
∈
∪
=
∪
4.
I
I
I
T
t
t
T
t
t
T
t
t
t
B
A
B
A
∈
∈
∈
∩
=
∩
)
(
,
5.
,
)
(
|
U
U
T
t
t
T
t
t
A
A
A
A
∈
∈
∩
=
∩
6.
,
)
(
I
I
T
t
t
T
t
t
A
A
A
A
∈
∈
∪
=
∪
7.
I
U
T
t
t
T
t
t
A
A
A
A
∈
∈
=
)
\
(
\
oraz
U
I
T
t
t
T
t
t
A
A
A
A
∈
∈
=
)
\
(
\
,
stąd
I
U
T
t
t
T
t
t
A
A
∈
∈
=
'
'
)
(
oraz
,'
'
)
(
U
I
T
t
t
T
t
t
A
A
∈
∈
=
8.
I
I
U
U
T
t
t
S
t
t
T
t
t
S
t
t
A
A
A
A
T
S
∈
∈
∈
∈
⊇
∧
⊆
⇒
⊆
,
9.
⇒
⊆
∈
∀
t
t
B
A
T
t
I
I
U
U
T
t
t
T
t
t
T
t
t
T
t
t
B
A
B
A
∈
∈
∈
∈
⊆
∧
⊆
.
Pusta rodzina zbiorów gdy T =
,
}
:
{
∅
∈
t
A
t
, wtedy:
∅
=
∅
∈
U
t
t
A
oraz
X
A
t
t
=
∅
∈
I
.
Rodziny podwójnie indeksowane
Jeśli T = I×J, to rodzinę
)
,
(
)
(
j
i
A
T
f
=
oznaczamy A
i,j
.
Możemy zdefiniować działania uogólnione po dwóch indeksach, np.:
Na początku wyznaczamy
}
:
{
:
,
,
j
i
J
j
j
i
i
A
x
J
j
x
A
B
I
i
∈
∈
∀
=
=
∈
∀
∈
I
,
Następnie otrzymujemy zbiór
U
UI
I
i
i
I
i
J
j
j
i
B
A
∈
∈ ∈
=
,
.
Mamy więc
j
i
I
i
J
j
j
i
A
x
J
j
I
i
A
x
,
,
)
(
)
(
∈
∈
∀
∈
∃
⇔
∈
∈ ∈
UI
.
Analogicznie definiujemy inne podwójne działania uogólnione.