2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

2

Algebra zbiorów

T

eorię zbiorów zainicjował Georg Cantor jako część większej teorii zwanej
teorią mnogości. Jednak pojęcie zbioru nie było przez Cantora rozumiane w

pełni poprawnie. Można powiedzieć, że początkowo (patrz określenie z [2]) była to
tzw. „naiwna” teoria mnogości. Różni się ona od obecnej opartej w dużej mierze na
odkryciaciach B. Russela i innych ale przede wszystkim na odkryciach K. G¨odla

1

.

Od kiedy w tej teorii pojawiły się licznie antynomie, ... „w toku polemiki, jaka
wywiązała się dokoła antynomii, okazało się wyraźnie, że różni matematycy wiążą
istotnie różne intuicje z pojęciem zbioru”. Podany dalej system aksjomatów teorii
mnogości ma co prawda swoje źródło w intuicji, to owa intuicyjna treść nie będzie
- „dzięki metodzie aksjomatycznej - interweniowała w dowodach twierdzeń ani w
definicjach pojęć teorii mnogości”.

2.1

Zbiory i działania na zbiorach

Cantor, 1895 ([20]): Przez zbiór rozumiemy zgromadzenie w jedną całość wyraźnie
określonych, rozróżnialnych obiektów naszej intuicji lub naszej myśli. Obiekty te na-
zywamy elementami zbiorów. Pojęciami pierwotnymi teorii są:
zbiory, które oznaczać będziemy dużymi literami alfabetu łacińskiego,
elementy tych zbiorów, które oznaczać będziemy małymi literami oraz stwierdzenie:
x

jest elementem zbioru X, co zapisujemy

1

x

∈ X - x należy do X. Aby zaznaczyć,

że x nie jest elementem zbioru X piszemy x 6∈ X. Zatem

x

6∈ X ⇔∼ (x ∈ X).

1

E. Nagel i J.R. Newman tak piszą o odkryciu G¨odla w [21]: „Co mianowicie i w jaki sposób

udowodnił G¨odel? Zasadnicza jego konkluzja była dwojaka. Przede wszystkim (choć kolejność rze-
czywistej argumentacji G¨odla była inna) wykazał on, że nie można podać metamatematycznego
dowodu niesprzeczności systemu, który jest dostatecznie bogaty, aby zawierać całą arytmetykę -
o ile dowód ten nie korzysta z takich reguł wnioskowania, które pod pewnym istotnym względem
różnią się od reguł transformacji służących wywodzeniu twierdzeń w owym systemie. Dowód korzy-
stający z takich reguł może, oczywiście, posiadać dużą wartość i doniosłość teoretyczną. Ponieważ
jednak rozumowanie w nim zawarte opiera się na mocniejszych regułach wnioskowania niż reguły
rachunku arytmetycznego, tak, że niesprzeczność założeń tego rozumowania jest rzeczą co najmniej
równie wątpliwą jak niesprzeczność arytmetyki, więc dowód ten stanowi sukces tylko pozorny: na
miejscu ściętej głowy smoka wyrasta druga. W każdym razie, o ile dowód nie jest finistyczny, to
nie zadośćuczyni wymaganiom oryginalnego programu Hilberta; tymczasem argumentacja G¨odla
wskazuje, że zbudowanie finistycznego dowodu niesprzeczności arytmetyki jest mało prawdopodob-
ne.

Drugi ważny rezultat uzyskany przez G¨odla jest bodaj bardziej jeszcze nieoczekiwany i rewolu-

cyjny, wskazuje bowiem na pewną istotną ograniczoność metody aksjomatycznej. G¨odel dowiódł,
że Principia i każdy inny system, w którym można zbudować arytmetykę, jest zasadniczo nie-
zupełny. Innymi słowy, dla dowolnego niesprzecznego zbioru aksjomatów arytmetycznych istnieje
takie prawdziwe zdanie arytmetyczne, którego nie można wydedukować z tego zbioru.” Powiedzmy
więcej, G¨odel wykazał, że nie istnieje możliwość uzupełnienia systemu aksjomatów do pewnego sys-
temu zawierającego skończoną liczbę aksjomatów, w którym nie byłoby zdań nie rozstrzygniętych.
Dodajmy, że bardzo istotne w teorii mnogości okazały się prace K. G¨odla dotyczące pojęcia klasy.

1

Oznaczenie x

∈ X zaproponował matematyk włoski G. Peano i pochodzi ono od greckiego

słowa `

στ

´ι (po polsku „być”).

21

2.1 Zbiory i działania na zbiorach

2 ALGEBRA ZBIORÓW

Inkluzja zbiorów

Definicja 2.1

Mówimy, że zbiór A zawiera się w zbiorze B lub, że A jest podzbiorem

zbioru B, jeżeli każdy element zbioru A jest elementem zbioru B; oznaczamy to sym-
bolicznie A ⊂ B. Mamy więc

A

⊂ B ⇔ ∀

a

[(a ∈ A) ⇒ (a ∈ B)].

Zasada równości zbiorów

Definicja 2.2

Mówimy, że dwa zbiory A i B są identyczne, jeżeli A ⊂ B i B ⊂ A

i piszemy wtedy A = B. Zatem:

A

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

Zbiór pusty

Definicja 2.3 Zbiorem pustym nazywamy zbiór, który nie posiada żadnego elemen-
tu. Oznaczamy go symbolem ∅.

Lemat 2.1 Zbiór pusty ma własności:

1

o

. Zbiór pusty jest podzbiorem dowolnego zbioru.

2

o

. Istnieje co najwyżej jeden

2

zbiór pusty.

Dw.

ad 1

o

. Dla dow. zbioru A, implikacja x ∈ ∅ ⇒ x ∈ A jest prawdziwa, bo

poprzednik implikacji jest zdaniem fałszywym. Stąd ∅ ⊂ A. Wobec dowolności zbioru
A

, dowodzi to prawdziwości tezy.

ad 2

o

. Dowód tego faktu poprowadzimy nie wprost. Przypuśćmy, że istnieje zbiór

pusty ∅

1

taki, że ∅

1

6= ∅. Oznacza to, że ∼ (∅ = ∅

1

). Zatem

∼ ∀

x

[(x ∈ ∅) ⇔ (x ∈ ∅

1

)] ⇔ ∃

x

0

∼ [(x

0

∈ ∅) ⇔ (x

0

∈ ∅

1

)] ⇔

∃

x

0

[∼ (x

0

∈ ∅)∨ ∼ (x

0

∈ ∅

1

)] ⇔ ∃

x

0

[(x

0

6∈ ∅)∨(x

0

6∈ ∅

1

)].

Ostatnie zdanie ma postać alternatywy wykluczającej; ta zaś jest prawdziwa w. i t.
w.

3

gdy jeden z jej członów jest prawdziwy i jednocześnie drugi jest fałszywy.

Oznacza to, że przynajmniej jeden ze zbiorów ∅ i ∅

1

nie jest zbiorem pustym,

wbrew założeniu. W myśl reguły dowodzenia nie wprost (wg tautologii (∼ p ⇒ 0) ⇒
p

), istnieje tylko jeden zbiór pusty.



Podzbiory właściwe i niewłaściwe danego zbioru

Definicja 2.4

Zbiór pusty jest podzbiorem niewłaściwym dowolnego zbioru A. Dru-

gim podzbiorem niewłaściwym zbioru A jest sam zbiór A. Pozostałe podzbiory

1

zbioru A określa się mianem podzbiorów właściwych zbioru A.

2

Istnienie zbioru pustego wynika z przyjętych dalej aksjomatów.

3

skrót „w.it.w.,gdy,” oznacza wtedy i tylko wtedy, gdy.

1

Zamiast A

⊂ B piszemy też B ⊃ A i czytamy „B jest nadzbiorem A”. Jeżeli A nie jest

podzbiorem zbioru B, piszemy A

6⊂ B lub B 6⊃ A.

22

2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

Sposoby zapisywania zbiorów

a) Zbiór możemy określić poprzez podanie jego elementów, np.

Zbiory liczbowe: {1}, {1, 2, . . . , 100},

Zbiory o danych elementach (niekoniecznie liczbowych) np. {a}, {a, b}.

b) Zbiór elementów mających pewną własność

2

np. {x ∈ X : ϕ(x)}, {x ∈ Z : |z| >

10}, {x ∈ R : |x| ¬ 1}.

2.1.1

Podstawowe działania na zbiorach

Dodawanie zbiorów

.

Definicja 2.5 Sumą mnogościową zbiorów A i B nazywamy zbiór

A

∪ B = {x : (x ∈ A) ∨ (x ∈ B)}.

Mnożenie zbiorów

.

Definicja 2.6 Iloczynem zbiorów (przekrojem zbiorów) A i B nazywamy zbiór

A

∩ B = {x : (x ∈ A) ∧ (x ∈ B)}.

Różnica zbiorów

.

Definicja 2.7 Różnicą zbiorów A i B nazywamy zbiór

A

\ B = {x : x ∈ A ∧ x 6∈ B}.

Dopełnienie zbioru A do zbioru X

.

Definicja 2.8 Dopełnieniem zbioru A do zbioru X nazywamy różnicę zbiorów
X

i A. Piszemy: A

0

= X \ A.

2.1.2

Zbiór potęgowy

Definicja 2.9

Niech X będzie zbiorem niepustym; będziemy go nazywać odtąd

przestrzenią. Symbolem 2

X

lub P(X) oznaczać będziemy rodzinę wszystkich pod-

zbiorów zbioru X. Rodzinę P(X) nazywać będziemy zbiorem potęgowym zbioru X.

Przykład 2.1

Zbiór potęgowy zbioru skończonego (liczbowego) A = {0, 1, 2} jest

postaci:

2

A

= {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, A}

i liczy dokładnie 8 = 2

3

elementów.

2

Zbiór taki istnieje na mocy pewnika podanego później.

23

2.1 Zbiory i działania na zbiorach

2 ALGEBRA ZBIORÓW

∗∗ Zbiór potęgowy jako struktura algebraiczna
W

P(X) można określić działania dwuargumentowe: dodawanie zbiorów i mnożenie

zbiorów:

∪ : P(X) × P(X) → P(X)

(A, B)

7→ A ∪ B

∩ : P(X) × P(X) → P(X)

(A, B)

7→ A ∩ B

oraz działanie jednoargumentowe „dopełnienie zbioru do przestrzeni”:

0

:

P(X) → P(X)

A

7→ A

0 df

= X

\ A

Wyróżniamy też stałe: zbiór pusty

∅ oraz całą przestrzeń X.

2.1.3

Prawa rachunku zbiorów

Oto zestawienie ważniejszych praw rachunku zbiorów. Dla dow. elementów A, B, C
przestrzeni P(X) mamy:

A

∪ B = B ∪ A

przemienność dodawania

A

∩ B = B ∩ A

przemienność mnożenia

A

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

łączność dodawania

A

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

łączność mnożenia

(A ∪ B)

0

= A

0

∩ B

0

pr. de Morgana

(A ∩ B)

0

= A

0

∪ B

0

pr. de Morgana

A

∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) rozdzielność mnożenia wzgl. dodawania

A

∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) rozdzielność dodawania wzgl. mnożenia

X

∪ X = X ∧ X ∩ X = X

X

∪ ∅ = X ∧ X ∩ ∅ = ∅

A

∩ B = (A ∪ B) \ (A ÷ B)

A

\ B = A \ (A ∩ B)

A

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

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

Symbolem A

÷ B oznaczamy tutaj różnicę symetryczna zbiorów A i B:

x

∈ A ÷ B ⇔ x ∈ (A \ B) ∪ (B \ A).

Ilustracja graficzna praw de Morgana algebry zbiorów

.

Stosujemy tzw. Schemat Venna; przetrzeń identyfikujemy z częścią płaszczyzny (np. prostokątem),
elementy przestrzeni X ilustrujemy przy użyciu figur (np. kół) na płaszczyźnie.podzbiory zbioru
X

.

Rys.1

&%

'$

&%

'$

A

B





















































(A ∪ B)

0

Rys.2

&%

'$

&%

'$

A

B

















 









 



A

0

24

2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

Zbiór (A

∪ B)

0

- zakreskowany w stylu „krata szkocka”, zbiór A

0

zakreślony jest liniami ukośnymi

typu  ;

Rys.3

&%

'$

&%

'$

A

B





























B

0

Rys.4

&%

'$

&%

'$

A

B























 

























 



A

0

∩ B

0

Zbiór B

0

zakreślony jest liniami ukośnymi typu  , zbiór A

0

∩ B

0

zakreślony jest (ponownie) w

„kratę szkocką”; „Równość” zbiorów zakreskowanych na rysunkach 1 i 4 podwójnymi liniami jest
oczywista.

2.2

Działania uogólnione

2.2.1

Rodzina indeksowana zbiorów

Dany jest zbiór potęgowy P(X) zbioru X oraz niepusty zbiór indeksów I.

Definicja 2.10

Funkcję

Φ : I →

P(X)

i

7→ Φ(i)

not

= Φ

i

nazywamy rodziną indeksowaną zbiorów - podzbiorów zbioru X.

Przykład 2.2

Niech I = N

0

, gdzie N

0

Df

= {n ∈ N : n ­ 0}, oraz X = R. Przyjmu-

jemy Φ

i

= A

i

= [i, i + 1), i ∈ I. Mamy zatem:

A

0

= [0, 1), A

1

= [1, 2), . . . , A

n

= [n, n + 1), . . . .

2.2.2

Suma i iloczyn uogólniony zbiorów

Niech Φ : I → P(X) będzie rodziną indeksowaną podzbiorów zbioru X.

Definicja 2.11 Sumą uogólnioną (iloczynem uogólnionym) podzbiorów rodziny Φ
nazywamy zbiór:

[

i

∈I

Φ

i

df

= {x ∈ X : ∃

i

∈I

x

∈ Φ

i

}

\

i

∈I

Φ

i

df

= {x ∈ X : ∀

i

∈I

x

∈ Φ

i

}

!

.

Jeżeli zbiór indeksów jest przeliczalny

1

, I = N, to notujemy

[

i

∈I

Φ

i

=

∞

[

i

=1

Φ

i

oraz

\

i

∈I

Φ

i

=

∞

\

i

=1

Φ

i

.

1

Termin zbiór przeliczalny zostanie wyjaśniony precyzyjniej w rozdziale poświęconym teorii

mocy.

25

2.2 Działania uogólnione

2 ALGEBRA ZBIORÓW

Przykład 2.3

Dla rodziny indeksowanej {A

i

: i ∈ I} z Przykładu 2. mamy

[

i

∈I

A

i

=

∞

[

l

=0

[k, k + 1) = [0, ∞) ,

\

i

∈I

A

i

=

∞

\

k

=0

[k, k + 1) = ∅.

Studenci sprawdzą te równości samodzielnie.

Przykład 2.4

Uzasadnimy, że A =

S

∞
n

=1

[−n; 1 −

1

n

+1

] = (−∞; 1).

Najpierw wykażemy inkluzję A ⊂ (−∞, 1).

x

∈ A ⇔ ∃

n

∈N

x

∈ [−n; 1 −

1

n

+ 1

].

Ale dla każdego n,

h

−n, 1 −

1

n

+1

i

⊂ (−∞, 1) i stąd x ∈ (−∞, 1).

Wykażemy, że (−∞, 1) ⊂ A. Inaczej, uzasadnimy, że x ∈ (−∞, 1) ⇒ x ∈ A.

Przypuśćmy, że implikacja ta nie jest prawdziwa. Zatem istnieje x ∈ (−∞, 1) takie,

że x 6∈ A. Tak więc mamy

[x ∈ (−∞, 1)∧ ∼ (x ∈ A)] ⇔ [x ∈ (−∞, 1)∧ ∼ ∃

n

∈N

x

∈ [−n, 1 −

1

n

+ 1

]] ⇔

[x ∈ (−∞, 1) ∧ ∀

n

∈N

x

6∈ [−n, 1 −

1

n

+ 1

]].

Mamy zatem −∞ < x < 1 i dla dowolnego n, x < −n lub x > 1 −

1

n

+1

. Stąd

−∞ < x < 1 i jednocześnie x ¬ −∞ lub x ­ 1. W takim razie x ∈ ∅ wbrew temu,

że x ∈ (−∞, 1) 6= ∅.

2.2.3

Prawa działań uogólnionych

Oto zestawienie kilku częściej używanych praw dla działań uogólnionych:
Niech {A

i

: i ∈ I} będzie rodziną indeksowaną podzbiorów zbioru X. Wtedy:

Prawo

Nazwa

(

S

i

∈I

A

i

)

0

=

T

i

∈I

A

0

i

pr. de Morgana

(

T

i

∈I

A

i

)

0

=

S

i

∈I

A

0

i

pr. de Morgana

Wykażemy pierwsze prawo de Morgana dla rodziny indeksowanej podzbiorów zbioru
X

. Mamy

x

∈

[

t

∈T

A

t

!

0

⇔ x ∈ X \

[

t

∈T

A

t

⇔

(x ∈ X)∧ ∼

x

∈

[

t

∈T

A

t

!

⇔ (x ∈ X) ∧ (∼ ∃

t

∈T

x

∈ A

t

) ⇔

(x ∈ X) ∧ (∀

t

∈T

x

6∈ A

t

) ⇔ ∀

t

∈T

[(x ∈ X) ∧ (x 6∈ A

t

) ⇔

∀

t

∈T

(x ∈ X \ A

t

) ⇔ ∀

t

∈T

(x ∈ A

0
t

) ⇔ x ∈

\

t

∈T

A

0
t

.

26

2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

W dowodzie powyższym wykorzystaliśmy znane prawo rachunku kwantyfikatorów:

p

(x)

∧ ∀

t∈T

ϕ

(t)

⇔ ∀

t∈T

(p(x)

∧ ϕ(t)),

dla dow. funkcji zdaniowej zmiennej x i dowolnej funkcji zdaniowej ϕ(t) o zakresie t

∈ T .

Niech dana będzie rodzina indeksowana zbiorów A = {A

i

: i ∈ I}, gdzie I =

S

× T . Piszemy wtedy A = {A

s,t

: s ∈ S, t ∈ T } i mówimy, że rodzina A jest rodziną

zbiorów indeksowanych podwójnie. Wykażemy, że ma miejsce inkluzja:

[

s

∈S

\

t

∈T

A

st

!

⊂

\

t

∈T

[

s

∈S

A

st

!

,

przy czym znaku inkluzji nie można generalnie zastąpić znakiem równości.

Istotnie, mamy

x

∈

[

s

∈S

\

t

∈T

A

st

!

⇔ ∃

s

∈S

x

∈

\

t

∈T

A

st

⇔

∃

s

∈S

∀

t

∈T

x

∈ A

st

(∗)

⇒ ∀

t

∈T

∃

s

∈S

x

∈ A

st

⇔ x ∈

\

t

∈T

[

s

∈S

A

st

!

.

ad

(∗)

⇒: Wykorzystujemy tu prawo dla kwantyfikatorów: ∃

s

∈S

∀

t

∈ T ϕ(s, t) ⇒ ∀

t

∈T

∃

s

∈

Sϕ

(s, t).

Weźmy teraz rodzinę indeksowaną zbiorów: A

st

=

{s + t}, s, t ∈ R - podzbiorów zbioru

R

. Wtedy

S

s

∈S

(

T

t

∈T

A

st

) =

∅ oraz

T

t

∈T

(

S

s

∈S

A

st

) = R. Ponieważ

∅ 6= R, więc faktycznie

znaku „

⊂” nie można zastąpić znakiem „=” w powyższej inkluzji.

2.2.4

* Dalsze przykłady rodzin zbiorów

1. Pierścień zbiorów. Niepustą rodzinę

S zawartą w P(X) nazywamy pierścieniem zbiorów,

jeżeli

∀

A,B

∈S

(A

∪ B ∈ S) ∧ (A \ B ∈ S).

2. Algebra zbiorów. Algebra zbiorów jest to niepusta rodzina

A podzbiorów zbioru X taka,

że

∀

A,B

∈A

(A

∪ B ∈ A) ∧ (A

0

∈ A).

W teorii miary rozpatruje się często σ - pierścień

S (σ - algebrę), żądając by dodatkowo

∀rodziny przeliczalnej zbiorów

{A

s

∈S:s∈N }

[

s

∈N

A

s

∈ S

[

s

∈N

A

s

∈ A, odpowiednio

!

.

3. Topologia. Topologią w zbiorze X (patrz np. [2], [17] i [26]) naywamy podrodzinę

T

zbioru potęgowego

P(X) spełniającą warunki:

(

T

1

)

∅, X ∈ T ,

(

T

2

)

∀

A,B

∈P(X)

A, B

∈ T ⇒ A ∩ B ∈ T ,

(

T

3

)

∀

A⊂P(X)

A ⊂ T ⇒

[

A

∈A

A

∈ T .

Elementy rodziny

T nazywamy zbiorami otwartymi. Parę uporządkowaną (X, T ) nazywa-

my przestrzenią topologiczną.

27

2.3 Iloczyn kartezjański zbiorów

2 ALGEBRA ZBIORÓW

2.3

Iloczyn kartezjański zbiorów

2.3.1

Iloczyn kartezjański skończonej liczby zbiorów

Definicja 2.12 Parą uporządkowaną (a

1

, a

2

) nazywamy (wg K. Kuratowskiego,

1921) zbiór {{a

1

}, {a

1

, a

2

}}.

Lemat 2.2 Ma miejsce własność:

(a

1

, a

2

) = (b

1

, b

2

) ⇔ a

1

= b

1

∧ a

2

= b

2

.

Dw.

(Konieczność). Jeżeli a

1

= b

1

oraz a

2

= b

2

, to {a

1

} = {b

1

} i {a

2

} = {b

2

}. Stąd

{a

1

, a

2

} = {b

1

, b

2

}. Zatem (a

1

, a

2

) = (b

1

, b

2

).

(Dostateczność). Wykażemy, że jeżeli (a

1

, a

2

) = (b

1

, b

2

), to a

1

= b

1

oraz a

2

= b

2

.

Dowód przeprowadzimy nie wprost. Przypuśćmy, że a

1

6= b

1

. Wtedy muszą być

spełnione równości {a

1

} = {b

1

, b

2

} oraz {a

1

, a

2

} = {b

2

}. Jednakże oznacza, to że

b

1

= b

2

= a

1

oraz a

1

= a

2

= b

2

, skąd a

1

= a

2

= b

1

= b

2

= a i w szczególności

a

1

= b

1

, co przeczy naszemu założeniu.



Definicję pary uporządkowanej uogólniamy indukcyjnie:

Definicja 2.13 Ciągiem n - elementowym lub n - tką uporządkowaną nazywamy
ciąg elementów (a

1

, . . . , a

n

) taki, że dla każdego i ∈ {1, . . . , n},

(a

1

, . . . a

i

−1

, a

i

) = {(a

1

, . . . , a

i

−1

), {(a

1

, . . . , a

i

−1

), a

i

}}.

Lemat 2.3 Dla dowolnego n

∈ N ma miejsce własność:

(a

1

, . . . , a

n

) = (b

1

, . . . , b

n

) ⇔ ∀

i

∈{1,...,n}

a

i

= b

i

.

Dw.

(przez indukcję) pomijamy.

Definicja 2.14

(R. Kartezjusz, 1659). Iloczynem kartezjańskim zbiorów A i B

nazywamy zbiór wszystkich par uporządkowanych (a, b) takich, że a ∈ A, b ∈ B i

oznaczamy A × B. Zatem:

A

× B = {(a, b) : a ∈ A ∧ b ∈ B}.

Definicję tę uogólniamy łatwo na przypadek dowolnej skończonej liczby zbiorów:

A

1

× A

2

× . . . × A

n

df

= {(a

1

, a

2

, . . . , a

n

) : a

i

∈ A

i

, i

= 1, . . . , n}

Przykład 2.5

Przykłady skończonych iloczynów kartezjańskich:

a

) Potęga kartezjańska A

n

zbioru A:

A

n

= A × . . . × A = {(a

1

, . . . , a

n

) : a

i

∈ A

i

, i

= 1, . . . , n}.

Np. R

n

- iloczyn kartezjański n egzemplarzy zbioru liczb rzeczywistych R. Jest to

tzw. n - wymiarowa przestrzeń kartezjańska. Zatem

x

∈ R

n

⇔ x = (x

1

, . . . , x

n

) ∧ x

i

∈ R, i = 1, . . . , n.

b

) Kostka n - wymiarowa < 0, 1 >

n

.

c

) {0, 1}

n

- zbiór wszystkich ciągów n - wyrazowych złożonych z zer i jedynek.

28

2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

2.3.2

*Uogólniony produkt kartezjański zbiorów

Niech Φ : I → P(X) będzie rodziną indeksowaną podzbiorów zbioru X.

Definicja 2.15 Uogólnionym iloczynem kartezjańskim podzbiorów rodziny Φ nazyw-
my zbiór wszystkich funkcji

f

: I →

S

i

∈I

Φ

i

i

7→ f(i) ∈ Φ

i

i oznaczamy

Q

i

∈I

Φ

i

bądź w przypadku ciągu zbiorów A

1

, A

2

, . . .

oznaczamy

Q

∞
i

=1

A

i

.

Przykład 2.6

W X = R dana jest rodzina indeksowana zbiorów

A = {A

i

: i ∈ N}, gdzie A

i

= [−1/i, 1/i], i = 1, 2, . . ..

Mamy

S

i

∈I

A

i

=

S

∞
i

=1

[−1/i, 1/i] = [−1, 1]. Zatem uogólniony produkt

Q

i

∈I

A

i

=

Q

∞
i

=1

[−1/i, 1/i] jest tutaj zbiorem wszystkich ciągów (a

n

)

n

∈N

takich, że

a

i

∈ [−1/i, 1/i].

** Jeżeli rozpatrzymy powyższy produkt w topologii przestrzeni metrycznej R z me-
tryką naturalną (ze znaną nam zbieżnością ciągów rzeczywistych), to łatwo można
sprawdzić, że wszystkie owe ciągi - elementy produktu - są zbieżne do zera.
Istotnie, z oczywistej nierówności

∀

i∈N

0 <

|a

i

| ¬

1

i

i z twierdzenia o trzech ciągach,

lim

i→∞

a

i

= 0.

Przykład 2.7

W X = R dana jest rodzina indeksowana zbiorów

A = {A

s

: s ∈ R}, gdzie A

s

= (−e

−|s|

, e

−|s|

), s ∈ R. Ponieważ

S

s

∈R

A

s

= [−1, 1]\{0},

więc produkt

Q

s

∈R

A

s

jest tutaj zbiorem wszystkich funkcji rzeczywistych (niekoniecz-

nie ciągłych) f : R

→ R takich, że f(x) ∈ (e

−|x|

, e

|x|

), x ∈ R, jak na rysunku:

Rys.

**Uwaga.

Spróbujemy odpowiedzieć na pytanie: jak należy rozumieć iloczyn kartezjański dwóch

zbiorów A

×B zdefiniowany przy użyciu par uporządkowanych na gruncie definicji produktu uogól-

nionego?

Możemy przyjąć, że A i B są podzbiorami pewnego zbioru X (np. sumy tych zbio-
rów A

∪ B). Rodzinę indeksowaną (dwuelementową) zdefiniujmy jak następuje: Φ :

{1, 2} → A ∪ B, Φ

1

= A, Φ

2

= B. Wtedy iloczynem kartezjańskim (uogólnionym)

zbiorów A i B jest zbiór wszystkich odwzorowań f :

{1, 2} → A ∪ B takich, że

f

(1)

∈ A, f(2) ∈ B. Parę (f(1), f(2)) można identyfikować z parą uporządkowaną

(a, b), a

∈ A, b ∈ B.

29

2.4

Informacja o aksjomatach teorii mnogości

2 ALGEBRA ZBIORÓW

2.4

Informacja o aksjomatach teorii mnogości

Podny niżej układ aksjomatów pochodzi z monografii K. Kuratowskiego i A. Mostowskiego
[2]. W latach poprzednich omawialiśmy prostszy i bardziej zwięzły układ aksjomatów
podany w podręczniku H. Rasiowej. Jednak w tym roku zamierzamy naszkicować teorię
systemów relacyjnych i podać aksjomatyczne przedstawienie zbioru liczb naturalnych w
ujęciu Barneysa - Fraenkla a do tego celu bardziej nadaje sie układ aksjomatów teorii
mnogości przedstawiony niżej.

W systemie tym rozpatrywane będą rodziny zbiorów a więc zbiory, których elementami

są również zbiory.

W aksjomatycznej teorii mnogości przyjmuje się :
POJĘCIA PIERWOTNE: zbiór, przynależność elementu do zbioru.
AKSJOMATY:
I. AKSJOMAT RÓWNOŚCI ZBIORÓW

1

. Jeśli zbiory A i B mają te same ele-

menty to A = B.

II. AKSJOMAT ZBIORU PUSTEGO. Istnieje zbiór ∅ taki, że dla żadnego x nie

jest x

∈ ∅.

II’. AKSJOMAT PARY

2

. Dla dowolnych przedmiotów a, b istnieje zbiór, którego

jedynymi elementami są a i b.

III. AKSJOMAT SUMY. Dla każdej rodziny zbiorów A istnieje zbiór S złożony

z tych i tylko tych elementów, które należą do jakiegoś zbioru X należącego do

A.

IV. AKSJOMAT ZBIORU POTĘGOWEGO

3

. Dla każdego zbioru X istnieje ro-

dzina zbiorów

P(X), której elementami są wszystkie podzbiory zbioru X i tylko one.

V. AKSJOMAT NIESKOŃCZONOŚCI

4

. Istnieje rodzina zbiorów A o nastę-

pujących własnościach:

∅ ∈ A; jeśli X ∈ A, to w A istnieje element Y taki, że

elementami Y są wszystkie elementy X oraz sam zbiór X.

VI. AKSJOMAT WYBORU

5

. Dla każdej rodziny zbiorów niepustych i rozłącz-

nych istnieje zbiór, który z każdym ze zbiorów tej rodziny ma jeden i tylko jeden

1

Aksjomat ten zwany jest też Aksjomatem Jednoznaczności.

2

Aksjomat ten jest zależny od pozostałych - dowód [2], str. 67.

3

Łatwo jest wykazać, że rodzina

P(X) dla danego zbioru X jest tylko jedna!

4

Aksjomat ten nie figuruje w zestawie podanym przez H. Rasiową. Tutaj odegra znaczącą rolę

przy definiowaniu zbioru induktywnego przy wprowadzaniu zbioru liczb naturalnych.

5

Autorzy monografii [2] piszą o aksjomacie wyboru w taki oto sposób: Aksjomat wyboru nie

przez wszystkich matematyków jest przyjmowany bez zastrzeżeń; niektórzy traktują ten aksjomat z
dużą dozą nieufności i są zdania, że dowody przeprowadzone przy jego pomocy mają inną wartość
poznawczą, niż dowody niezależne od niego. Takie jest stanowisko w tej sprawie np. Borela i
Lebesque’a. Hausdorff i Fraenkel przyjmują pewnik wyboru bez zastrzeżeń, przypisując mu
ten sam stopień „oczywistości”, co pewnikom I-V.

W 1918 roku Wacław Sierpiński przeprowadził szczegółową analizę licznych dowodów opartych

na aksjomacie wyboru (por. [2], str 59). W popularnej książeczce [25] W. Sierpiński pisze: Co do
pewnika wyboru, to należy tu jeszcze uwzględnić okoliczności następujące:

1. Wiele wniosków z pewnika wyboru zostało udowodnionych bez odwoływania się do tego pewnika;
2. z pewnika wyboru wyprowadzono mnóstwo różnych wniosków, z których żaden nie doprowadził

do sprzeczności, a Kurt G¨

odel dowiódł, że pewnik wyboru nie jest sprzeczny z innymi powszechnie

przyjętymi pewnikami teorii mnogości (o ile te ostatnie są niesprzeczne);

3. pewnik wyboru jest przy dzisiejszym stanie nauki nieodzowny dla dowodu wielkiej liczby różnych

twierdzeń teorii mnogości i analizy i upraszcza znacznie wiele działów tych nauk.

30

2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

punkt wspólny.

V I

0

Φ

. AKSJOMAT O PODZBIORACH DLA FUNKCJI ZDANIOWEJ

6

Φ. Dla

dowolnego zbioru A i dla dowolnej funkcji zdaniowej Φ(a), a

∈ A istnieje zbiór X,

którego elementami są te i tylko te elementy A, które spełniaja funkcje zdaniową Φ.

V II

Φ

. AKSJOMAT ZASTĘPOWANIA

1

DLA FUNKCJI ZDANIOWEJ Φ. Jeśli

dla funkcji zdaniowej Φ(x, y), x

∈ X, y ∈ Y ma miejsce własność: dla każdego x

istnieje dokładnie jedno y takie, że Φ(x, y), to dla każdego zbioru A

⊂ X istnieje

zbiór B, którego elementami są te i tylko te elementy y, dla których - przy pewnym
x

∈ A - spełniony jest warunek Φ(x, y).

Uwaga 2.1

Łatwo wykazać, że:

a

) istnieje tylko jedna suma mnogościowa podzbiorów danej rodziny A,

b

) dla danego zbioru A istnieje dokładnie jeden zbiór potęgowy.

Układ aksjomatów teorii mnogości podał Zermelo. Układ (I) - (VII) zaproponowny w [16] jest
nieco ogólniejszy. Jest on niesprzeczny. Ale niektóre z aksjomatów są wnioskami z innych. Nie jest
to układ pełny, bo nie można opisać przy użyciu tych aksjomatów pewnych faktów teorio - mnogo-
ściowych (np. z teorii mocy). Wyjątkową pozycję w układzie aksjomatów ma aksjomat (VI). Jest
on (jak wykazał w 1963 roku P.J. Cohen) niezależny od pozostałych aksjomatów. Dowody twier-
dzeń, w których korzysta się z aksjomatu wyboru nazywa się niefektywnymi. Matematycy stosują
powszechnie w dowodach Aksjomat Wyboru zaznaczając na ogół, że w dowodzie interweniuje ten
aksjomat. Aksjomat wyboru ma liczne równoważne sformułowania. O jednym z nich, o Lemacie
Kuratowskiego - Zorna, wspomnimy jeszcze w tym wykładzie.

Zacytujmy uwagę z [2]: „Inne ujęcie aksjomatyki teorii mnogości zaproponował Neu-
mann...(1928)... . Idea von Neumanna polegała na wzbogaceniu teorii mnogości no-
wym pojęciem pierwotnym, które figuruje w aksjomacie zastępowania ... i pozwala
nie używać dowolnej funkcji zdaniowej Φ. Według nowszych koncepcji, pochodzących
od Bernaysa ... (1937) jako to nowe pojęcie pierwotne przyjmuje się pojęcie klasy:
treść intuicyjna tego pojęcia może być objaśniona jak następuje: X jest klasą, jeśli X
jest zespołem wszystkich przedmiotów spełniających jakąś funkcję zdaniową. Zespół
taki nie jest na ogół zbiorem”.

2

Uwaga 2.2

W związku z aksjomatem VI warto zdać sobie sprawę z tego, że niektó-

rych faktów udowodnionych przy pomocy tego pewnika nie jesteśmy w stanie potwierdzić
na żadnej innej drodze, np. konstruktywnie. W. Sierpiński wymienia w [25] zdumiewają-
ce twierdzenie udowodnione w 1914 roku przez świetnego matematyka polskiego Stefana
Mazurkiewicza (zmarł w młodym wieku ([3], str. 156-158) po upadku powstania w Warsza-
wie): Istnieje zbiór punktów na płaszczyźnie taki, że każda prosta, leżąca w tej płaszczyźnie,
przecina go dokładnie w dwóch punktach.

3

6

Aksjomat ten jest zależny od pozostałych (patrz [2], str 59, 67).

1

Aksjomat ten (patrz uwagi w [2]) wprowadzili niezależnie od siebie D. Mirimanoff (1917),

A. Fraenkel (1922) i T. Skolem (1922). W literaurze przyjeto nazywać ten aksjomat aksjomatem
Fraenkla.

2

Odnotujmy w tym miejscu (patrz uwaga w paragrafie 5.10 wykładu), że teoria klas została

wzmocniona najpierw przez K. G¨

odla a następnie przez Kelleya i Morse’a.

3

W 1924 roku Stefan Banach i Alfred Tarski dowiedli (patrz np. [25]), że „każde dwie

31

2.5 Zadania z algebry zbiorów

2 ALGEBRA ZBIORÓW

2.5

Zadania z algebry zbiorów

1. Podaj elementy następujących zbiorów:

a)

{α, β, γ};

b)

{α};

c)

{∅};

d)

{x ∈ N : x = −3};

e)

{x ∈ N : x ­ 0}

f)

{x ∈ R : |3 − x| < 3};

g)

{{a}, {∅}}.

2. Zbadaj jakie relacje inkluzji zachodzą między zbiorami A i B:

a) A =

∅, B = {α, β}.

b) A =

{x ∈ R : x > 0}, B = {x ∈ R : x ¬ 10}.

c) na płaszczyźnie : A - zbiór kwadratów, B - zbiór prostokątów. ([4])

3. ([4]). Zakładamy, że

{α, β, γ, δ} są różne od zbioru pustego. Jakie relacje zachodzą

między nimi, jeżeli ma miejsce równość:
a)

{α, β, γ} = {β, γ, δ}.

b)

{{α}, {α, β}} = {{γ}, {γ, δ}}.

4. Dowieść, że dla dowolnych zbiorów A, B, C zachodzą implikacje:

a) [(A

⊂ B) ∧ (C ⊂ D)] ⇒ [A ∩ C ⊂ B ∩ D].

b) (A

⊂ B) ⇒ [(C \ B) ⊂ (C \ A)].

5. (H.S.). Czy istnieją zbiory A, B, C takie, że A

∩ B 6= ∅, A ∩ C = ∅, (A ∪ B) \ C = ∅?

6. ([20]) W zaciętej bitwie 85 spośród 100 piratów straciło jedno oko, 80 jedno ucho,

75 jedną rękę, 70 jedną nogę. Jaka jest najmniejsza liczba piratów, którzy stracili
jednocześnie wszystkie te części ciała?

7. ([6]). Różnicę symetryczną zbiorów A i B określamy następująco:

A

÷ B = A ⊕ B = (A \ B) ∪ (B \ A). Wykaż, że

a

)A

⊕ A = ∅,

b

)A

⊕ B = B ⊕ A,

c

)A

⊕ B = A ∪ B \ A ∩ B,

d

)A

⊕ ∅ = A.

8. Wyznacz zbiory A

∪ B, A ∩ B, A − B, B − A oraz A ⊕ B dla następujących zbiorów

A

i B:

a) A =

{a, b, c, d}, B = {a, d};

b) A =

{{a, c}, b}, B = {b, c};

c) A =

{x ∈ N : x < 5}, B = {x ∈ N : x ­ 4};

d) A =

{x ∈ N : x ¬ 3

2
3

}, B = {x ∈ R : x ¬ 3

2
3

};

e) A =

{x ∈ R : ∃

u

∈R

u

2

+ xu + 1 < 0

}, B = {x ∈ R : ∃

w

∈R

w

2

+ w + x

¬ 0};

f) A =

{x ∈ R : ∀

u

∈R

u

2

+ xu

− 4 > 0}, B = {x ∈ R : ∀

w

∈R

w

2

+ w + x

­ 0};

g) A =

{x ∈ R : ∀

u

∈R

u

2

+ (x

− 2)u + 4 ¬ 0}, B = {x ∈ R : ∃

w

∈R

w

2

− 2w + x ¬ 0}.

9. Zapisz symbolicznie następujące zbiory:

(a) zbiór liczb naturalnych mniejszych od 2004;

(b) zbiór liczb naturalnych podzielnych przez 5;

(c) zbiór liczb postaci 3 + (

−2)

n

, gdzie n

∈ N;

ograniczone bryły, choćby miały różne objętości, są równoważne przez skończony rozkład”. Dalej
W. Sierpiński pisze: Banach i Tarski dowiedli, że dla koła nie zachodzi podobny paradoks jak dla kuli
(„Każda kula K jest sumą pięciu zbiorów rozłącznych, z których, po odpowiednich przesunięciach
i obrotach, otrzymujemy dwie kule rozłączne, gdzie każda z nich przystaje do kuli K”). Natomiast
nie wiemy, czy koło jest równoważne przez skończony rozkład kwadratowi o tej samej powierzchni.
W tym sensie zagadnienie kwadratury koła jest dotąd nie rozstrzygnięte (!).

32

2 ALGEBRA ZBIORÓW

Antoni Miczko, Wstęp do Matematyki

(d) zbiór liczb wymiernych z przedziału [

−1, 10).

10. Dana jest rodzina indeksowana (pojedynczo) zbiorów

A = {A

t

: t

∈ T }. Wykaż, że

a

)

∀

t

∈T

T

t

0

∈T

A

t

0

⊂ A

t

⊂

S

t

0

∈T

A

t

0

,

b

)

∃

A

∈A

∀

t

∈T

A

t

⊂ A ⇒

S

t

∈T

A

t

⊂ A,

c

)

∃

A

∈A

∀

t

∈T

A

⊂ A

t

⇒ A ⊂

T

t

∈T

A

t

.

11. Dane są dwie rodziny zbiorów (indeksowane tym samym zbiorem T ):

A = {A

t

: t

∈ T }, B = {B

t

: t

∈ T }. Dowieść, że

a

)

T

t

∈T

(A

t

∩ B

t

) = (

T

t

∈T

A

t

)

∩ (

T

t

∈T

B

t

) ,

b

)

S

t

∈T

(A

t

∪ B

t

) = (

S

t

∈T

A

t

)

∪ (

S

t

∈T

B

t

) ,

c

)

S

t

∈T

(A

t

∩ B

t

)

⊂ (

S

t

∈T

A

t

)

∩ (

S

t

∈T

B

t

) ,

d

) (

T

t

∈T

A

t

)

∪ (

T

t

∈T

B

t

)

⊂

T

t

∈T

(A

t

∪ B

t

).

12. ([4]). Znajdź sumę i iloczyn zbiorów dla t

∈ N oraz dla t ∈ R

+

\ {0}, gdzie R

+

Df

=

{t ∈ R : t > 0}, jeżeli A

t

⊂ R jest postaci:

a

) A

t

=

{x ∈ R :

√

t

¬ x ¬

√

2t

},

b

) A

t

=

{x ∈ R : cos x = t}.

c

) A

t

=

{x ∈ R : t

2

¬ x ¬ −t

2

+ 16

}, d) A

t

=

{x ∈ R : x = |t + 1|}.

13. ([4]). Oblicz sumę i iloczyn zbiorów dla t

∈ R:

a

) A

t

=

{(x, y) ∈ R

2

: x

2

+ y

2

¬ t

2

}, b) A

t

=

{(x, y) ∈ R

2

: x < t

· y}.

c

) A

t

=

{(x, y) ∈ R

2

: xy

¬ t

2

},

d

) A

t

=

{(x, y) ∈ R

2

: 4x

2

+ 9y

2

= 36

}.

14. Przedstaw na rysunku produkt zbiorów A i B (podzbiorów zbioru R), jeżeli:

a

) A =

∅, B = R,

b

) A = (0, +

∞), B = (1, +∞)

c

) A =

{1, 2, 3}, B = {3, 4}, d) A = {3, 5}, B = h1, 5).

15. Znalejdź

Q

t

∈T

A

t

jeżeli:

a) A

t

=

{1}, T = N;

b) A

t

=

{0, 1}, T = N;

c) A

t

=

h0, 1i, T = R

+

;

d) A

t

=

h−t, ti, T = R

+

;

e) A

t

=

{t

2

+ 2

}, T = R;

f) A

t

=

{2t − 1}, T = {1, 2, . . . , 2004}.

16. Uzasadnić, że

∀

X,Y

[X

6= ∅ 6= Y ∧ X × Y = Y × X ⇒ X = Y ].

33