3_logika.indd

1. Algebra zbiorów

Pojęcia

zbioru

relacji należenia

są w matematyce traktowane jako pojęcia pierwotne,

czyli  pozostawiane  bez  deﬁnicji. Gdyby przyjrzeć  się  bliżej  problemowi  deﬁnicji
zbioru, można zauważyć, że gdyby nawet udało się zdeﬁniować zbiór jako na przykład
„grupę  pewnych  elementów”,  zrodzi  się  wtedy  automatycznie  pytanie  o deﬁnicję
takiej  „grupy”.  Gdyby  i to  zdeﬁniować,  trzeba  byłoby  użyć  jakichś  innych  pojęć,
o deﬁnicję których znowu trzeba byłoby zadbać itp. Problem ten wiódłby oczywiście
do  podobnych  rozważań  i sporów  o deﬁniowanie w nieskończoność.  Ustalono
zatem, że dwa wyżej wspomniane pojęcia przyjmuje się za

pierwotne

. Pojęcia te są

odpowiednio charakteryzowane przez aksjomaty tzw.

teorii mnogości

(np.

Zermelo-

Fraenkla

W dalszych rozważaniach dużymi literami A, B oznaczać będziemy zbiory, małymi
zaś x, y — elementy zbiorów. Przez zapis x ∈ A rozumiemy zwyczajowo intuicję:
element x należy do zbioru

Przykład 1

Rozważmy następujące przykłady zbiorów:
 A = {a, b, 1, 0} — jak można łatwo zauważyć, zbiór ten ma cztery elementy. Są

to: a, b, 1, 0. Możemy zatem zapisać: a ∈ A, b ∈ A, 1

∈ A, 0

∈ A;

 B = {{a}, b, {1, 0}} — zbiór ten ma trzy elementy. Są to: {a}, b, {1, 0}. Mimo

że {a} sam w sobie jest zbiorem (jednoelementowym), to jest on elementem
rozważanego zbioru

B. Podobnie {1, 0} jest zbiorem dwuelementowym, ale

jako całość jest elementem zbioru B. Prawdą jest zatem, że {a} ∈ B, b ∈ B oraz
{1, 0} ∈ B. Ale nie jest prawdą, że a ∈ B (choć oczywiście a ∈ {a}). Mamy też
0

∉ B

(choć 0

∈ {1, 0});

 C = {{a, {b}}} — zbiór C ma tylko jeden element. Jest nim (dwuelementowy)

zbiór {a, {b}}. Mamy zatem {a, {b}} ∈ C. Ale nie jest prawdą, że a ∈ C czy też
nie jest prawdą, że b ∈ C;

 D = {a, {a, {b}}} — zbiór D ma dwa elementy. Są to: a oraz zbiór {a, {b}}.

Mamy oczywiście a ∈ D, ale też b ∉ D;

 N

= {0, 1, 2, 3, 4, ...}

— zbiór liczb naturalnych jest zbiorem nieskończonym;

 Z

= {... , –4, –3, –2, –1, 0, 1, 2, 3, 4, ...}

— zbiór liczb całkowitych (zbiór

nieskończony).

1.1. Działania algebry zbiorów

Jeżeli A oraz B są zbiorami, to:

 przez zapis A ∪ B rozumieć będziemy zbiór spełniający warunek
x ∈ A ∪ B ⇔ (x ∈ A ∨ x ∈ B) (element należy do zbioru A ∪ B wtedy

i tylko wtedy, gdy należy do jednego z nich lub do drugiego). Zbiór A ∪ B
nazywamy

sumą

zbiorów A oraz B. Interpretacja graﬁczna sumy zbiorów

przedstawiona jest na rysunku 1;

A B

Rysunek 1

 przez zapis A ∩ B rozumiemy zbiór spełniający warunek

x ∈ A ∩ B ⇔ (x ∈ A ∧ x ∈ B) (element należy do zbioru
A ∩ B wtedy i tylko wtedy, gdy należy do jednego z nich
i jednocześnie do drugiego). Zbiór A ∩ B nazywamy

iloczynem

lub

częścią wspólną

zbiorów A oraz B. Interpretacja graﬁczna

iloczynu zbiorów przedstawiona jest na rysunku 2;

 przez zapis A – B rozumiemy zbiór spełniający warunek

x ∈ A – B ⇔ (x ∈ A ∧ x ∉ B) (element należy do zbioru A
– B wtedy i tylko wtedy, gdy należy do pierwszego z nich i nie należy do
drugiego). Zbiór A – B nazywamy

różnicą

zbiorów A oraz B. Interpretacja

graﬁczna różnicy zbiorów przedstawiona jest na rysunku 3;

 przez zapis A ÷ B rozumiemy zbiór spełniający warunek

x ∈ A ÷ B ⇔ [(x ∈ A ∧ x ∉ B) ∨ (x ∈ B ∧ x ∉ A)]. Zbiór A ÷ B
nazywamy

różnicą symetryczną

zbiorów A oraz B. Interpretacja graﬁczna

różnicy symetrycznej zbiorów przedstawiona jest na rysunku 4;

 przez zapis A’ rozumiemy zbiór spełniający warunek

x ∈ A’ ⇔ x ∉ A ⇔ ¬x ∈ A (element należy do zbioru A’
wtedy i tylko wtedy, gdy nie należy do zbioru A). Zbiór
A’ nazywamy

dopełnieniem

zbioru A. Interpretacja graﬁczna

dopełnienia zbioru przedstawiona jest na rysunku 5.

1.2. Inkluzja (zawieranie) i równość zbiorów

Między zbiorami rozważa się dwie podstawowe zależności: zawierania
i równości zbiorów. Powiemy, że zbiór

A zawiera się w zbiorze B, co

zapisujemy A ⊆ B (rysunek 6), jeżeli każdy element zbioru A należy również
do zbioru B.

Formalnie możemy ten fakt zapisać następująco:

A ⊆ B ⇔ ∀

(x ∈ A ⇒ x ∈ B).

Powiemy, że zbiór A jest równy zbiorowi B wtedy i tylko wtedy, gdy zbiór
A zawiera się w zbiorze B oraz zbiór B zawiera się w zbiorze A (każdy element
zbioru A należy do zbioru B oraz każdy element zbioru B należy do zbioru A).

Formalnie:

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

Po odpowiednich przekształceniach możemy otrzymać:

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

(x ∈ A ⇒ x ∈ B) ∧ ∀

(x ∈ B ⇒ x ∈ A)] ⇔

⇔ ∀

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

∀

(x ∈ A ⇔ x ∈ B).

Finalnie mamy:

A = B ⇔ ∀

(x ∈ A ⇔ x ∈ B).

Dla zdeﬁniowanych wyżej działań i zależności między zbiorami możemy
udowodnić wiele własności zbiorów i działań na zbiorach.

Zgodnie z prawem rachunku kwantyfikatorów [

∀

A(x )

∧ ∀

B(x)]

⇔

∀

[A(x)

∧

B(x)].

Z prawa rachunku zdań [(α ⇒ β) ∧ (β ⇒ α)] ⇔ (α ⇔ β).

A B

A – B

A B

Rysunek 2

Rysunek 3

Rysunek 4

Rysunek 5

Rysunek 6

A B

A-B

Twierdzenie 1

Dla dowolnych zbiorów A, B, C zachodzą następujące własności:

(a)

A ∩ A = A — i d e m p o t e n t n o ś ć iloczynu,

(b)

A ∪ A = A — i d e m p o t e n t n o ś ć sumy,

(c)

A ∩ B = B ∩ A — p r z e m i e n n o ś ć iloczynu,

(d)

A ∪ B = B ∪ A — p r z e m i e n n o ś ć sumy,

(e)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) — r o z d z i e l n o ś ć i l o c z y n u w z g l ę d e m

s u m y,

(f)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) — r o z d z i e l n o ś ć s u m y w z g l ę d e m

i l o c z y n u ,

(g)

A ∩ (A ∪ B) = A — p o c h ł a n i a n i e ,

(h)

A ∪ (A ∩ B) = A — p o c h ł a n i a n i e ,

(i)

(A ∪ B)’ = A’ ∩ B’ — p r a w o d e M o r g a n a algebry zbiorów,

(j)

(A ∩ B)’ = A’ ∪ B’ — p r a w o d e M o r g a n a algebry zbiorów,

(k)

A ∩ B ⊆ A,

(l)

A ⊆ A ∪ B.

1.3. Metody dowodzenia własności zbiorów

Udowodnimy dla przykładu własność (a) z

twierdzenia 1

(idempotentności iloczynu

zbiorów):

A ∩ A = A.

Aby udowodnić tę własność, zgodnie z deﬁnicją równości zbiorów, należy pokazać, że:

∀

(x ∈ A ∩ A ⇔ x ∈ A),

czyli dla dowolnego elementu x należy wykazać prawdziwość równoważności
x ∈ A ∩ A ⇔ x ∈ A.

Weźmy zatem dowolny element x.

Rozpisując lewą stronę równoważności, otrzymujemy:

L : x ∈ A ∩ A ⇔ x ∈ A ∧ x ∈ A ⇔

x ∈ A : P

Następnie

—

wykorzystując

prawo

przechodniości

równoważności

[(α ⇔ β) ∧ (β ⇔ γ)] ⇒ (α ⇔ γ) — otrzymujemy ﬁnalnie:

x ∈ A ∩ A ⇔ x ∈ A.

Dowód (e)

Należy pokazać, że ∀

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

Weźmy dowolny element x. Mamy:

L : x ∈ A ∩ (B ∪ C) ⇔

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

x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⇔

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

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

(x ∈ (A ∩ C)) ⇔ x ∈ (A ∩ B) ∪ (A ∩ C) : P

Wykorzystujemy tu prawo idempotentności koniunkcji: α ∧ α ⇔ α.

Korzystamy z deﬁnicji iloczynu zbiorów: x ∈ A ∩ B ⇔ (x ∈ A ∧ x ∈ B).

Deﬁnicja sumy x ∈ A ∪ B ⇔ (x ∈ A ∨ x ∈ B).

Prawo rozdzielności koniunkcji względem alternatywy α ∧ (β ∨ γ) ⇔ (α ∧ β) ∨ (α ∧ γ).

I ponownie wykorzystując przechodniość równoważności, otrzymujemy:

x ∈ A ∩ (B ∪ C) ⇔ x ∈ (A ∩ B) ∪ (A ∩ C).

Dowód (g)

Należy pokazać, że ∀

[x ∈ A ∩ (A ∪ B) ⇔ x ∈ A].

Weźmy dowolny element x. Mamy:

L : x ∈ A ∩ (A ∪ B) ⇔ x ∈ A ∧ x ∈ (A ∪ B) ⇔ x ∈ A ∧ (x ∈ A ∨ x ∈ B) ⇔

x ∈ A : P

Korzystając z przechodniości równoważności, mamy:

x ∈ A ∩ (A ∪ B) ⇔ x ∈ A.

Dowód (i)

Należy pokazać, że ∀

[x ∈ (A ∪ B)’ ⇔ x ∈ A’ ∩ B’].

Weźmy dowolny element x. Mamy:

L : x ∈ (A ∪ B)’ ⇔

¬x ∈ (A ∪ B) ⇔ ¬(x ∈ A ∨ x ∈ B) ⇔

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

⇔ x ∈ A’ ∧ x ∈ B’ ⇔ x ∈ A’ ∩ B’ : P

I wreszcie:

x ∈ (A ∪ B)’ ⇔ x ∈ A’ ∩ B’.

1.4. Uniwersum i zbiór pusty

Łatwo dowodzi się faktu, że nie ma (uniwersalnego) zbioru wszystkich elementów.
Założenie takie dałoby natychmiastową sprzeczność, zakłada się bowiem, że żaden
zbiór nie może należeć do siebie samego. Dlatego jeżeli rozważamy jakieś zbiory,
bardzo często przydaje się pojęcie uniwersum — przestrzeni. Przestrzeń to, mówiąc
krótko,  świat  —  rzeczywistość,  którą  w danym  momencie  się  rozważa  (czyli  tak
naprawdę jakaś część całego świata — pełnej rzeczywistości). Jeżeli zastanawiamy
się  nad  własnościami  przedziałów  na  osi  rzeczywistej,  jako  uniwersum  możemy
przyjąć zbiór wszystkich liczb rzeczywistych. Jeżeli mówimy o własnościach zbiorów
punktów  na  płaszczyźnie  (w układzie  współrzędnych),  to  jako  uniwersum  można
przyjąć zbiór wszystkich punktów płaszczyzny. Uniwersum będzie tutaj oznaczane
jako X. Jeżeli rozważamy pewne zbiory nad pewnym uniwersum, możemy ograniczyć
pojęcie dopełnienia zbioru do dopełnienia względem uniwersum, tzn. przez zapis A’
rozumieć będziemy różnicę X – A. W dowodach własności związanych z uniwersum
X będziemy przyjmować, że wyrażenie x

∈

X jest prawdziwe.

Istotną rolę w teorii mnogości spełnia także

zbiór pusty

. Jest to zbiór, o którym

zakłada się, że nie ma żadnych elementów. Zakładamy również, że zbiór pusty jest
tylko jeden. Zbiór pusty oznaczamy zwyczajowo jako ∅.

Prawo pochłaniania α ∧ (β ∨ α) ⇔ α.

Deﬁnicja dopełnienia zbioru.

Prawo de Morgana rachunku zdań ¬(α ∨ β) ⇔ (¬α ∧ ¬β).

Twierdzenie 2

Rozważmy jako uniwersum zbiór X. Dla dowolnego zbioru A zawartego w zbiorze X
zachodzą następujące własności:
(a)  A ∩ X = A,
(b)  A ∪ X = X,
(c)  A ∪ A’ = X.

Dowód (a)

Należy pokazać, że ∀

[x ∈ A ∩ X ⇔ x ∈ A].

Weźmy dowolny element x. Mamy:

L : x ∈ A ∩ X ⇔ x ∈ A ∧ x ∈ X.

Zauważmy, że prawy czynnik powyższej koniunkcji jest prawdziwy. Przypomnĳmy
także, że jeżeli jeden z czynników koniunkcji jest prawdziwy, to cała koniunkcja
zależy tylko od drugiego z czynników i jest jemu równoważna. Uzasadniona jest
zatem następująca równoważność:

x ∈ A ∧ x ∈ X ⇔ x ∈ A : P,

I ﬁnalnie:

x ∈ A ∩ X ⇔ x ∈ A.

Dowód (c)

Należy pokazać, że ∀

[x ∈ A ∪ A’ ⇔ x ∈ X].

Weźmy dowolny element x. Mamy:

L : x ∈ A ∪ A’ ⇔ x ∈ A ∨ x ∈ A’ ⇔ x ∈ A ∨ ¬x ∈ A.

Zauważmy, że powyższa alternatywa jest prawdziwa

. Zatem uzasadniona jest

następująca równoważność:

x ∈ A ∨ ¬x ∈ A ⇔ x ∈ X : P.

I ﬁnalnie:

x ∈ A ∪ A’ ⇔ x ∈ X.

Twierdzenie 3

Dla dowolnego zbioru A zachodzą następujące własności:
(a)  ∅ ⊆ A,
(b)  A ∩ ∅ = ∅,
(c)  A ∪ ∅ = A,
(d)  A ∩ A’ = ∅.

Dowód (a)

Zgodnie z definicją inkluzji (zawierania) zbiorów należy pokazać, że

∀

[x ∈ ∅ ⇒ x ∈ A].

Jest to pewne podstawienie tautologii α ∨ ¬α.

Weźmy zatem dowolny element x. Jeżeli rozważymy poprzednik powyższej
implikacji, łatwo można zauważyć, że wyrażenie x ∈ ∅ jest fałszywe (do zbioru
pustego nie należy żaden element). Przypomnĳmy z rachunku zdań, że implikacja
o fałszywym poprzedniku jest prawdziwa niezależnie od następnika. Prawdziwe jest
zatem wyrażenie:

x ∈ ∅ ⇒ x

∈ A, co kończy dowód

Dowód (b)

Należy pokazać, że ∀

[x ∈ A ∩ ∅ ⇔ x ∈ ∅].

Weźmy dowolny element x. Mamy:

L : x ∈ A ∩ ∅ ⇔ x ∈ A ∧ x ∈ ∅.

Zauważmy, że prawy czynnik powyższej koniunkcji jest fałszywy. Przypomnĳmy także,
że jeżeli jeden z czynników koniunkcji jest fałszywy, to cała koniunkcja jest fałszywa.
Oczywiście, dwa dowolne fałszywe wyrażenia są sobie logicznie równoważne, zatem
uzasadniona jest następująca równoważność:

x ∈ A ∧ x ∈ ∅ ⇔ x ∈ ∅ : P,

I ﬁnalnie:

x ∈ A ∩ ∅ ⇔ x ∈ ∅.

Dowód (d)

Należy pokazać, że ∀

[x ∈ A ∩ A’ ⇔ x ∈ ∅].

Weźmy dowolny element x. Mamy:

L : x ∈ A ∩ A’ ⇔ x ∈ A ∧ x ∈ A’ ⇔ x ∈ A ∧ ¬x ∈ A.

Zauważmy, że powyższa koniunkcja jest fałszywa

. Zatem uzasadniona jest

następująca równoważność:

x ∈ A ∧ ¬x ∈ A ⇔ x ∈ ∅ : P.

I ﬁnalnie:

x ∈ A

∩ A’ ⇔ x ∈ ∅.

Opisywane wyżej własności dotyczą przede wszystkim działań na zbiorach. Poniżej
przedstawionych jest kilka własności zależności między zbiorami.

Twierdzenie 4

Dla dowolnych zbiorów A, B, C, D zachodzą następujące własności:
(a)  A ⊆ B ∧ B ⊆ C  ⇒ A ⊆ C,
(b)  A ⊆ B ∧ C ⊆ B  ⇒ A ∪ C ⊆ B,
(c)  A ⊆ B ∧ C ⊆ D  ⇒ A – D ⊆ B – C,
(d)  A ⊆ B ⇔ A ∪ B = B,
(e)  A ⊆ B ⇔ A ∩ B = A,
(f)  A ⊆ B ⇔ A – B = ∅,
(g)  A ⊆ B  ⇒ B

’

⊆ A

’

Zauważmy, że z tej własności wynika na mocy dowolności zbioru A własność ∅ ⊆ ∅.

Jest to pewne podstawienie kontrtautologii α ∧ ¬α.

(h) C ⊆ D ⇒ A – D ⊆ A – C,
(i) A ⊆ B ⇒ A ∪ (B – A) = B.

Dowód (a)

Załóżmy, że A ⊆ B oraz B ⊆ C. Z obu założeń otrzymujemy zgodnie z deﬁnicją
inkluzji zbiorów ∀

[x ∈ A ⇒ x ∈ B] oraz ∀

[x ∈ B ⇒ x ∈ C]. Aby udowodnić tezę

A ⊆ C, należy pokazać, że ∀

[x ∈ A ⇒ x ∈ C].

Weźmy więc dowolny element x i załóżmy, że x ∈ A. Na mocy założeń mamy kolejno
x

∈ B oraz x ∈ C, co kończy dowód.

Dowód (b)

Załóżmy, że A ⊆ B oraz C

⊆

B. Otrzymujemy ∀

[x ∈ A ⇒ x ∈ B] oraz

∀

[x ∈ C ⇒ x ∈ B]. Aby udowodnić tezę A ∪ C ⊆ B, należy pokazać, że

∀

[x ∈ A ∪ C ⇒ x ∈ B].

Weźmy więc dowolny element x i załóżmy, że x ∈ A ∪ C. Mamy:

x ∈ A ∨ x ∈ C.

Stosując kolejno oba założenia, otrzymujemy:

x ∈ B ∨ x ∈ B,

czyli:

x ∈ B,

co kończy dowód.

Dowód (d)

Aby pokazać, że A ⊆ B ⇔ A ∪ B = B, musimy udowodnić dwie implikacje:
(*)

A ⊆ B ⇒ A ∪ B = B oraz

(**) A ∪ B = B

⇒ A ⊆ B.

(*)

Załóżmy, że A ⊆ B,

czyli ∀

[x ∈ A ⇒ x ∈ B]. Aby udowodnić równość zbiorów

A ∪ B = B, wykażemy dwie inkluzje: A ∪ B ⊆ B oraz B

⊆ A ∪ B. Druga z nich jest

oczywista na podstawie jednej z własności z

twierdzenia 1

Aby udowodnić pierwszą inkluzję, załóżmy, że

x ∈ A ∪ B.

Mamy:

x ∈ A ∨ x ∈ B.

Teraz, korzystając z założenia dowodu (*), mamy:

x ∈ B ∨ x ∈ B

i oczywiście x ∈ B,

co kończy dowód pierwszej z inkluzji potrzebnych do

udowodnienia implikacji (*).

(**)

Załóżmy, że A ∪ B = B,

czyli ∀

[x ∈ A ∪ B ⇔ x ∈ B]. Aby udowodnić inkluzję

A ⊆ B, załóżmy, że x ∈ A.

Cytowana własność jest postaci A

⊆

∪

B, ale oczywiście — zważywszy na przemienność

sumy zbiorów — oznacza to samo.

Wiemy, że w ogólnym przypadku A ⊆ A ∪ B, czyli ∀

[x ∈ A ⇒ x ∈ A ∪ B].

Otrzymujemy zatem:

x ∈ A ∨ x ∈ B.

Teraz, korzystając z założenia dowodu (**), mamy:

x ∈ B,

co kończy dowód implikacji (**).

Oczywiście zważywszy na odpowiednie prawo rachunku zdań

, równoważność

A ⊆ B ⇔ A ∪ B = B została udowodniona.

Dowód (h)

Załóżmy, że A ⊆ B,

czyli ∀

[x ∈ A ⇒ x ∈ B]. Rozważmy dowolny element x.

Przypomnĳmy, że — zgodnie z odpowiednim prawem rachunku zdań — implikacja
x ∈ A ⇒ x ∈ B jest równoważna implikacji ¬x ∈ B ⇒ ¬x ∈ A, która inaczej zapisana
przybiera postać: x ∈ B

‘

⇒ x ∈ A

‘

. Mamy zatem:

∀

[x ∈ B

‘

⇒ x ∈ A

‘

czyli:

‘

⊆ A

‘

Prawo [(α ⇒ β) ∧ (β ⇒ α)] ⇔ (α ⇔ β).

2. Zbiór potęgowy

i inne rodziny zbiorów

Czasem — z pewnych powodów — istnieje potrzeba rozpatrywania zbiorów, których
elementami są również zbiory. Zbiory zbiorów nazywamy rodzinami. Typowym
przykładem rodziny zbiorów jest zbiór potęgowy danego zbioru.

Zbiorem potęgowym zbioru X nazywamy zbiór P(X) wszystkich podzbiorów tego
zbioru, symbolicznie:

P(X) = {A: A ⊆ X}.

Możemy też zapisać:

A ∈ P(X) ⇔ A ⊆ X.

Dla dowolnego zbioru X jego zbiór potęgowy P(X) nie jest zbiorem pustym, bo

∅ ∈ P(X) oraz X ∈ P(X).

Przykład 1

Jeśli X

= ∅, to P(X

) = {∅}. Nie ma bowiem innego podzbioru zbioru pustego poza

nim samym.

Przykład 2

Niech X

= {a, b, c}, wtedy P(X

)={∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Przykład 3

Niech X

= {{a}, {{b}, c}}. Zauważmy, że zbiór ma tylko dwa elementy.

Są to {a} oraz {{b}, c}. Zbiór potęgowy wygląda zatem następująco:
P(X

) = {∅, {{a}}, {{{b}, c}}, {{a}, {{b}, c}}}.

Twierdzenie 5

Dla dowolnych zbiorów A i B zachodzą poniższe własności:

(a) A, B ∈ P(X) ⇒ A ∩ B, A ∪ B, A – B ∈ P(X),

(b) X ⊆ Y ⇒ P(X) ⊆ P(Y).

Dowód (a)

Niech A, B ∈ P(X), wtedy A ⊆ X oraz B ⊆ X, ale oczywiście również zbiory A ∩ B,
A ∪ B, A – B są podzbiorami zbioru X, więc A ∩ B, A ∪ B, A – B ∈ P(X).

Dowód (b)

Załóżmy, że X ⊆ Y. Mamy pokazać, iż P(X) ⊆ P(Y).

Weźmy zatem dowolny element A zbioru potęgowego P(X). Mamy:

A ∈ P(X) ⇔

A ⊆ X ⇒

A ⊆ Y ⇔

A ∈ P(Y).

Ostatecznie, korzystając z praw przechodniości równoważności i implikacji, mamy:

∈ P(X) ⇒ A ∈ P(Y).

Przykład 4

Rozważmy zbiór X

= {a, b, c, d}. Zauważmy, że mamy wtedy X

= X

∪ {d}.

Można zauważyć, że elementami zbioru potęgowego P(X

) będą wszystkie elementy

zbioru potęgowego P(X

) oraz wszystkie sumy elementów zbioru P(X

) ze zbiorem

jednoelementowym {d}. Symbolicznie mamy w naszym przypadku:

P(X

) = P(X

) ∪ {A

∪ {d} : A ∈ P(X

)}.

W rozważanym przypadku mamy:

P(X

) = P(X

) ∪ {A

∪ {d} : A ∈ P(X

)} =

= {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} ∪

∪ {∅ ∪ {d}, {a} ∪ {d}, {b} ∪ {d}, {c} ∪ {d}, {a, b} ∪

{d}, {a, c} ∪ {d}, {b, c} ∪ {d}, {a, b, c} ∪ {d}} =

= {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} ∪

∪ {{d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}} =

= {∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d},

{c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}.

Twierdzenie 6

Jeżeli zbiór A ma n elementów, to jego zbiór potęgowy P(A) ma 2

elementów.

Dowód

Dowód przeprowadzony zostanie przez indukcję ze względu na ilość elementów
zbioru A.

B a z a i n d u k c j i — rozważmy zbiór niemający elementów (n = 0). Jedynym takim
zbiorem jest oczywiście zbiór pusty ∅. Zauważmy również, że P(∅) = {∅}. Zatem
w tym przypadku zbiór potęgowy faktycznie ma 2

= 1 elementów.

Z a ł o ż e n i e k r o k u i n d u k c y j n e g o — załóżmy, że zbiór potęgowy zbioru
mającego k elementów ma 2

elementów.

K r o k i n d u k c y j n y — rozważmy zbiór k + 1-elementowy. Możemy zapisać ten
zbiór następująco:

, a

, ..., a

, a

k+1

} (zbiór ten oznaczamy dalej jako A

k+1

Z deﬁnicji zbioru potęgowego.

Z założenia, że X

⊆

Z deﬁnicji zbioru potęgowego.

Zauważmy, że zbiór ten można potraktować również jako poniższą sumę:

, a

, ..., a

} ∪ {a

k+1

} (inaczej możemy zapisać A

∪ {a

k+1

}).

Oczywiście, zbiór A

= {a

, a

, ..., a

} jest zbiorem k-elementowym, a zatem jego

zbiór potęgowy P(A

) ma zgodnie z założeniem indukcyjnym 2

elementów. Łatwo

można zauważyć (patrz

przykład 5

), że zbiór potęgowy P(A

k+1

) można przedstawić

następująco: P(A

k+1

) = P(A

) ∪ {X ∪ {a

k+1

} : X ∈ P(A

)}. Zbiory P(A

) oraz {X ∪

k+1

} : X ∈ P(A

)} są rozłączne oraz każdy z nich ma 2

elementów. Zatem zbiór

P(A

k+1

) ma 2

+ 2

= 2 ⋅ 2

= 2

k+1

elementów, co kończy dowód.

Innym dobrym przykładem rodziny zbiorów jest

ciało zbiorów

. Rozważmy zbiór X

oraz jego zbiór potęgowy P(X).

Rodzinę  ℑ  podzbiorów  zbioru  X  nazwiemy  ciałem  zbiorów,  jeżeli  spełnione  są
następujące warunki:
1.  ℑ ≠ ∅.
2.  Jeżeli A ∈ ℑ, to X – A ∈ ℑ (dopełnienia zbiorów należących do ℑ należą również

do ℑ).

3. Jeżeli A ∈ ℑ oraz B ∈ ℑ, to A ∪ B ∈ ℑ (sumy zbiorów należących do ℑ należą

również do ℑ).

Przykład 5

Rozważmy następujący zbiór X = {a, b, c} oraz rodzinę ℑ

= {{a}, {b}}.

Zauważmy, że X

– {a} = {b, c} ∉ ℑ

, a także X

– {b} = {a, c} ∉ ℑ

. Każde z tych

spostrzeżeń wystarcza, aby orzec, że ℑ

nie jest ciałem zbiorów. Warunek sumy

również nie jest spełniony, bowiem {a} ∪ {b} = {a, b} ∉ ℑ

Przykład 6

Wzbogaćmy zatem rozważaną wyżej rodzinę ℑ

o wskazane wyżej zbiory.

Niech ℑ

= {{a}, {b}, {b, c}, {a, c}, {a, b}}.

Zauważmy następujące fakty: {a} ∪ {b, c} =

{a, b, c} = X ∉ ℑ

oraz

– {a, b} = {c} ∉ ℑ

. Jeżeli wzbogacimy rodzinę ℑ

o powyższe zbiory, to rodzina

ta jeszcze nie spełnia aksjomatów ciała zbiorów, gdyż X

–

= ∅ ∉ ℑ

. Okazuje się, że

dopiero pełny zbiór potęgowy P(X) jest ciałem zbiorów zawierającym rodzinę ℑ

Przykład 7

Nie tylko zbiory potęgowe są ciałami zbiorów. Jeżeli rozważymy zbiór
X = {a, b, c, d} oraz rodzinę ℑ

= {∅, {a, c}, {b, d}, X}, to łatwo zauważyć, że

spełnia ona aksjomaty ciała zbiorów.

Zachodzą następujące własności ciał zbiorów:

Twierdzenie 7

Dla dowolnego zbioru X

i dowolnego ciała zbiorów ℑ takiego, że ℑ ⊆

P(X) jest:

(a) jeżeli A ∈ ℑ oraz B ∈ ℑ, to A ∩ B ∈ ℑ (iloczyny zbiorów należących do ℑ należą

również do ℑ),

Bibliograﬁa

Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki
Częstochowskiej.

Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN, Warszawa.

Kuratowski K., Mostowski A., 1978: Teoria mnogości, PWN, Warszawa.

Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości w zadaniach,
PWN, Warszawa.

Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN, Warszawa.

Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria mnogości,
Warszawa.

Bibliograﬁa stron WWW

7. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Witryna internetowa. h�p://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan

z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).