5. ALGEBRA ZBIORÓW

5.0. POCZĄTKI TEORII MNOGOŚCI

Teoria mnogości, czyli teoria zbiorów zawdzięcza swe powstanie

matematykom XIX w., którzy dążyli do ugruntowania analizy mate-
matycznej i zbadania jej podstawowych pojęć. Pod tym kątem pisane
były prace Dedekinda i Du Bois-Reymonda. Początki teorii znajdu-
jemy już w pracach Boole’a, jednak właściwym twórcą teorii mno-
gości jako odrębnej dyscypliny matematycznej jest Georg Cantor

122

.

Opublikował on szereg prac poświęconych pojęciu zbioru, podał defi-
nicje i twierdzenia teorii mnogości, które do dziś tworzą jej podstawy.
Przez wieki niezależnie od siebie rozwijały się pojęcie zbioru i nieskoń-
czoności. Zasługą Cantora jest połączenie ich w jednej teorii. To on
stworzył teorię mnogości. Jest ona dziełem jednego człowieka. Tym
historia teorii mnogości różni się od historii innych działów matema-
tyki. Rozwój większości z nich to długi proces ewolucji idei i zaan-
gażowania wielu matematyków, którzy czasem prawie jednocześnie
dokonywali odkryć. Prace Cantora spotykały się z niezrozumieniem
i opozycją nawet tak wybitnych matematyków jak np. Gauss. Uwa-
żał on, że pojęcie nieskończoności, którego teorią jest w szczególności
teoria zbiorów, nigdy nie wejdzie w skład pojęć matematycznych.
Miał to być tylko sposób mówienia. Henri Poincare przewidywał, że
teoria zbiorów przez przyszłe pokolenia będzie postrzegana jako „cho-
roba, przez którą trzeba było przejść”. Stwierdzenia te były łagodne

122

Georg Ferdinand Ludwig Philip Cantor (1845–1918) urodził się w Sankt Pe-

tersburgu. Ojciec był duńskim Żydem wyznania protestanckiego, matka Dunką
wyznania rzymsko-katolickiego. Po opuszczeniu w dzieciństwie Rosji, Cantor do
końca życia mieszkał w Niemczech. Był profesorem prowincjonalnego Uniwersy-
tetu w Halle. Podstawowe prace ogłaszał w Mathematische Annalen w latach
1879–1893.

260

5. ALGEBRA ZBIORÓW

w porównaniu z działaniami podjętymi przez Kroneckera, jednego z
nauczycieli Cantora

123

.

Zwalczał on Cantora nie przebierając w środ-

kach i na wszelkich płaszczyznach, nawet jego samego, podobno na-
zywając go „deprawatorem młodzieży”

124

.

Uniemożliwił mu pracę na

prestiżowym Uniwersytecie Berlińskim. Cantor przechodził nerwowe
załamania. Od 1884 r. przez resztę życia leczył się psychiatrycznie.

Nieskończoności obawiali się matematycy starożytnymi. Na przy-

kład Grecy odrzucali liczby niewymierne, bo wiązało się to z nieskoń-
czonością. Czyniono to z powodu paradoksów z nią związanych, na
które już wskazywał Zenon z Elei (ok. 490 – ok. 430 p.n.e.). Wśród
współczesnych Cantorowi byli jednak i tacy matematycy, którzy od
razu zrozumieli znaczenie i rolę teorii mnogości. Należeli do nich Mit-
tag-Leffler, Weierstrass i wieloletni przyjaciel Cantora Richard De-
dekind. Szerszą akceptację Cantor zaczął znajdować na przełomie
wieków. Na Kongresie Matematycznym w Zurichu w 1897 r. prace
Cantora spotkały się z najwyższym uznaniem wielu, w tym Hurwitza
i Hadamarda. W 1904 Cantor został członkiem Londyńskiego Towa-
rzystwa Matematycznego oraz Towarzystwa Naukowego w G¨

ottingen.

W pierwszych latach XX w. teoria mnogości przechodzi kryzys.

Prace Cantora owiane były duchem mistycyzmu. Szukając filozoficz-
nych uzasadnień zbiorów nieskończonych, odwoływał się do metafi-
zyki i teologii. Wyniki zaś interpretował w duchu religijnym. Zresztą
i odwrotnie: Cantor znalazł wiernych czytelników i odbiorców swoich
idei właśnie wśród filozofów i teologów. To zaś narażało na możli-
wość wejścia w konflikt z ortodoksją katolicką. Cantor musiał np. szu-
kać rozwiązań, które uchroniłyby go przed podejrzeniami o tendencje
panteistyczne. W swoich rozważaniach o zbiorach kierował się intu-
icyjnym pojęciem zbioru. Takie niesprecyzowane pojęcie okazało się
zawodne w wypadku bardziej subtelnych rozważań. Na przykład nie
było jednoznacznej odpowiedzi na pytanie, czy istnieje zbiór wszyst-

123

Cantor studiował w Berlinie, gdzie jego nauczycielami byli najwięksi mate-

matycy tamtych czasów, m.in. Kronecker i Weierstrass.

124

Interesujące, że jezuici zastosowali jego teorię do dowodu istnienia Boga i

Świętej Trójcy. Cantor, który sam był wybitnym teologiem, zdystansował się od
tych „dowodów”.

5. ALGEBRA ZBIORÓW

261

kich zbiorów. W konsekwencji pojawiły się antynomie, czyli rozwa-
żania intuicyjnie poprawne prowadzące jednak do sprzeczności

125

.

Jednak – powtarzając za Whiteheadem – a contradiction is not a
failure, it’s an opportunity

126

.

Kryzys został opanowany w 1904 r.

przez Zermelo (i jego kontynuatorów) dzięki sformułowaniu systemu
aksjomatycznego. Ujęcie zaproponowane przez Zermelo a kontynu-
owane przez Fraenkla, Johna von Neumana i innych, zrodziło nowe
problemy, z których wiele pozostaje nierozwiązanych do dziś. Wąt-
pliwości budzi np. aksjomat wyboru, który umożliwia konstrukcję
«patologicznych» zbiorów. Pierwsze ćwierćwiecze XX w. jest okre-
sem tryumfu teorii mnogości, jej metod i pojęć.

Ważny wkład w rozwój teorii mnogości wnieśli matematycy pol-

scy. Na przykład wydana w 1912 r. książka Wacława Sierpińskiego
Zarys teorii mnogości była jednym z pierwszych podręczników tej
dziedziny w literaturze światowej. Zgodnie z planem wyznaczonym
przez organizatorów Polskiej Szkoły Matematycznej, przede wszyst-
kim Janiszewskiego, jej prace koncentrowały wokół teorii mnogości.
„Fundamenta Mathematicae”– pismo tej szkoły – stało się świato-
wym organem teorii mnogości.

Tu głównie zajmiemy się fragmentem teorii mnogości dającym się

przedstawić w oparciu o intuicyjne pojęcia zbioru i elementu zbioru
(czyli na gruncie «naiwnej» teorii mnogości), tak zwaną algebrą zbio-
rów (rachunkiem zbiorów)

127

. Badać będziemy operacje na zbiorach.

125

Chronologicznie pierwszą antynomią, znaną już Cantorowi w 1895 r., jest ro-

zumowanie podane w [1897] przez włoskiego matematyka Burali-Forti. Opiera się
ono na pojęciu zbioru wszystkich liczb porządkowych. Sądzi się, że Cantor para-
doks ten odkrył sam w 1885 r. i pisał o nim w liście do Hilberta w 1886 r.. W
1899 r. Cantor odkrył paradoks zbioru wszystkich zbiorów. Ostateczna antynomia
oparta na podziale zbiorów na te, które są i te, które nie są swoimi elementami,
podana została przez Russella (i niezależnie przez Zermelo). W liście z 16 czerwca
1902 r. do Fregego, Russell pisał o skonstruowaniu antynomii w oparciu o aksjo-
maty z Grundgesetze der Arithmetik [1893]. Zdaniem Fregego paradoks Russella
podważył całą matematykę.

126

Sprzeczność nie jest nieszczęściem, jest okazją.

127

Algebra zbiorów została ugruntowana przez matematyka angielskiego G. Bo-

ole’a. Pierwsza jego praca z tej dziedziny ukazała się w 1854 r. Wiele twierdzeń z
algebry zbiorów znał wcześniej Leibniz (XVII w.).

262

5. ALGEBRA ZBIORÓW

5.1. ZBIÓR I ELEMENT ZBIORU

Pojęcia zbioru i elementu zbioru są jednymi z podstawowych po-

jęć matematyki. Teoria mnogości, czyli teoria zbiorów, obok logiki
zakładana jest przez wszystkie dyscypliny matematyczne. Terminy i
twierdzenia teorii mnogości wykorzystywane są w prawie każdej na-
uce. Jest narzędziem innych działów matematyki. Z podstawowych
intuicyjnych pojęć i twierdzeń teorii mnogości korzystaliśmy w pierw-
szej części książki, części poświęconej logice.

G. Cantor pisze: „Pod pojęciem ‘rozmaitości’ (Mannigfaltigkeit)

czy ‘zbioru’ (Menge) rozumiem mianowicie ogólnie każdą wielość (je-
des Viele), która może być pomyślana jako jedność (als Eines), tj.
każdy ogół (Inbegriff) określonych elementów, które na mocy pew-
nego prawa mogą być złączone w jedną całość”

128

.

Podane przez Cantora określenie, jako postulat charakteryzujący

pojęcie zbioru określa się mianem pewnika abstrakcji lub pewnika de-
finicyjnego

129

.

Do pojęcia zbioru dochodzimy abstrahując od konkretu, czyli

jednostkowości przedmiotów. Stos kamieni jest przedmiotem konkret-
nym

130

.

Zbiór, którego wszystkimi i tylko elementami są kamienie z

tego stosu jest obiektem abstrakcyjnym

131

.

Stos kamieni jako obiekt

fizyczny, ma własności fizyczne takie, jak np. masa. Zbiór, którego
kamienie z tego stosu są elementami nie jest przedmiotem fizycznym,
a zatem nawet pytanie o jego własności fizyczne nie jest pytaniem po-
prawnie postawionym. Kamienie ze stosu kamieni nie są elementami
stosu, tylko jego częściami.

128

Zob. Murawski [1986], s. 157. Oryginalny tekst jest następujący: Unter einer

‘Menge’ verstehe ich allgemein jedes Viele welches sich als Eines denken l¨

asst, d.h.

jeden Inbegriff bestimmter Elemente, welcher durch ein Gesetz zu einem Ganzen
verbunden werden kann. Cantor [1883a], zob. Cantor [1932] s. 204.

129

W języku angielskim używa się określenia comprehension axiom.

130

Przez przedmiot konkretny rozumiemy rzecz, czyli przedmiot fizyczny, osobę

lub coś, co sobie jako takie wyobrażamy. Na przykład Wołodyjowski jest przed-
miotem konkretnym.

131

Przedmioty abstrakcyjne to cechy, stosunki (relacje), zjawiska, stany itp.

5. ALGEBRA ZBIORÓW

263

W języku potocznym słowo „zbiór” używane jest w znaczeniu

dystrybutywnym, czyli abstrakcyjnym, zatem w tym znaczeniu, jakie
ma ono w teorii mnogości, oraz w znaczeniu kolektywnym, zwanym też
mereologicznym, czyli znaczeniu, w którym stos kamieni jest zbiorem.

W wypadku dystrybutywnego znaczenia słowa „zbiór”, przed-

mioty, które się na zbiór składają są jego elementami. W wypadku
kolektywnego znaczenia słowa „zbiór”, przedmioty, które składają się
na niego są jego częściami. Zbiór w sensie kolektywnym to agregat lub
konglomerat.

Liczność zbioru (w sensie dystrybutywnym) jest określona przez

to, ile elementów ma ten zbiór. Zbiór, którego elementami są wszyst-
kie i tylko kamienie z pewnego stosu kamieni ma tyle elementów, ile
kamieni składa się na ten stos kamieni. O liczności agregatu, jakim
jest stos kamieni nawet trudno mówić: liczba jego części zależy od
«głębokości» podziału. Mogą to być najprościej dające się wydzielić
kamienie, ale mogą to też być części tych kamieni

132

.

Ei

264

5. ALGEBRA ZBIORÓW

elementem danego zbioru. Z punktu widzenia języka znaczy to, że
zbiory pojmowane są jako zakresy nazw ostrych, czyli takich, że do-
wolny przedmiot jest albo nie jest ich desygnatem

133

.

Przykładem

nazwy ostrej jest „dziecko Jana” – dowolny przedmiot jest albo nie
jest dzieckiem Jana. To, czy ktoś jest, czy nie jest dzieckiem Jana
nie zależy ani od stanu wiedzy kogokolwiek, ani nie podlega jakiej-
kolwiek gradacji spowodowanej ewentualnymi wątpliwościami, co do
stanu faktycznego. W związku z językiem naturalnym i pojawiają-
cymi się możliwościami stosowania m.in. narzędzi informatycznych
pojawiła się potrzeba opisu zakresów nazw nieostrych. Są to takie
nazwy, co do których reguły języka nie przesądzają, czy pewne przed-
mioty są, czy też nie są ich desygnatami. Przykładem nazwy nieostrej
jest „dziecko”

134

.

Ktoś, kto kwestionowałby użycie tej nazwy do wska-

zania siedmiolatka naruszałby reguły języka polskiego. Podobnie na-
rusza te reguły ktoś, kto tę nazwę zastosowałby do dwudziestolatka.
Jednak reguły języka polskiego nie przesądzają, czy czternastolatek
to dziecko, czy nie. Innym przykładem nazwy nieostrej jest „młody”.
W wypadku nazw nieostrych nie jest więc tak, że dowolny przed-
miot jest albo nie jest ich desygnatem. Formalny opis ich zakresów
jako zbiorów wymaga zatem nowego rozumienia samej przynależności
elementu do zbioru. W wypadku zbioru rozmytego przynależność ele-
mentu do zbioru podlega gradacji, przyjmując wartości z przedziału

[0

, 1]

135

.

Szuka się też innych rozwiązań, jak np. w wypadku koncep-

cji zbiorów przybliżonych. W teorii klasycznej – takiej, jaka tu jest
rozwijana – przyjmuje się, że dowolny przedmiot jest albo nie jest
elementem danego zbioru. To rozstrzygnięcie nie wyczerpuje jednak
wszystkich problemów sposobu rozumienia przynależności do zbioru.

Natura elementów zbioru może być dowolna. W szczególności

133

Desygnat nazwy to każdy i tylko przedmiot, do którego wskazania nazwa

może być użyta zgodnie z regułami języka. Zakres nazwy to zbiór jej desygnatów.

134

Jako nazwa nierelatywna, a więc nazwa, która służy do wskazania elementu

pewnej grupy wiekowej. Nazwa „dziecko” może być wzięta w zanczeniu relatyw-
nym, jak wówczas, gdy mówimy, że Piotr jest dzieckiem Jana. Dzieckiem w sensie
nierelatywnym jest każdy człowiek w pewnym okresie swego życia, a mianowicie
wówczas, gdy jest w wieku dziecięcym. Dzieckiem Jana jest się, albo się nim nie
jest i nie zależy to od wieku.

135

Zob. Zadeh [1965].

5. ALGEBRA ZBIORÓW

265

same mogą być zbiorami

136

.

O takich elementach zbiorów, które

same nie są zbiorami można mówić jako o praelementach. Istnienie
takich obiektów nie jest jednak konieczne dla teorii mnogości. Wy-
starczy przyjąć, że istnieje przynajmniej zbiór pusty. Zbiór ten może
być elementem innego zbioru. Dalej zbiór pusty i zbiór, którego ele-
mentem jest zbiór pusty mogą być elementami innego zbioru itd. Ta
konstrukcja nie pozwala na stworzenie zbioru, którego on sam byłby
elementem. W ogóle nie jest możliwa konstrukcja zbioru, którego ele-
mentem byłby obiekt, w którego konstrukcji korzystałoby się z tego
konstruowanego zbioru. Metoda konstrukcji zbiorów kolejnymi kro-
kami najogólniej rzecz biorąc polega na tym, że

1. każdy obiekt utworzony w kroku

K

ze zbiorów utworzonych w

krokach wcześniejszych niż

K

jest zbiorem;

2. nie ma żadnych innych zbiorów niż utworzone, na którymś kroku.

Ta idea konstrukcji zbiorów kolejnymi krokami jest ważna dla wła-
ściwego pojęcia zbioru, jakie ma się na uwadze w teorii mnogości.

Stosowanie intuicyjnych pojęć zbioru oraz bycia elementem

zbioru jest ograniczone i w wypadku bardziej zaawansowanych roz-
ważań musi zostać zastąpione przez pojęcia ściśle określone

137

.

Do-

konuje się tego na gruncie aksjomatycznej teorii mnogości. Pierwszą
taką teorię stworzył Ernest Zermelo [1908].

Wielkich liter z początku alfabetu:

A, B, C, . . .

, w razie potrzeby

z indeksami, używać będziemy jako zmiennych, których wartościami
są zbiory.

136

W takich wypadkach zamiast o zbiorze zwykło się mówić o klasie zbiorów lub

rodzinie zbiorów. Od strony formalnej tak rozumiana „klasa” i „rodzina” znaczą
to samo co „zbiór”.

137

I tym samym dochodzi do zerwania ze zdroworosądkowym ich pojmowaniem.

Jak jednak zauważa Irving Copi: „To a greater or lesser degree, every scientific
advance marks some departure from the common sense that preceded it.” – W
większym lub mniejszym stopniu, każde osiągnięcie naukowe wskazuje na odej-
ście od sensu zdroworozsądkowego, na którym było oparte (Copi [1979], s. 195).
Wszak wciąż „

. . .

among all the mathematical theories, it is just the theory of

sets that requiers clarification more than any other.” – spośród wszystkich teorii
matematycznych właśnie teoria mnogości wymaga wyjaśnień bardziej niż każda
inna (Mostowski [1979], s. 3).

266

5. ALGEBRA ZBIORÓW

Wielkich liter z końca alfabetu:

X , Y, Z

, w razie potrzeby z in-

deksami, używać będziemy jak nazw pewnych wyróżnionych zbiorów
(przestrzeni).

Małych liter z początku alfabetu:

a, b, c, . . .

, w razie potrzeby z

indeksami, używać będziemy jako nazw elementów zbiorów.

Małe litery z końca alfabetu:

x, y, z

, w razie potrzeby z indek-

sami, będą używane jako zmienne, których wartościami są elementy
zbiorów

138

.

Przedmioty (indywidua), które tworzą zbiór to jego elementy.

Fakt, że przedmiot

a

jest elementem (należy do) zbioru

A

zapisujemy

a ∈ A

„

∈

” jest dwuargumentową literą predykatową

139

.

To, że

a

nie jest elementem (nie należy do) zbioru

A

,

¬(a ∈ A)

,

możemy zapisać

a ∈ A

.

138

Jest to umowa na użytek teorii mnogości. W jej aplikacjach możliwe są inne

konwencje. Na przykład w geometrii elementarnej zwyczajowo przyjęło się wiel-
kimi literami oznaczać punkty a małych używać na oznaczenie figur, czyli zbiorów
punktów.

139

Znak „

∈

” został wprowadzony w 1889 przez G. Peano. Taka informacja po-

dawana jest na stronie internetowej University of St. Andrews. Peano użył jej we
wstępie do I tomu Formulaire de math´

ematiques [1895]. Sam wstęp datowany jest

na 1894 r. Symbol ten pochodzi od pierwszej litery greckiego słowa

´

στι

(być).

W tradycyjnej ontologii wyróżnia się podmiot (

P

) i atrybut (

A

). Rozpoznanie

podmiotu i jego atrybutu jest podstawową czynnością poznawczą. Mówimy, że

P

jest

A

wówczas i tylko, gdy atrybut

A

przysługuje podmiotowi

P

. Ten pod-

stawowy związek wyraża więc słowo „ jest” a po grecku właśnie

´

στι

. Niech

y

będzie zmienną, której zakresem są przedmioty dowolnej kategorii ontologicznej.
Niech

Z(y)

będzie zbiorem wszystkich i tylko przedmiotów, dla których

y

może

być znakiem. Niech

E(Z(y))

będzie skrótem dla „element zbioru

y

-ków”. Bycie

elementem zbioru

y

-ków jest atrybutem. Zatem to, że przedmiotowi

x

przysługuje

atrybut bycia elementem zbioru

y

-ków możemy zapisać

x
E(Z(y))

.

Te dwa znaki „

E

w teorii mnogości zostały sprowadzone do jednego

∈

.

Roman Suszko mówi o wzorze

x ∈ Z(y) ⇔ x
y

jako o naczelnej zasadzie teorii mnogości. Zob. Suszko [1965], s. 54–56.

5. ALGEBRA ZBIORÓW

267

Oczywiście, używać będziemy również nawiasów. Zasady ich uży-

cia nie różnią się istotnie od zasad stosowanych w rachunku predyka-
tów.

Nasz język jest w istocie językiem rachunku predykatów (pierw-

szego rzędu) z identycznością. Gdybyśmy wprowadzili jednoargumen-
tową literę predykatową „

. . .

jest zbiorem”, to moglibyśmy operować

tylko stałymi i zmiennymi indywiduowymi:

a, b, . . . ; x

0

, x

1

, . . .

. Byłby

to jednak mniej czytelny zapis.

Rozwijając teorię zbiorów będziemy wzbogacać język o użyteczne

symbole. Będziemy definiowali stałe indywiduowe, litery predykatowe
i litery funkcyjne zgodnie z zasadami definiowania tych rodzajów sym-
boli opisanymi w rozdziale o definiowaniu. Podawane będą również
zasady co do mocy wiązania.

Zbiór charakteryzujemy ekstensjonalnie wskazując jego elementy.

Nazwy elementów wpisujemy w nawiasy sześcienne. Zbiór, którego
wszystkimi i tylko elementami są

a

0

, a

1

, . . . , a

n

to zbiór

{a

0

, a

1

, . . . , a

n

}

lub, gdy są to przedmioty

a

t

przyporządkowane elementom zbioru

T

{a

t

:

t ∈ T }

.

Warto tu zauważyć, że przedmiot (indywiduum) różni się od

zbioru, którego jest on jedynym elementem:

a

jest jedynym elemen-

tem zbioru

{a}

.

Zbiór charakteryzujemy intensjonalnie podając formułę z jedną

zmienną wolną, którą to formułę spełniają wszystkie i tylko elementy
tego zbioru lub – jak to zwykle będziemy mówili – podając własność,
którą mają wszystkie i tylko elementy tego zbioru.

{x : φ(x)}

to zbiór wszystkich tych i tylko tych przedmiotów, dla których prawdą
jest, że są

φ

(lub – jak mówimy – które mają własność

φ

)

140

.

140

Nie mówimy tu, że

φ

wyznacza zbiór. Mówimy jedynie, że za pomocą

φ

charakteryzujemy wszystkie i tylko elementy pewnego zbioru. Por. przypis do

268

5. ALGEBRA ZBIORÓW

Znaków „

{

” oraz „

}

” używaliśmy jako znaków interpunkcyj-

nych. Teraz nawiasy te występują w roli operatora tworzącego nazwę
zbioru

141

.

Operator ten nazywa się operatorem abstrakcji lub znakiem

abstrakcji. Istnieje wiele odmian jego użycia. Pisze się np.

{x|φ(x)}

,

Aby zapisać, że mamy na uwadze tylko przedmioty ze zbioru

A

,

które spełniają

φ

piszemy

{x ∈ A : φ(x)}

.

Zapis

{x · y|x ∈ X ∧ y ∈ Y }

oznacza zbiór, którego wszystkimi elementami są iloczyny z pierw-
szym czynnikiem, będącym elementem zbioru

X

i z drugim czynni-

kiem, będącym elementem zbioru

Y

.

Operator abstrakcji został wprowadzony przez Fregego [1893].

Jego nazwa pojawia się w Principia Mathematica, gdzie stosowany
jest symbol:

ˆ

. „

(ˆ

x)φ(x)

” oznacza zbiór taki, że

y ∈ (ˆx)φ(x) ⇔ φ(y)

.

Inny symbol był używany przez Fregego, a jeszcze inny przez Peano.

Czasem zależy nam na charakterystyce ekstensjonalnej zbioru

scharakteryzowanego intensjonalnie, np. równanie jest charaktery-
styką intensjonalną zbioru pierwiastków tego równania. Rozwiązać
równanie to tyle, co scharakteryzować ten zbiór ekstensjonalnie.

aksjomatu podzbiorów. Wprowadzenie do języka teorii mnogości oznaczenia

{x :

φ(x)}

wymaga pokazania, że istnieje zbiór

A

taki, że

∀x.[x ∈ A ⇔ φ(x)]

(do

tego celu trzeba skorzystać z aksjomatu podzbiorów) oraz że jest dokładnie jeden
(tu korzystamy z definicji równości zbiorów).

141

Taki symbol wprowadził G. Cantor w [1895], s. 481. Pisał: Unter einer

‘Menge’ verstehen wir jede Zusammenfassung

M

von bestimmten wohlunter-

schiedenen Objecten

m

unserer Anschauung oder unseres Denkens (welche die

‘Elemente’ von

M

genannt werden) zu einem Ganzen.

In Zeichen dr¨

ucken wir dies so aus:

M = {m}

.

– Przez ‘zbiór’ rozumiemy każde zebranie w całość

M

określonych, dobrze

odróżnionych przedmiotów

m

naszego oglądu lub naszych myśli (które nazywane

są ‘elementami’

M

).

5.2. RÓWNOŚĆ ZBIORÓW

269

5.2. RÓWNOŚĆ ZBIORÓW

O zbiorach

A

i

B

powiemy, że są ekstensjonalnie równe wtedy i

tylko wtedy, gdy mają te same elementy, czyli – inaczej – nie różnią się
swoimi elementami. Zbiory, które są równe, są ekstensjonalnie równe.

(T1) Jeżeli zbiory

A

i

B

są równe (

=

), to mają te same elementy:

(

A = B) ⇒ ∀x.(x ∈ A ⇔ x ∈ B)

.

DOWÓD

142

Z aksjomatu identyczności ID3 mamy

1.

A = B ⇒ x ∈ A ⇒ x ∈ B

.

Podobnie

2.

B = A ⇒ x ∈ B ⇒ x ∈ A

.

Po dołączeniu dużego kwantyfikatora z 1 i 2, odpowiednio, otrzy-

mujemy

3.

A = B ⇒ ∀x.(x ∈ A ⇒ x ∈ B)

,

4.

B = A ⇒ ∀x.(x ∈ B ⇒ x ∈ A)

.

Z 3 i 4 i z tego, że identyczność jest symetryczna mamy

5.

A = B ⇒ ∀x.(x ∈ A ⇔ x ∈ B)

.

Powstaje pytanie, czy jeżeli zbiory są ekstensjonalnie równe, to

są równe. Pozytywna odpowiedź na to pytanie nie wydaje się być in-
tucyjnie oczywista. Zbiór mieszkańców Warszawy jest ekstensjonalnie
równy zbiorowi mieszkańców stolicy Polski. Czy jednak zbiory te są
równe? Gdyby rozumieć zbiory w sposób intensjonalny, to ich rów-
ność zależałaby nie tylko od ich elementów (ekstensji), lecz również
od sposobu określenia (intensji). Na gruncie rachunku predykatów

142

Dowody twierdzeń rachunku zbiorów przeprowadzamy metodą dowodów za-

łożeniowych. Jako założenia dowodu mogą być brane tezy rachunku predykatów
oraz definicje i wcześniej udowodnione twierdzenia rachunku zbiorów. Korzystamy
nie tylko z reguł pierwotnych, lecz również z tych reguł, które są intuicyjnie oczy-
wiste. Nie będziemy tych reguł nazywać. Zwykle wskazywane będą tylko wiersze
dowodowe, do których reguły są stosowane. Odpowiedni komentarz będzie za-
mieszczany między wierszami dowodowymi (ze względów typograficznych).

270

5. ALGEBRA ZBIORÓW

z identycznością z ekstensjonalnej równości zbiorów nie wynika ich
równość. Teorię mnogości uprawia się przyjmując aksjomatycznie, że
ekstensjonalna równość zbiorów pociąga za sobą równość zbiorów.
Takie, ekstensjonalne, ujęcie zbioru jest prostsze. Konsekwencją jest
jednak konieczność uznania tezy, że cechy koekstensywne

143

,

są toż-

same.

Zasada ekstensjonalności

144

głosi, że jeżeli dwa zbiory są eksten-

sjonalnie równe, mają te same elementy, to są równe, czyli mają te
same własności:

∀x.(x ∈ A ⇔ x ∈ B) ⇒ (A = B)

.

A zatem:

(DEF.

=

)

(

A = B) ⇔ ∀x.(x ∈ A ⇔ x ∈ B)

,

czyli zbiory są równe wtedy i tylko wtedy, gdy mają te same elementy.

Symbol „

=

” to dwuargumentowa litera predykatowa.

Wprowadzamy skrót „

=

”:

¬(A = B) ⇔ A = B

.

Przyjmujemy, że symbole „

=

” i „

=

” wiążą słabiej niż symbole

operacji na zbiorach

145

.

Dla dowolnych zbiorów

A, B, C

:

(T1)

A = A

zwrotność,

(T2)

(

A = B) ⇒ (B = A)

symetryczność,

(T3)

[(

A = B) ∧ (B = C)] ⇒ (A = C)

przechodniość,

czyli relacja równości zbiorów

146

jest zwrotna, symetryczna i prze-

chodnia.

143

Cech

c

1

jest koekstensywna z cechą

c

2

wtedy i tylko wtedy, gdy każdemu

wystąpieniu cechy

c

1

towarzyszy wystąpienie cechy

c

2

i na odwrót, czyli każdemu

wystąpieniu cechy

c

2

towarzyszy wystąpienie cechy

c

1

. Inaczej mówiąc nie ma

obiektów, które miałyby jedną z tych cech, a drugiej nie miały.

144

Zob. aksjomat równości zbiorów.

145

O symbolach tych będzie mowa później.

146

W sensie ścisłym o relacji mówi się w kontekście zbiorów, na których jest

określona. Wszelkie «relacje» między zbiorami winny być zrelatywizowane do
jakiejś rodziny zbiorów, bowiem – będzie o tym jeszcze mowa – nie ma zbioru
wszystkich zbiorów.

5.2. RÓWNOŚĆ ZBIORÓW

271

Udowodnimy tylko (T3).

DOWÓD

Z definicji równości zbiorów mamy:

1.

(

A = B) ⇔ ∀x.(x ∈ A ⇔ x ∈ B),

2.

(

B = C) ⇔ ∀x.(x ∈ B ⇔ x ∈ C).

Z (1) i (2) dostajemy:

3.

[(

A = B) ∧ (B = C)] ⇔ [∀x.(x ∈ A ⇔ x ∈ B) ∧ ∀x.(x ∈ B ⇔ x ∈ C)]

.

Tezą rachunku predykatów jest:

4.

[

∀x.(x ∈ A ⇔ x ∈ B) ∧ ∀x.(x ∈ B ⇔ x ∈ C)] ⇒ ∀x.(x ∈ A ⇔ x ∈ C)

,

więc z 3 i 4:

5.

[(

A = B) ∧ (B = C)] ⇒ ∀x.(x ∈ A ⇔ x ∈ C)

.

Ponieważ z definicji równości zbiorów:

6.

(

A = C) ⇔ ∀x.(x ∈ A ⇔ x ∈ C)

,

więc ostatecznie:

7.

[(

A = B) ∧ (B = C)] ⇒ (A = C)

.

Zbiór pusty,

∅

147

,

to zbiór, który nie ma żadnego elementu. Nie

ma takiego przedmiotu, który posiadałby jakąś własność

φ

i jej nie

posiadał. Byłby to więc zbiór

{x : φ(x) ∧ ¬φ(x)}

,

lub, mając na uwadze to, że każdy przedmiot jest równy samemu
sobie, a więc, że nie ma przedmiotów, które nie byłyby równe sobie:

{x : ¬x = x}

Dowód, że taki zbiór istnieje możliwy jest dopiero po przyjęciu

aksjomatów

148

.

147

Andr´

e Weil (1906–1998), jeden z członków grupy matematyków, kryjących

się pod pseudonimem Nicolas Bourbaki, w autobiografi sobie przypisuje wprowa-
dzenie tego symbolu. Symbol ten pochodzi z norweskiego alfabetu, który to język
Weil znał jako jedyny spośród bourbakistów.

148

Korzystać trzeba z aksjomatu istnienia oraz z aksjomatu różnicy.

272

5. ALGEBRA ZBIORÓW

Dla wykazania jedyności tego zbioru trzeba pokazać, że jeżeli

A = {x : ¬x = x}

i

B = {x : ¬x = x}

, to

A = B

.

Niech

1.

A = {x : ¬x = x},

2.

B = {x : ¬x = x}.

Na podstawie symetryczności równości zbiorów i 2 mamy:

3.

{x : ¬x = x} = B

Z 1 i 3 mamy:

4.

A = {x : ¬x = x} ∧ {x : ¬x = x} = B

Z przechodniości równości zbiorów i z 4 ostatecznie dostajemy:

5.

A = B

.

(DEF.

∅

)

∅ = {x : ¬x = x}

,

co inaczej możemy zapisać:

∅ = {x : x = x}

.

Symbol „

∅

” to stała indywiduowa. Zbiór pusty pełni w teorii

mnogości rolę podobną do tej, którą

0

pełni w algebrze

149

.

W algebrze zbiorów przyjmuje się, że zbiory rozważane w ramach

określonej dyscypliny – w której algebra zbiorów jest stosowana –
są tego rodzaju, że wszystkie ich elementy są elementami pewnych
zbiorów

150

.

Dla określonej klasy zbiorów taki zbiór jest tylko jeden.

Zbiór ten,

X

, to przestrzeń (zbiór pełny lub zbiór uniwersalny).

X

możemy zdefiniować przez własność, którą posiadają wszystkie i tylko
jego elementy. Byłby to więc zbiór:

{x : φ(x) ∨ ¬φ(x)}

,

lub, mając na uwadze to, że każdy przedmiot jest równy samemu
sobie:

149

Pojęcie zbioru pustego występuje już w średniowieczu w XIII i XIV wieku.

Zajmowano się wówczas analizą wyrażeń, które określają byty nie istniejące.

150

Nie twierdzimy tym samym, że istnieje jakiś taki zbiór, że wszystkie elementy

jakiegokolwiek zbioru byłyby elementami tego zbioru.

5.3. ZAWIERANIE SIĘ ZBIORÓW

273

{x : x = x}

.

(DEF. zbioru uniwersalnego,

X

)

X = {x : x = x}

.

Symbol „

X

” to stała indywiduowa

151

.

Zgodnie z regułą definiowania stałych indywiduowych należy po-

kazać, że istnieje zbiór

X

i że jest dokładnie jeden. Podobnie jak w

wypadku zbioru pustego

∅

istnienie zbioru pełnego

X

wymaga od-

wołania się do aksjomatów

152

,

zaś dowód jego jedyności przebiega

analogicznie do dowodu jedyności zbioru pustego

∅

.

Czasem, w szczególności w rozważaniach nad relacjami i funk-

cjami, przyjmuje się istnienie więcej niż jednego zbioru uniwersal-
nego (każdy z nich jest jedynym zbiorem uniwersalnym, który ozna-
cza dana stała indywiduowa). Na oznaczenie tych zbiorów, jak już
była mowa, używa się wielkich liter z końca alfabetu:

X , Y, Z

(w razie

potrzeby z indeksami).

5.3. ZAWIERANIE SIĘ ZBIORÓW

153

Zbiór

A

jest podzbiorem

B

,

A ⊆ B

154

,

wtedy i tylko wtedy, gdy

każdy element zbioru

A

jest elementem zbioru

B

:

(DEF.

⊆

)

(

A ⊆ B) ⇔ ∀x.(x ∈ A ⇒ x ∈ B)

.

Symbol „

⊆

” to dwuargumentowa litera predykatowa.

Gdy

A

nie jest podzbiorem

B

, to piszemy:

151

Zamiast zajmować się wszystkimi indywiduami i określać, które z nich wcho-

dzą w zakres rozważanej teorii, wygodniej jest z góry ograniczyć się do tych przed-
miotów. Ten zbiór przedmiotów, zbiór uniwersalny, to dziedzina rozważanej teorii.
Na przykład dziedziną arytmetyki jest zbiór liczb. Pojęcie dziedziny teorii (zbioru
uniwersalnego) wprowadził do logiki De Morgan. Jest ono późniejsze od pojęcia
zbioru pustego.

152

Korzystamy z aksjomatu istnienia.

153

Relacje, o których tu będzie mowa jako pierwszy wyczerpująco zbadał mate-

matyk francuski J. D. Gergonne (1771–1859). Zauważmy – o czym już była mowa
przy okazji relacji równości zbiorów – że ponieważ nie ma zbioru zbiorów, w sensie
właściwym o relacjach między zbiorami można mówić, mając zawsze na uwadze
jakąś rodzinę zbiorów.

154

W tym samym znaczeniu co „

⊆

” bywa używany też symbol „

⊂

”.

274

5. ALGEBRA ZBIORÓW

A ⊆ B

.

Zbiór

A

zawiera się w zbiorze

B

wtedy i tylko wtedy, gdy zbiór

A

jest podzbiorem zbioru

B

. Relacja

⊆

to relacja zawierania się zbiorów

lub inaczej relacja inkluzji.

Zbiór

A

jest właściwym podzbiorem zbioru

B

wtedy i tylko wtedy,

gdy każdy element

A

jest elementem

B

i są elementy

B

, które nie są

elementami

A

:

(DEF.

⊂

)

(

A ⊂ B) ⇔ ∀x.(x ∈ A ⇒ x ∈ B)∧∃x.(x ∈ B∧x ∈ A)

155

.

Zauważmy, że

A ⊂ B ⇔ [(A ⊆ B) ∧ (A = B)]

,

czyli

A

jest właściwym podzbiorem

B

wtedy i tylko, gdy

A

jest pod-

zbiorem

B

i

A

jest różne od

B

.

Zbiór

A

jest nadzbiorem zbioru

B

wtedy i tylko wtedy, gdy każdy

element zbioru

B

jest elementem zbioru

A

:

(DEF.

⊇

)

(

A ⊇ B) ⇔ ∀x.(x ∈ B ⇒ x ∈ A)

.

Zauważmy, że

A ⊇ B ⇔ B ⊆ A

.

Symbol „

⊇

” to dwuargumentowa litera predykatowa

156

.

Gdy

A

nie jest nadzbiorem

B

, to piszemy:

A ⊇ B

.

Zbiór

A

jest właściwym nadzbiorem zbioru

B

,

A ⊃ B

157

,

wtedy i

tylko wtedy, gdy każdy element

B

jest elementem

A

i są elementy

A

,

które nie są elementami

B

:

(DEF.

⊃

)

(

A ⊃ B) ⇔ ∀x.(x ∈ B ⇒ x ∈ A) ∧ ∃x.(x ∈ A ∧ x ∈ B)

.

Zauważmy, że

A ⊃ B ⇔ [(A ⊇ B) ∧ (A = B)]

,

155

Zob. uwagę w sprawie stosowania symbolu „

⊆

”.

156

W tym samym znaczeniu co „

⊇

” używany bywa symbol „

⊃

”.

157

Zob. uwagę w sprawie stosowania symbolu „

⊇

”.

5.3. ZAWIERANIE SIĘ ZBIORÓW

275

czyli

A

jest nadzbiorem

B

wtedy i tylko wtedy, gdy

B

jest podzbiorem

A

i

A

jest różne od

B

.

Przyjmujemy, że symbole „

⊆

”, „

⊆

”, „

⊂

”, „

⊇

”, „

⊇

”, „

⊃

” wiążą

słabiej niż wszystkie symbole operacji na zbiorach.

Dla dowolnych zbiorów

A, B, C

:

(T1)

A ⊆ A

–

zwrotność,

(T2)

[(

A ⊆ B) ∧ (B ⊆ A)] ⇒ (A = B)

–

antysymetryczność,

(T3)

[(

A ⊆ B) ∧ (B ⊆ C)] ⇒ (A ⊆ C)

–

przechodniość,

(T4)

(

A = B) ⇒ [A ⊆ B) ∨ (B ⊆ A)].

DOWÓD

Dowiedźmy tylko antysymetryczności

⊆

.

Na podstawie definicji

⊆

:

1.

A ⊆ B ⇔ ∀x.(x ∈ A ⇒ x ∈ B)

.

Podobnie:

2.

B ⊆ A ⇔ ∀x.(x ∈ B ⇒ x ∈ A)

.

Z 1 i 2 otrzymujemy:

3.

[(

A ⊆ B) ∧ (B ⊆ A)] ⇔ [∀x.(x ∈ A ⇒ x ∈ B) ∧ ∀x.(x ∈ B ⇒ x ∈ A)]

.

Tezą rachunku predykatów jest:

4.

[

∀x.(x ∈ A ⇒ x ∈ B) ∧ ∀x.(x ∈ B ⇒ x ∈ A)] ⇒ ∀x.(x ∈ A ⇔ x ∈ B).

Z 3 i 4 dostajemy:

5.

[(

A ⊆ B) ∧ (B ⊆ A)] ⇒ ∀x.(x ∈ A ⇔ x ∈ B).

Ponieważ z definicji równości zbiorów:

6.

(

A = B) ⇔ ∀x.(x ∈ A ⇔ x ∈ B),

więc z 5 i 6 ostatecznie otrzymujemy:

7.

[(

A ⊆ B) ∧ (B ⊆ A)] ⇒ (A = B)

.

Na podstawie definicji zbioru pustego i zawierania się zbiorów

mamy:

(T5)

∅ ⊆ A

,

276

5. ALGEBRA ZBIORÓW

czyli zbiór pusty jest podzbiorem każdego zbioru.

Ponadto:

(T6)

A = ∅ ⇒ A ⊆ ∅

,

czyli żaden zbiór w sposób właściwy nie zawiera się w zbiorze pustym
lub – inaczej – żaden zbiór niepusty nie zawiera się w zbiorze pustym.

Możemy zauważyć, że

(T7)

A ⊆ X

,

czyli każdy zbiór zawiera się w przestrzeni; oraz

(T8)

A = X ⇒ X ⊆ A

,

czyli przestrzeń w sposób właściwy nie zawiera się w żadnym zbiorze
lub – inaczej – przestrzeń nie jest podzbiorem żadnego zbioru różnego
od przestrzeni.

5.4. OPERACJE NA ZBIORACH

5.4.1. Dopełnienie zbioru

Dopełnieniem (uzupełnieniem) zbioru

A

jest zbiór

−A

, którego

elementami są wszystkie i tylko te elementy przestrzeni, które nie są
elementami

A

:

(DEF.

−

)

−A = {x ∈ X : ¬x ∈ A},

co możemy też zapisać:

−A = {x ∈ X : x ∈ A},

lub

∀x.[x ∈ −A ⇔ ¬x ∈ A].

Symbol „

−

” to jednoargumentowa litera funkcyjna. Przyjmu-

jemy, że wiąże najmocniej ze wszystkich symboli operacji na zbiorach
Zamiast pisać:

−(−A)

piszemy też:

− − A

.

Charakteryzując zbiór intensjonalnie mówimy o własności, którą

posiadają wszystkie i tylko elementy tego zbioru. Następuje utożsa-
mienie zbioru z własnością. Dopełnienie zbioru można więc utożsa-
miać z brakiem własności, która ten zbiór wyznacza.

5.4. OPERACJE NA ZBIORACH

277

Dla dowolnego zbioru

A

:

P1

−(−A) = A

P2

−∅ = X

P3

−X = ∅

P4

A ⊆ B ⇔ −B ⊆ −A.

Dowiedźmy tylko P1. Nosi ono nazwę prawa podwójnego uzupeł-

nienia.

DOWÓD

Z definicji dopełnienia zbioru mamy:

1.

∀x.[(x ∈ −A) ⇔ ¬(x ∈ A)]

.

Podobnie:

2.

∀x.[(x ∈ −(−A)) ⇔ ¬(x ∈ −A)]

.

Teraz opuszczamy kwantyfikatory w 1 i 2. Dostajemy więc:

3.

(

x ∈ −A) ⇔ ¬(x ∈ A),

4.

(

x ∈ −(−A)) ⇔ ¬(x ∈ −A).

Z 3 otrzymujemy:

5.

(

x ∈ A) ⇔ ¬(x ∈ −A).

Z 4 i 5 otrzymujemy:

6.

(

x ∈ A) ⇔ (x ∈ −(−A)).

Dołączając w 6 duży kwantyfikator mamy:

7.

∀x.[(x ∈ A) ⇔ (x ∈ −(−A))].

Z definicji równości zbiorów:

8.

A = −(−A) ⇔ ∀x.[(x ∈ A) ⇔ (x ∈ −(−A))]

.

Z 7 i 8 dostajemy więc:

9.

−(−A) = A

.

Przeprowadzając dowód zwykle dokonujemy «przeskoków». Czy-

nimy to wówczas mianowicie, gdy wynikanie kolejnego wiersza z po-
rzednich jest oczywiste. To, co jest oczywiste dla jednych nie musi
być oczywiste dla innych. Pojęcie oczywistości zrelatywizowane jest

278

5. ALGEBRA ZBIORÓW

więc do tych, do których dany tekst, dowód, argumentacja są skie-
rowane. Tu – mając na uwadze kształcenie wiedzy i sprawności lo-
gicznych – zwykle dowody są bardziej szczegółowe niż byłoby to ko-
nieczne dla samego wykładu omawianych treści. Zauważmy, że bez
jakiejś szkody dla możliwości stwierdzenia poprawności dowodu moż-
naby opuścić dwa początkowe wiersze naszego ostatniego dowodu.
Moglibyśmy więc dowód rozpocząć od wierszy 3 i 4, przyjmując jako
oczywistą regułę opuszczania dużego kwantyfikatora. Podobnie pomi-
nięte mogłoby być odwołanie się do definicji równości zbiorów. Dowód
możnaby więc zakończyć na wierszu 6. W miarę wykładu będziemy
co raz więcej kroków pomijać jako oczywistych. Nasze dowody będą
stawać się mniej szczegółowe.

5.4.2. Suma zbiorów

Sumą zbiorów

A

i

B

jest zbiór

A ∪ B

, którego elementami są

wszystkie i tylko te przedmioty, które są elementami zbioru

A

lub są

elementami zbioru

B

:

(DEF.

∪

)

(

A ∪ B) = {x ∈ X : x ∈ A ∨ x ∈ B}

.

W sposób równoważny możemy to wyrazić:

∀x.[x ∈ (A ∪ B) ⇔ (x ∈ A) ∨ (x ∈ B)]

.

Zauważmy, że

x ∈ (A ∪ B) ⇔ (x ∈ A) ∧ (x ∈ B)

.

Operacją sumowania teorimnogościowego rządzą następujące

prawa.

Dla dowolnych zbiorów

A

,

B

,

C

:

(T1)

A ∪ B = B ∪ A

–

przemienność,

(T2)

A ∪ (B ∪ C) = (A ∪ B) ∪ C

–

łączność,

(T3)

∅ ∪ A = A

–

∅

– element neutralny

∪

158

,

(T4)

A ∪ A = A

–

idempotencja

∪

158

158

Element

a

jest elementem neutralnym operacji

f

jeśli dla dowolnego

x

:

f(x, a) = x

.

158

Element

a

jest idempotentny dla operacji

f

jeśli

f(a, a) = a

.

5.4. OPERACJE NA ZBIORACH

279

(T5)

A ∪ X = X

–

X

– element jednostkowy

∪

159

.

Udowodnimy tylko (T2).

DOWÓD

Z definicji sumy teoriomnogościowej zachodzą kolejne równoważ-

ności:

1.

x ∈ [A ∪ (B ∪ C)] ⇔ [x ∈ A ∨ x ∈ (B ∪ C)]

,

2.

[

x ∈ A ∨ x ∈ (B ∪ C)] ⇔ [x ∈ A ∨ (x ∈ B ∨ x ∈ C)]

.

Tezą rachunku logicznego jest:

3.

[

x ∈ A ∨ (x ∈ B ∨ x ∈ C)] ⇔ [(x ∈ A ∨ x ∈ B) ∨ x ∈ C]

.

Ponownie korzystając z definicji sumy teoriomnogościowej mamy:

4.

[(

x ∈ A ∨ x ∈ B) ∨ x ∈ C] ⇔ [x ∈ (A ∪ B) ∨ x ∈ C]

,

5.

[

x ∈ (A ∪ B) ∨ x ∈ C] ⇔ x ∈ [(A ∪ B) ∪ C]

.

Korzystając z przechodniości

⇔

ostatecznie dostajemy:

6.

x ∈ [A ∪ (B ∪ C)] ⇔ x ∈ [(A ∪ B) ∪ C]

.

W związku z łącznością

∪

, zapisując sumę skończonej liczby zbio-

rów możemy opuścić nawiasy. W jakiejkolwiek kolejności byśmy su-
mowali, to zawsze otrzymamy ten sam wynik.

Ponadto, dla dowolnych zbiorów

A

,

B

,

C

,

D

:

(T6)

A ⊆ A ∪ B

,

(T7)

B ⊆ A ∪ B

,

(T8)

A ⊆ C ∧ B ⊆ C ⇒ A ∪ B ⊆ C

,

(T9)

A ⊆ B ∧ C ⊆ D ⇒ A ∪ C ⊆ B ∪ D

,

(T10)

A ⊆ B ⇔ A ∪ B = B

.

Dowiedźmy tylko (T10).

DOWÓD

Ograniczmy się do dowodu tego, że

159

Element

a

jest elementem jednostkowym operacji

f

jeśli dla dowolnego

x

:

f(x, a) = a

.

280

5. ALGEBRA ZBIORÓW

A ∪ B = B ⇒ A ⊆ B

.

Tezą rachunku predykatów jest:

1.

(

x ∈ A ∨ x ∈ B ⇔ x ∈ B) ⇒ (x ∈ A ⇒ x ∈ B)

.

Korzystając z definicji sumy teoriomnogościowej dostajemy:

2.

(

x ∈ A ∪ B ⇔ x ∈ B) ⇒ (x ∈ A ⇒ x ∈ B)

.

Na podstawie definicji zawierania się zbiorów dostajemy:

3.

(

x ∈ A ∪ B ⇔ x ∈ B) ⇒ (A ⊆ B)

.

Z kolei korzystając z definicji równości zbiorów:

4.

(

A ∪ B = B) ⇒ (A ⊆ B)

.

5.4.3. Przecięcie zbiorów

Przecięciem (przekrojem, iloczynem) zbiorów

A

i

B

jest zbiór

A∩B

taki, którego elementami są wszystkie i tylko te przedmioty, które są
elementami zbioru

A

i które są elementami zbioru

B

:

(DEF.

∩

)

(

A ∩ B) = {x ∈ X : x ∈ A ∧ x ∈ B}

.

W sposób równoważny możemy to wyrazić:

∀x.[x ∈ (A ∩ B) ⇔ (x ∈ A) ∧ (x ∈ B)]

.

Symbol „

∩

” to dwuargumentowa litera funkcyjna.

Zauważmy, że

x ∈ (A ∩ B) ⇔ (x ∈ A) ∨ (x ∈ B)

.

Operacją mnożenia zbiorów rządzą następujące prawa.

Dla dowolnych zbiorów

A

,

B

,

C

:

(T1)

A ∩ B = B ∩ A

–

przemienność,

(T2)

A ∩ (B ∩ C) = (A ∩ B) ∩ C

–

łączność,

(T3)

∅ ∩ A = ∅

–

∅

– element jednostkowy

∩

,

(T4)

A ∩ A = A

–

idempotencja

∩

,

(T5)

A ∩ X = A

–

X

– element neutralny

∩

.

Udowodnimy tylko (T2).

DOWÓD

5.4. OPERACJE NA ZBIORACH

281

Z definicji przecięcia zbiorów zachodzą kolejne równoważności:

1.

x ∈ [A ∩ (B ∩ C)] ⇔ [x ∈ A ∧ x ∈ (B ∩ C)]

,

2.

[

x ∈ A ∧ x ∈ (B ∩ C)] ⇔ [x ∈ A ∧ (x ∈ B ∧ x ∈ C)]

.

Tezą rachunku logicznego jest:

3.

[

x ∈ A ∧ (x ∈ B ∧ x ∈ C)] ⇔ [(x ∈ A ∧ x ∈ B) ∧ x ∈ C]

.

Ponownie korzystając z definicji przecięcia dostajemy:

4.

[(

x ∈ A ∧ x ∈ B) ∧ x ∈ C] ⇔ [x ∈ (A ∩ B) ∧ x ∈ C]

,

5.

[

x ∈ (A ∩ B) ∧ x ∈ C] ⇔ x ∈ [(A ∩ B) ∩ C]

.

Korzystając z przechodniości

⇔

ostatecznie mamy:

6.

x ∈ [A ∩ (B ∩ C)] ⇔ x ∈ [(A ∩ B) ∩ C]

.

W związku z łącznością

∩

, zapisując przecięcie skończonej liczby

zbiorów możemy opuścić nawiasy. W jakiejkolwiek kolejności byśmy
brali przecięcie, to zawsze otrzymamy ten sam wynik.

Ponadto, dla dowolnych zbiorów

A

,

B

,

C

,

D

:

(T6)

A ∩ B ⊆ A

,

(T7)

A ∩ B ⊆ B

,

(T8)

A ⊆ B ∧ A ⊆ C ⇒ A ⊆ B ∩ C

,

(T9)

A ⊆ B ∧ C ⊆ D ⇒ A ∩ C ⊆ B ∩ D

,

(T10)

A ⊆ B ⇔ A ∩ B = A

.

Dowiedźmy tylko (T10).

DOWÓD

Ograniczmy się do dowodu tego, że

A ∩ B = A ⇒ A ⊆ B

.

Niech

1.

A ∩ B = A

.

Z 1 na podstawie definicji równości zbiorów:

2.

x ∈ (A ∩ B) ⇔ x ∈ A

.

Z definicji przecięcia zbiorów:

282

5. ALGEBRA ZBIORÓW

3.

x ∈ (A ∩ B) ⇔ (x ∈ A ∧ x ∈ B)

.

Z 2 i 3 mamy:

4.

(

x ∈ A ∧ x ∈ B) ⇔ x ∈ A

.

Tezą rachunku logicznego jest:

5.

[(

x ∈ A ∧ x ∈ B) ⇔ x ∈ A] ⇒ (x ∈ A ⇒ x ∈ B)

.

Z 4 i 5 dostajemy:

6.

x ∈ A ⇒ x ∈ B

.

Z definicji zawierania się zbiorów i 6:

7.

A ⊆ B

.

O dwóch zbiorach

A

i

B

mówimy, że są rozłączne,

A ⊇⊆ B

, wtedy i

tylko wtedy, gdy żaden element jednego ze zbiorów nie jest elementem
drugiego, czyli:

(DEF.

⊇⊆

)

(

A ⊇⊆ B) ⇔ ¬∃x.(x ∈ A ∧ x ∈ B)

.

Zauważmy, że:

(

A ⊇⊆ B) ⇔ (A ∩ B = ∅)

.

5.4.4. Różnica i różnica symetryczna zbiorów

Różnicą zbiorów

A

i

B

jest zbiór

A \ B

, którego elementami są

wszystkie i tylko te elementy zbioru

A

, które nie są elementami zbioru

B

:

(DEF.

\

)

(

A \ B) = {x ∈ X : x ∈ A ∧ ¬x ∈ B}

.

W sposób równoważny możemy to wyrazić:

∀x.[x ∈ (A \ B) ⇔ (x ∈ A) ∧ ¬(x ∈ B)]

.

Symbol „

\

” to dwurgumentowa litera funkcyjna.

Dla dowolnych zbiorów

A

,

B

,

C

,

D

:

(T1)

A \ B ⊆ A,

(T2)

A ⊆ B ∧ C ⊆ D ⇒ A \ D ⊆ B \ C,

(T3)

C ⊆ D ⇒ A \ D ⊆ A \ C,

(T4)

A ⊆ B ⇔ A \ B = ∅.

5.4. OPERACJE NA ZBIORACH

283

Różnicą symetryczną zbiorów

A

i

B

jest zbiór

A . B

, którego ele-

mentami są wszystkie i tylko te elementy zbioru

A

, które nie są ele-

mentami zbioru

B

oraz wszystkie i tylko te elementy zbioru

B

, które

nie są elementami zbioru

A

:

(DEF.

.

)

(

A . B) = [x ∈ X : (x ∈ A ∧ ¬x ∈ B) ∨ (¬x ∈ A ∧ x ∈ B)]

.

Równoważnie możemy to zapisać:

∀x.[x ∈ (A . B) ⇔ (x ∈ A ∧ ¬x ∈ B) ∨ (¬x ∈ A ∧ x ∈ B)]

.

Symbol „

.

” to dwuargumentowa litera funkcyjna.

Zauważmy, że

(

A . B) = (B . A)

.

5.4.5. Związki między działaniami teoriomnogościo-

wymi

Operacja dopełnienia pozostaje w następujących związkach z in-

nymi działaniami teoriomnogościowymi.

Dla dowolnego zbioru

A

i przestrzeni

X

160

:

(T1)

−A = X \ A,

(T2)

A ∪ −A = X ,

(T3)

A ∩ −A = ∅.

Dla dowolnych zbiorów

A

i

B

:

(T4)

−(A ∪ B) = −A ∩ −B,

(T5)

−(A ∩ B) = −A ∪ −B,

(T6)

A \ B = A ∩ −B,

(T7)

A \ B = −(−A ∪ B).

Równości (T4) i (T5) to prawa De Morgana (rachunku zbiorów).

Dla dowolnych zbiorów

A

,

B

i przestrzeni

X

:

(T8)

A ⊆ B ⇔ A ∩ −B = ∅,

(T9)

A ⊆ B ⇔ −A ∪ B = X .

160

Twierdzenia T2 i T3 można by nazwać, odpowiednio, teoriomnogościowym

prawem wyłączonego środka i teoriomnogościowym prawem (nie)sprzeczności. Ist-
nieje ścisły związek między tymi (i innymi) prawami rachunku zbiorów a odpo-
wiednimi prawami rachunku zdań: odrzucenie tych drugich wiąże się z zakwestio-
nowaniem tych pierwszych.

284

5. ALGEBRA ZBIORÓW

Następujące prawa ustalają związki między dodawaniem a mno-

żeniem zbiorów.

Dla dowolnych zbiorów

A

,

B

i

C

:

(T10)

A ∩ (A ∪ B) = A,

(T11)

(

A ∩ B) ∪ B = B,

(T12)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),

(T13)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Równości (T10) i (T11) to prawa absorpcji (pochłaniania). Rów-

ność (T12) to prawo rozdzielności dodawania względem mnożenia.
Równość (T13) to prawo rozdzielności mnożenia względem dodawa-
nia.

Związki między różnicą a sumą określają następujące prawa.

Dla dowolnych zbiorów

A

i

B

:

(T14)

A ∪ (B \ A) = A ∪ B,

(T15)

A ⊆ B ⇒ A ∪ (B \ A) = B.

Kolejne prawo pozwala określić przecięcie za pomocą różnicy.

Dla dowolnych zbiorów

A

i

B

:

(T16)

A \ (A \ B) = A ∩ B.

Między różnicą a dodawaniem i mnożeniem zbiorów zachodzą

następujące związki.

Dla dowolnych zbiorów

A

,

B

,

C

:

(T17)

A \ (B ∪ C) = (A \ B) ∩ (A \ C),

(T18)

A \ (B ∩ C) = (A \ B) ∪ (A \ C).

Równości (T17) i (T18) to prawa De Morgana (dla różnicy).

Można postawić pytanie, ile daje się uzyskać zbiorów z danych

n

zbiorów stosując do nich operacje dodawania, mnożenia i odejmowa-
nia. Dowodzi się, że jest to liczba skończona i wynosi

2

2

n

161

.

5.4.6. Uogólnione suma i przecięcie zbiorów

161

Zob. Kuratowski, Mostowski [1978] s. 39.

5.4. OPERACJE NA ZBIORACH

285

Dotychczas omawialiśmy działania teoriomnogościowe na skoń-

czonej liczbie zbiorów. Sumę i przecięcie można uogólnić na dowolną
rodzinę zbiorów.

Niech

X

będzie niepustą przestrzenią (

X = ∅

). Niech

(

A

t

)

t∈T

bę-

dzie rodziną podzbiorów przestrzeni

X

, gdzie

T

jest zbiorem (indek-

sów).

PRZYKŁAD

Niech przestrzenią będzie zbiór liczb naturalnych

N

. Niech

T

bę-

dzie zbiorem

{1, 2, 3, 4, 5}

.

Niech

(

A

t

)

t∈T

=

{n ∈ N : t < n}

.

Rodzinę zbiorów

(

A

t

)

t∈T

tworzą następujące zbiory:

A

1

=

{2, 3, . . .}; A

2

=

{3, 4, . . .}; A

3

=

{4, 5, . . .}; A

4

=

{5, 6, . . .}; A

5

=

{6, 7, . . .}

.

Gdybyśmy jako

T

wzięli zbiór liczb naturalnych, to rodzina

(

A

t

)

t∈T

miałaby nieskończenie wiele elementów. Jej elementami byłby

wszystkie zbiory (dla każdego

n ∈ N

):

A

n

=

{(n + 1), (n + 2), . . .}

.



Sumą uogólnioną zbiorów rodziny

(

A

t

)

t∈T

jest zbiór

t∈T

A

t

(lub

{A

t

:

t ∈ T }

), którego elementami są wszystkie i tylko te przedmioty,

które są elementem przynajmniej jednego ze zbiorów

(

A

t

)

t∈T

.

(DEF.

)

∀x.{(x ∈



t∈T

A

t

)

⇔ ∃

t∈T

(

x ∈ A

t

)

}.

Przecięciem uogólnionym zbiorów niepustej rodziny

(

A

t

)

t∈T

jest

zbiór



t∈T

A

t

(lub



{A

t

:

t ∈ T }

), którego elementami są wszystkie i

tylko te przedmioty, które są elementami każdego ze zbiorów rodziny

(

A

t

)

t∈T

.

286

5. ALGEBRA ZBIORÓW

(DEF.



)

∀x.{(x ∈



t∈T

A

t

)

⇔ ∀

t∈T

(

x ∈ A

t

)

}.

W wypadku, gdy zbiór

T

jest skończony,

T = {1, 2, . . . , n}

, to



t∈T

A

t

=

A

1

∪ A

2

∪ . . . ∪ A

n

,



t∈T

A

t

=

A

1

∩ A

2

∩ . . . ∩ A

n

.

W wypadku, gdy

T = N

, czyli gdy

T

jest zbiorem liczb natural-

nych piszemy:

∞



n=1

A

n

zamiast



n∈

N

A

n

,

∞



n=1

A

n

zamiast



n∈

N

A

n

.

Omówimy teraz niektóre własności uogólnionych sumy i przecię-

cia.

Dla dowolnej rodziny zbiorów

(

A

t

)

t∈T

, dla każdego

t ∈ T

:

(T1)

A

t

⊆



t∈T

A

t

,

(T2)



t∈T

A

t

⊆ A

t

,

(T3)

A

t

⊆ A ⇒



t∈T

A

t

⊆ A,

5.4. OPERACJE NA ZBIORACH

287

(T4)

A ⊆ A

t

⇒ A ⊆



t∈T

A

t

,

(T5)



t∈T

A

t

∪



t∈T

B

t

=



t∈T

(

A

t

∪ B

t

)

,

(T6)



t∈T

A

t

∩



t∈T

B

t

=



t∈T

(

A

t

∩ B

t

)

.

Udowodnijmy tylko własność (T4).

DOWÓD

Przeprowadzimy dowód niewprost. Niech więc

1.

∀t ∈ T.(A ⊆ A

t

)

,

2.

A ⊆



t∈T

A

t

.

Z definicji zawierania się zbiorów i z 2 mamy, że dla pewnego

a

:

3.

a ∈ A ∧ ¬a ∈



t∈T

A

t

.

Z tego

4.

a ∈ A

,

oraz

5.

¬a ∈



t∈T

A

t

.

Z 5 i definicji uogólnionego przecięcia dostajemy:

6.

∃t ∈ T.¬a ∈ A

t

.

Z 1 mamy:

7.

∀t ∈ T.(a ∈ A ⇒ a ∈ A

t

)

.

Z 4 i 7 zaś dostajemy:

8.

∀t ∈ T.(a ∈ A

t

)

.

Korzystając z prawa De Morgana stwierdzamy sprzeczność mię-

dzy wierszami 6 i 8.

288

5. ALGEBRA ZBIORÓW

Związki między uogólnionymi sumą i przecięciem a relacją inklu-

zji ustalają następujące twierdzenia.

Dla dowolnych rodzin zbiorów

(

A

t

)

t∈T

i

(

B

t

)

t∈T

oraz każdego

t(∈

T )

:

(T7)

(

A

t

⊆ B

t

)

⇒



t∈T

A

t

⊆



t∈T

B

t

,

(T8)

(

A

t

⊆ B

t

)

⇒



t∈T

A

t

⊆



t∈T

B

t

,

(T9)



t∈T

(

A

t

∩ B

t

)

⊆



t∈T

A

t

∩



t∈T

B

t

,

(T10)



t∈T

A

t

∪



t∈T

B

t

⊆



t∈T

(

A

t

∪ B

t

)

.

Kolejne twierdzenia określają związki między dodawaniem i prze-

krojem a uogólnionymi sumą oraz przecięciem.

Dla dowolnej rodziny zbiorów

(

A

t

)

t∈T

i dowolnego zbioru

A

:

(T11)

A ∪



t∈T

A

t

=



t∈T

(

A ∪ A

t

)

,

(T12)

A ∩



t∈T

A

t

=



t∈T

(

A ∩ A

t

)

,

(T13)

A ∪



t∈T

A

t

=



t∈T

(

A ∪ A

t

)

,

(T14)

A ∩



t∈T

A

t

=



t∈T

(

A ∩ A

t

)

.

Udowodnijmy tylko własność (T14), ograniczając się do:

5.4. OPERACJE NA ZBIORACH

289

A ∩



t∈T

A

t

⊆



t∈T

(

A ∩ A

t

)

.

DOWÓD

Niech

1.

x ∈ (A ∩



t∈T

A

t

)

.

Z 1 oraz definicji przecięcia i uogólnionego przecięcia

2.

x ∈ A ∧ ∀t ∈ T.x ∈ A

t

.

Z tego

3.

∀t ∈ T.(x ∈ A ∧ x ∈ A

t

)

.

Z definicji przecięcia więc

4.

∀t ∈ T.x ∈ (A ∩ A

t

)

.

Zatem z definicji uogólnionego przecięcia

5.

x ∈



t∈T

(

A ∩ A

t

)

,

co kończy dowód.

Związki między różnicą a uogólnionymi sumą i przecięciem usta-

lają dwa pierwsze uogólnione prawa De Morgana (dla różnicy), zaś
dla dopełnienia – dwa kolejne uogólnione prawa De Morgana (dla
dopełnienia).

Dla dowolnej rodziny

(

A

t

)

t∈T

i dowolnego zbioru

A

:

(T15)

A \



t∈T

A

t

=



t∈T

(

A \ A

t

)

,

(T16)

A \



t∈T

A

t

=



t∈T

(

A \ A

t

)

,

(T17)

−



t∈T

A

t

=



t∈T

(

−A

t

)

,

290

5. ALGEBRA ZBIORÓW

(T18)

−



t∈T

A

t

=



t∈T

(

−A

t

)

.

Twierdzenia (T17) i (T18) są konsekwencjami, odpowiednio, (T15) i
(T16).

5.5. AKSJOMATY ALGEBRY ZBIORÓW

W powyższych rozważaniach dotyczących algebry zbiorów przyj-

mowano jako pewniki niektóre własności zbiorów i pewne rozumienie
bycia elementem zbioru. Te założenia znajdują jawne sformułowanie
w następujących czterach aksjomatach algebry zbiorów. Stanowią one
system aksjomatów algebry zbiorów.

(I) AKSJOMAT RÓWNOŚCI ZBIORÓW (EKSTENSJONAL-

NOŚCI)

162

.

Jeśli zbiory

A

i

B

nie różnią się swoimi elementami,

to zbiory

A

i

B

są równe.

(II) AKSJOMAT SUMY. Dla dowolnych zbiorów

A

i

B

istnieje

zbiór, którego elementami są wszystkie i tylko elementy zbioru

A

i elementy zbioru

B

.

(III) AKSJOMAT RÓŻNICY. Dla dowolnych zbiorów

A

i

B

istnieje

zbiór, którego elementami są wszystkie i tylko elementy zbioru

A

, które nie są elementami

B

.

(IV) AKSJOMAT ISTNIENIA. Istnieje co najmniej jeden zbiór.

Aksjomaty te nie obejmują wszystkiego tego, co dla potrzeb ma-

tematyki wystarczająco charakteryzowałoby pojęcie zbioru. Zwykle
oprócz podanych wyżej czterech aksjomatów przyjmuje się jeszcze
kolejne trzy. Wszystkie te aksjomaty pochodzą od E. Zermelo.

(V) AKSJOMAT PODZBIORÓW (WYRÓŻNIANIA). Dla każ-

dego zbioru

X

i każdej formuły

φ

z jedną zmienną wolną, któ-

rej zakresem jest zbiór

X

istnieje zbiór, którego elementami są

wszystkie i tylko elementy zbioru

X

, które spełniają

φ

.

162

Por. z zasadą ekstensjonalności.

5.5. AKSJOMATY ALGEBRY ZBIORÓW

291

Naiwna intuicja zbioru mogłaby nas skłaniać do przyjęcia ak-

sjomatu mocniejszego, a mianowicie aksjomatu głoszącego, że dla
dowolnej własności (formuły) istnieje zbiór wszystkich i tylko tych
przedmiotów, które tę własność posiadają (lub, odpowiednio, zbiór
przedmiotów spełniających formułę). Twórca teorii mnogości, Can-
tor, przynajmniej w początkowym okresie, wierzył w prawdziwość
takiego aksjomatu. W jego pracy [1883] znajdujemy zdanie „Istnieje
zbiór

X

złożony ze wszystkich obiektów

x

spełniających

φ(x)

.” Oka-

zuje się jednak, że taki aksjomat prowadzi do sprzeczności (antyno-
mii). Jest tak np. w wypadku antynomii Russella.

φ(x) ⇔ (x

jest zbiorem

)

∧ (x ∈ x)

.

Niech

R = {x : φ(x)}

,

czyli

R = {x : x

jest zbiorem

∧ x ∈ x}

.

Jeśli przyjmiemy, że każda własność wyznacza zbiór, to

R

jest

zbiorem. Zasadne staje się więc pytanie, czy

R

jest elementem

R

. Z

definicji

R

mamy, że

R ∈ R ⇔ R ∈ R

,

co jest ewidentną sprzecznością

163

.

Aksjomat wyróżniania pozwala z każdego zbioru wyróżnić pod-

zbiór jego elementów posiadających określoną własność. W szczegól-
ności zapewnia istnienie zbioru pustego. Zbiór ten zawiera się w każ-
dym zbiorze, ponieważ można go wyróżnić z każdego zbioru, a mia-
nowicie jako

{x ∈ A : ¬x = x}

.

(VI) AKSJOMAT ZBIORU POTĘGOWEGO. Dla każdego zbioru

X

istnieje zbiór

2

X

, zwany zbiorem potęgowym zbioru

X

, któ-

rego elementami są wszystkie i tylko podzbiory zbioru

X

.

Zbiór potęgowy bywa oznaczany „P(X)” – od angielskiego

163

Antynomia ta po raz pierwszy została opublikowana w dodatku do książki

Fregego Grundgesetze der Arithmetik, t. 2 [1903]. Zainteresowanego czytelnika
odsyłam do: Murawski [1986]. Zob. „List do G. Fregego”, s. 221–222; oraz –
stanowiący odpowiedź – „List do B. Russella”, s. 203–204.

292

5. ALGEBRA ZBIORÓW

Power lub też „C(X)” – od Cantora. Aksjomat ten pozwala tworzyć
dowolnie duże zbiory.

(VII) AKSJOMAT WYBORU (PEWNIK WYBORU). Dla każdej

rodziny zbiorów niepustych i rozłącznych istnieje zbiór, który z
każdym ze zbiorów z tej rodziny ma jeden i tylko jeden wspólny
element.

Pewnik wyboru należy do chyba najbardziej dyskutowanych

aksjomatów. Zajmuje on dość specyficzną pozycję w systemie teorii
mnogości. Używany był dość wcześnie, m.in. przez Cantora, który jed-
nak nie czuł, że wymaga on szczególnego traktowania. Po raz pierw-
szy wprost wspomniał o nim Peano [1890] w związku z problemem
rozwiązania układu równań różniczkowych. W 1902 wyraźnie zasto-
sował go Beppo Levi. Wprost został sformułowany dopiero przez Ze-
rmelo w 1904 r. w dowodzie twierdzenia Zermelo, że każdy zbiór może
być dobrze uporządkowany. Stąd bywa nazywany pewnikiem Zermelo.

´

Emile Borel pokazał, że pewnik wyboru jest równoważny twierdzeniu
Zermelo. Z jednej strony okazuje się być niezbędny do dowodu wielu
intuicyjnie prawdziwych twierdzeń. Z drugiej strony za jego pomocą
dowodzi się wielu twierdzeń nieintuicyjnych, jak np. twierdzenie Ba-
nacha-Tarskiego o paradoksalnym rozkładzie kuli

163

.

Wielu matema-

tyków przyjmuje go więc z nieufnością. Uważa się, że dowody oparte
na pewniku wyboru mają inną naturę niż bez jego zastosowania. Jest
tak dlatego, że pewnik ten postuluje istnienie zbioru bez podania
metody jego skonstruowania, tj. ma charakter nieefektywny. Dlatego
w wielu podręcznikach teorii mnogości dowody z użyciem pewnika
wyboru są specjalnie oznakowane. Fakt przyjmowania go jako aksjo-
matu jest również zaznaczany w nazwie danego systemu aksjomatycz-
nego. Na przykład ZFC to system aksjomatyczny Zermelo-Fraenkla
z aksjomatem wyboru (Choice – ang.: wybór). Niesprzeczność aksjo-
matu wyboru udowodnił G¨

odel [1940]. Niezależność aksjomatu wy-

boru od pozostałych aksjomatów teorii mnogości dowiedziona została
w 1964 r. przez Cohen’a [1966]. Istnieje ogólniejsza wersja aksjomatu

163

Do roli pewnika wyboru w dowodach twierdzeń szczególną uwagę przy-

wiązywał Sierpiński. Począwszy od 1918 opublikował wiele prac poświęconych tej
kwestii. Zob. Sierpiński [1975].

5.5. AKSJOMATY ALGEBRY ZBIORÓW

293

wyboru, która nie wymaga rozłączności zbiorów. Postuluje się istnie-
nie funkcji, która każdemu elementowi rodziny niepustych zbiorów
przyporządkowuje ich element. Ta funkcja to funkcja wyboru. Istnieje
wiele twierdzeń równoważnych pewnikowi wyboru

164

.

Zasadą alterna-

tywną do pewnika wyboru jest aksjomat determinacji sformułowany
przez Jana Mycielskiego i Hugona Steinhausa [1962].

Aksjomaty (I)–(VII) są zależne. Na przykład, można pominąć

aksjomat algebry zbiorów o istnieniu różnicy. Wynika on z aksjomatu
podzbiorów.

Aksjomatyczne ujęcie teorii mnogości zostało równocześnie i

niezależnie od siebie zaproponowane w 1908 r. przez Zermelo i Rus-
sella. Ujęcia te różnią się istotnie.

Zermelo wyeliminował antynomie, ograniczając rozmiar zbio-

rów. Ich źródła upatrywał w pewniku abstrakcji

165

:

∃x.∀y.[y ∈ x ⇔ φ(y)]

.

Pewnik ten dopuszcza istnienie zbiorów (

x

) przedmiotów (

y

) o dowol-

nej cesze

φ

. W szczególności mogą to być „bardzo duże” zbiory, jakimi

są zbiór wszystkich zbiorów i zbiór wszystkich zbiorów, które nie są
swoimi elementami. Zermelo w miejsce pewnika abstrakcji przyjął
aksjomat wyróżniania:

∀z.∃x.∀y.[y ∈ x ⇔ y ∈ z ∧ φ(y)]

.

Teraz przyjmuje się istnienie zbiorów (

x

) przedmiotów (

y

) o dowolnej

cesze

φ

, ale tylko tych przedmiotów, które są elementami jakiegoś

zbioru (

z

).

Russell w Principia Mathematica zaproponował (rozgałęzioną)

teorię typów, która zakładała nieskończoną hierarchię zbiorów wy-
znaczoną przez ogół własności. Nie były możliwe klasy zbiorów o
własnościach mieszanych, tzn. takich, które przysługiwałyby zarówno
przedmiotom jak i zbiorom tych przedmiotów. Rozwiązanie Russella

164

Szerzej na ten temat zob. Jech [1973] oraz Rubin i Rubin [1963].

165

W sprawie innego stanowiska w kwestii motywów, którymi kierował się

Zermelo zob. Murawski [1995], s. 171.

294

5. ALGEBRA ZBIORÓW

zmodyfikowali Chwistek i Ramsey proponując uproszczoną teorię ty-
pów. Koncepcja typu, antycypowana przez Schr¨

odera i Fregego, była

przez Russella uznana za naturalną i zgodną ze zdrowym rozsądkiem.

Oba rozwiązania, Zermelo i Russella, znalazły licznych zwolen-

ników. Do lat pięćdziesiątych większe wzięcie miało ujęcie Russella.
Dzisiaj standardem są rozwiązania oparte na propozycji Zermelo.

Obie koncepcje, Russella i Zermelo, miały pewne wady, usu-

nięte przez innych jeszcze w latach dwudziestych, w szczególności
w wypadku aksjomatyki Zermelo przez Fraenkla i Thoralfa A. Sko-
lema. System ten oznacza się ZF lub – gdy dołączony jest aksjomat
wyboru (Axiom of Choice) – ZFC. Inną propozycję przedstawił John
von Neumann (1924). W wyniku jej rozwoju powstała teoria mno-
gości von Neumanna-G¨

odla-Bernaysa zwykle oznaczana GB. Można

tu wspomnieć jeszcze o systemie Morse’a (1956) teorii mnogości i o
koncepcji Wilhelma Ackermana. Mówi się o niekantorowskiej teorii
zbiorów

166

.

Najnowsze pomysły wiążą się z dociekaniami matematy-

ków czeskich związanych z Peterem Vopˇ

enką

167

.

Do podejścia Russella

nawiązują propozycje Quine’a

168

.

Jego system, oznaczany NF, łączy

rozwiązanie Zermelo ograniczenia istnienia zbiorów z ideą Russella –
odrzucenia niektórych wyrażeń jako niepoprawnych.

Powyżej podana aksjomatyka Zermelo teorii mnogości nie jest

przedstawiona w języku formalnym. Podamy inną wersję aksjoma-
tyki Zermelo zgodną ze współczesnymi wymogami formułowania sys-
temów aksjomatycznych. Jest to system dedukcyjnie bardzo mocny:
na tym systemie w zasadzie może być oparta cała współczesna ma-
tematyka.

166

Zob. Cohen, Reuben [1967].

167

Zob. Vopˇ

enka, Hajek [1972], Vopˇ

enka [1979]. Zdaniem Vopˇ

enki teza o ist-

nieniu aktualnej nieskończoności to dogmat współczesnej teorii mnogości. Mate-
matycy nie tylko wierzą w ten dogmat. Usiłują go narzucić też innym. W świecie
realnym zaś nie ma aktualnie nieskończonych zbiorów. Pojęcie takiego zbioru nie
ma więc sensu fenomenologicznego. Teoria zależy zatem od ustaleń formalnych i
one stają się jedynym kryterium poprawności. To właśnie jest prawdziwym źró-
dłem trudności teorii mnogości.

168

Zob. Quine [1937], [1940].

5.5. AKSJOMATY ALGEBRY ZBIORÓW

295

JĘZYK

Językiem teorii mnogości jest język rachunku predykatów z

identycznością z dwoma literami predykatowymi:

Z

– jednoargumen-

towa;

∈

– dwuargumentowa.

Intuicyjnie rzecz biorąc

Z

rozumiemy:

. . .

jest zbiorem; a

∈

:

. . .

jest elementem

. . .

.

System ten oparty jest na rachunku predykatów z identyczno-

ścią. Aksjomatami specyficznymi są:

(I) AKSJOMAT EKSTENSJONALNOŚCI

∀x, y.[Z(x) ∧ Z(y) ∧ ∀z.(z ∈ x ⇔ z ∈ y) ⇒ x = y].

(II) AKSJOMAT PARY

∀x, y.∃z.[Z(z) ∧ ∀u.(u ∈ z ⇔ u = x ∨ u = y)].

Aksjomat ten głosi, że dla każdych dwóch przedmiotów istnieje zbiór,
którego elementami są te i tylko te przedmioty.

(III) AKSJOMAT WYRÓŻNIANIA

. . . ∀x.{Z(x) ⇒ ∃y.[Z(y) ∧ ∀z.(z ∈ y ⇔ z ∈ x ∧ φ(z))]},

gdzie

φ(z)

jest dowolną formułą nie zawierającą

y

jako zmiennej wol-

nej. Aksjomat wyróżniania jest schematem zdań, które otrzymujemy
wstawiając w miejsce

φ(z)

konkretne formuły, które oprócz zmiennej

wolnej

z

mogą zawierać też inne zmienne wolne (za wyjątkiem

y

).

Zmienne te wiążemy kwantyfikatorem ogólnym. Kropki znajdujące
się na początku schematu, „

. . .

”, wskazują na miejsce dla kwantyfika-

torów wiążących te zmienne.

(IV) AKSJOMAT ZBIORU POTĘGOWEGO

∀x.{Z(x) ⇒ ∃y.[Z(y) ∧ ∀z.(z ∈ y ⇔ Z(z) ∧ ∀u.(u ∈ z ⇒ u ∈ x))]}.

296

5. ALGEBRA ZBIORÓW

(V) AKSJOMAT SUMY

∀x.{Z(x) ∧ ∀y.(y ∈ x ⇒ Z(y)) ⇒

∃z.[Z(z) ∧ ∀y.(y ∈ z ⇔ ∃u.(u ∈ x ∧ y ∈ u))]}

.

Aksjomat ten głosi, że dla każdej rodziny zbiorów

x

istnieje jej suma,

tzn. taki zbiór

z

, którego elementami są wszystkie i tylko te przed-

mioty, które należą do co najmniej jednego elementu rodziny zbiorów

x

.

(VI) AKSJOMAT WYBORU

∀x.{[Z(x) ∧ ∀y.[y ∈ x ⇒ Z(y) ∧ ∃z.(z ∈ y)] ∧ ∀y, u.(y ∈ x ∧ u ∈ x ⇒

y = u ∨ ¬∃v.(v ∈ y ∧ v ∈ u))] ⇒ ∃w.{Z(w) ∧ ∀y.[y ∈ x ⇒

∃z.(z ∈ y ∧ z ∈ w ∧ ∀v.(v ∈ y ∧ v ∈ w ⇒ v = z))]}}

.

(VII) AKSJOMAT NIESKOŃCZONOŚCI

∃x.{Z(x) ∧ ∃y.[Z(y) ∧ ¬∃z.(z ∈ y) ∧ y ∈ x] ∧ ∀y.[y ∈ x ⇒

∀z.[Z(z) ∧ ∀u.(u ∈ z ⇔ u = y) ⇒ z ∈ x]]}

.

Biorąc symbol „

∅

” na oznaczenie zbioru pustego, a „

{y}

” jako zbiór,

którego jedynym elementem jest

y

, aksjomat (VII) można zapisać

znacznie krócej:

(VII’) AKSJOMAT NIESKOŃCZONOŚCI

∃x.[Z(x) ∧ ∅ ∈ x ∧ ∀y.(y ∈ x ⇒ {y} ∈ x)].

Na podstawie tego aksjomatu stwierdzamy istnienie zbioru,

którego elementami są:

∅, {∅}, {{∅}}, . . .

.