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 Cantor122 .

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 Cantora123 . 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�śttingen.

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 matematycy 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ści125 .

Jednak – powtarzając za Whiteheadem – a contradiction is not a

failure, it’s an opportunity126 . 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 paradoks 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 aksjomaty 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-

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

tego stosu jest obiektem abstrakcyjnym131 . 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�ńsst, 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 przedmiotem 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 kamieni132 .

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 desygnatem133 . 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 koncepcji 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 relatywnym, 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ć zbiorami136 . 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ślone137 . 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ów138 .

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 podstawowy 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) �" xy

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 , . . . , an to zbiór

{a 0 , a 1 , . . . , an}

lub, gdy są to przedmioty at przyporządkowane elementom zbioru T

{at : 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ę

zbioru141 . 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�źcken 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ÓD142

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 oczywiste. 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 koekstensywne143 , 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 zbiorach145 .

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ów146 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ów148 .

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

się pod pseudonimem Nicolas Bourbaki, w autobiografi sobie przypisuje wprowadzenie 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 algebrze149 .

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ów150 . 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 indywiduowa151 .

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ów152 , 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ÓW153

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 przedmiotó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ł matematyk 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 podzbiorem 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 predykatowa156 .

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 elementami 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. Istnieje ś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 22 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 ( At) t∈T bę-

dzie rodziną podzbiorów przestrzeni X , gdzie T jest zbiorem (indeksów).

PRZYKŁAD

Niech przestrzenią będzie zbiór liczb naturalnych N. Niech T bę-

dzie zbiorem { 1 , 2 , 3 , 4 , 5 }.

Niech

( At) t∈T = {n ∈ N : t < n}.

Rodzinę zbiorów ( At) 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

( At) t∈T miałaby nieskończenie wiele elementów. Jej elementami byłby wszystkie zbiory (dla każdego n ∈ N):

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



Sumą uogólnioną zbiorów rodziny ( At) t∈T jest zbiór

A

t∈T

t (lub

{At : t ∈ T}), którego elementami są wszystkie i tylko te przedmioty, które są elementem przynajmniej jednego ze zbiorów ( At) t∈T .





(DEF.

)

∀x.{( x ∈

At) �" ∃t∈T ( x ∈ At) }.

t∈T

Przecięciem uogólnionym zbiorów niepustej rodziny ( At) t∈T jest





zbiór

A

{A

t∈T

t (lub

t : t ∈ T }), którego elementami są wszystkie i

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

( At) t∈T .



286

5. ALGEBRA ZBIORÓW





(DEF.

)

∀x.{( x ∈

At) �" ∀t∈T ( x ∈ At) }.

t∈T

W wypadku, gdy zbiór T jest skończony, T = { 1 , 2 , . . . , n}, to

At = A 1 ∪A 2 ∪...∪An,

t∈T

At = A 1 ∩A 2 ∩...∩An.

t∈T

W wypadku, gdy T = N, czyli gdy T jest zbiorem liczb naturalnych piszemy:

�ś





An

zamiast

An,

n=1

n∈ N

�ś





An

zamiast

An.

n=1

n∈ N

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

cia.

Dla dowolnej rodziny zbiorów ( At) t∈T , dla każdego t ∈ T : (T1)



At �ą

At,

t∈T

(T2)

At �ą At,

t∈T

(T3)



At �ą A �ł

At �ą A,

t∈T





5.4. OPERACJE NA ZBIORACH

287

(T4)



A �ą At �ł A �ą

At,

t∈T

(T5)





At ∪

Bt =

( At ∪ Bt) ,

t∈T

t∈T

t∈T

(T6)





At ∩

Bt =

( At ∩ Bt) .

t∈T

t∈T

t∈T

Udowodnijmy tylko własność (T4).

DOWÓD

Przeprowadzimy dowód niewprost. Niech więc

1. ∀t ∈ T. ( A �ą At),



2. A �ą

A

t∈T

t.

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



3. a ∈ A �ż �Źa ∈

A

t∈T

t.

Z tego

4. a ∈ A,

oraz



5. �Źa ∈

A

t∈T

t.

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

6. ∃t ∈ T.�Źa ∈ At.

Z 1 mamy:

7. ∀t ∈ T. ( a ∈ A �ł a ∈ At).

Z 4 i 7 zaś dostajemy:

8. ∀t ∈ T. ( a ∈ At).

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 ( At) t∈T i ( Bt) t∈T oraz każdego t( ∈

T ):

(T7)





( At �ą Bt) �ł

At �ą

Bt,

t∈T

t∈T

(T8)





( At �ą Bt) �ł

At �ą

Bt,

t∈T

t∈T

(T9)





( At ∩ Bt) �ą

At ∩

Bt,

t∈T

t∈T

t∈T

(T10)





At ∪

Bt �ą

( At ∪ Bt) .

t∈T

t∈T

t∈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 ( At) t∈T i dowolnego zbioru A: (T11)





A ∪

At =

( A ∪ At) ,

t∈T

t∈T

(T12)





A ∩

At =

( A ∩ At) ,

t∈T

t∈T

(T13)





A ∪

At =

( A ∪ At) ,

t∈T

t∈T

(T14)





A ∩

At =

( A ∩ At) .

t∈T

t∈T

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





5.4. OPERACJE NA ZBIORACH

289





A ∩

At �ą

( A ∩ At) .

t∈T

t∈T

DOWÓD

Niech



1. x ∈ ( A ∩

A

t∈T

t).

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

2. x ∈ A �ż ∀t ∈ T.x ∈ At.

Z tego

3. ∀t ∈ T. ( x ∈ A �ż x ∈ At) .

Z definicji przecięcia więc

4. ∀t ∈ T.x ∈ ( A ∩ At) .

Zatem z definicji uogólnionego przecięcia



5. x ∈ t∈T ( A ∩ At) ,

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 ( At) t∈T i dowolnego zbioru A:

(T15)





A \

At =

( A \ At) ,

t∈T

t∈T

(T16)





A \

At =

( A \ At) ,

t∈T

t∈T

(T17)





�ł

At =

( �łAt) ,

t∈T

t∈T





290

5. ALGEBRA ZBIORÓW

(T18)





�ł

At =

( �łAt) .

t∈T

t∈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).” Okazuje 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

P ower 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.

Émile 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 kuli163 . 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ść aksjomatu wyboru udowodnił G�śdel [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 wyboru164. 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 dowolnej 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�śdera 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�śdla-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ów166 . Najnowsze pomysły wiążą się z dociekaniami matematy-

ków czeskich związanych z Peterem Vopěnką167. Do podejścia Russella

nawiązują propozycje Quine’a168 . 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ěnka, Hajek [1972], Vopěnka [1979]. Zdaniem Vopěnki teza o ist-

nieniu aktualnej nieskończoności to dogmat współczesnej teorii mnogości. Matematycy 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 wolnej. 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 kwantyfikatoró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 przedmioty, 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ą: �, {�}, {{�}}, . . .