Rachunek zdań:

Zdaniem w sensie logiki jest zdanie twierdzące, o którym można obiektywnie stwierdzić czy jest prawdziwe czy fałszywe.

Prawem logicznym (tautologią) nazywamy wyrażenia zbudowane za pomocą zdań, funktorów zdaniotwórczych i nawiasów, które jest zawsze prawdziwe dla dowolnych wartości logicznych zdań w nim występujących.

Podstawowe tautologie:

●Prawo tożsamości dla implikacji:
p=>p

●Prawa przemienności koniunkcji i alternatywy:
(p/\q)(q/\p)
(p\/q)(q\/p)

●Prawa łączności koniunkcji i alternatywy
(p/\q)/\rp/\(q/\r)
(p\/q)\/rp\/(q\/r)

●Prawa identpotentności
(p/\p)p
(p\/p)p

●Prawa pochłaniania
(p/\1)p
(p\/0)p

●Prawa rozdzielności
(p\/q)/\r(p/\r)\/(q/\r)
(p/\q)\/r(p\/r)/\(q\/r)

●Prawo wyłączonego środka
p\/(~p)

●Prawo wyłączonej sprzeczności
~(p/\(~p))

●Prawo podwójnego przeczenia
~(~p)p

●Prawa de Morgana
~(p/\q)(~p)\/(~q)
~(p\/q)(~p)/\(~q)

●Zaprzeczenie implikacji
~(p=>q)p/\(~q)

●Eliminacja implikacji
(p=>q)[(~p)\/q]

●Eliminacja równoważności
(pq)[(p=>q)/\(q=>p)]

●Przechodniość implikacji
[(p=>q)/\(q=>r)](p=>r)

●Prawo kontrapozycji
(p=>q)[(~p)=>(~q)]

●Reguła odrywania
((p=>q)/\p)=>p

Zbiory:

Zbiory oznaczamy dużymi literami. Element x należący do zbioru A oznaczamy x ∈ A. Element x nie należący do zbioru A oznaczamy x ∉ A. Elementy zbioru oznaczamy A = {a, b, c}. Zbiór który nie ma elementu nazywamy zbiorem pustym. Elementem zbioru może być inny zbiór, wtedy mówimy o rodzinie zbiorów.

Zasada ekstensjonalności:

Mówimy, że zbiory A i B są równe (identyczne) jeśli posiadają te same elementy i zapisujemyA = B lub B = A.

Def. 1. Mówimy, że zbiór A jest zawarty w zbiorze B, jeśli dla dowolnego x spełniony jest warunek:

x ∈ A = >x ∈ B

i oznaczamy A ⊂ B.

Tw.1. Zbiory są równe wtedy i tylko wtedy, gdy A zawiera się w B i B zawiera się w A:

$$A = B \Longleftrightarrow \left( A \subset B\hat{}B \subset A \right)$$

Tw.2. Jeśli A ⊂ B i B ⊂ C to A ⊂ C.

Działania na zbiorach:

A ∪ B = B ∪ AA ∩ B = B ∩ A

(A∪B) ∪ C ⇔ A ∪ (B ∪ C)(A∩B) ∩ C ⇔ A ∩ (B ∩ C)

(A∪B) ∩ C ⇔ (A∩C) ∪ (B∩C) ∖ n(A∩B) ∪ C ⇔ (A∪C) ∩ (B ∪ C)

(A∪B)^′ = A′∩B′(A∩B)^′ = A′∪B′

A ∩ A = AA ∪ A = A

●A ∩ A^′ = ⌀,  A ∪ A^′ = X

A ∪ ⌀ = AA ∩ X = A

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

Tw.3. Dla dowolnych zbiorów A,B,C mamy:

●A ⊂ B = >A ∪ C ⊂ B ∪ C

●A ⊂ B = >A ∩ C ⊂ B ∩ C

●A ⊂ B = >A − C ⊂ B − C

●$A \subset B\hat{}C \subset D = > A \cup C \subset B \cup D$

●A ⊂ B = >A′⊃B′

Def.2. Funkcją zdaniową zmiennej x nazywamy wyrażenie, które zawiera niewiadomą x i ma taką wartość, że jeśli w miejsce tej niewiadomej podstawimy konkretny przedmiot należący do ustalonego zbioru X to otrzymamy zdanie na gruncie logiki. Zbiór X nazywamy dziedziną lub zakresem zmienności.

Def.3. Iloczyn kartezjański: A × B = { < a, b > , a ∈ A,  b ∈ B}. Własności:

●(A∪B) × C ⇔ (A×C) ∪ (B×C)

●(A∩B) × C ⇔ (A×C) ∩ (B×C)

●<a₁, b₁ > = < a₂, b₂ >   ⇔ a₁ = a₂ ∧ b₁ = b₂

Kwantyfikatory

Def.4. Kwantyfikatory. Wyrażenie „dla każdego” nazywamy kwantyfikatorem ogólnym ∀. Wyrażenie „istnieje” nazywamy kwantyfikatorem egzystencjalnym ∃.

Tw.4. Jeśli φ(x) jest funkcją zdaniową o zakresie zmienności X to istnieje zbiór tych {x: φ(x)}, a więc zbiór elementów, które spełniają funkcję zdaniową. Dowód jest konsekwencją aksjomatów.

Tw.5. Typowe prawa kwantyfikatorów. Niech φ(x) jest funkcją zdaniową o zakresie zmienności X i niech x₀ ∈ X:

●∀_x ∈ Xφ(x) ⇒ φ(x)

●φ(x) ⇒ ∃_x ∈ Xφ(x)

●∀_x ∈ Xφ(x) ⇒ ∃_x ∈ Xφ(x)

Tw.6. Prawa de Morgana dla kwantyfikatorów:

●∼(∀_x ∈ Xφ(x)) ⇔ ∃_x ∈ X ∼ φ(x)

●∼(∃_x ∈ Xφ(x)) ⇔ ∀_x ∈ X ∼ φ(x)

Tw.7. Niech φ(x) będzie funkcją zdaniową o zakresie zmienności X. Wówczas:

●w(∀_x ∈ Xφ(x)) = 1 ⇔ {x∈X: φ(x)} = X

●w(∀_x ∈ Xφ(x)) = 0 ⇔ {x∈X: φ(x)} ≠ X

●w(∃_x ∈ Xφ(x)) = 1 ⇔ {x∈X: φ(x)} ≠ ⌀

●w(∃_x ∈ Xφ(x)) = 0 ⇔ {x∈X: φ(x)} = ⌀

Tw.8. Niech φ(x) i ψ(x) będą funkcjami zdaniowymi o zakresie zmienności X. Wówczas:

●∀_x ∈ X(φ(x)∧ψ(x)) ⇔ [∀_z ∈ X(φ(x))∧∀_x ∈ X(ψ(x))]

●∃(φ(x)∨ψ(x)) ⇔ [∃_z ∈ X(φ(x))∨∃_x ∈ X(ψ(x))]

●(∀_x ∈ Xφ(x)) ∨ (∀_x ∈ Xψ(x)) ⇒ ∀_x ∈ X(φ(x)∨ψ(x))

●∃_x ∈ X(φ(x)∧ψ(x)) ⇒ (∃_x ∈ Xφ(x)) ∧ (∃_x ∈ Xψ(x))

●∀_x ∈ X(φ(x)⇒ψ(x)) ⇒ (∀_x ∈ Xφ(x)⇒∀_x ∈ Xψ(x))

●∀_x ∈ X(φ(x)⇒ψ(x)) ⇒ (∃_x ∈ Xφ(x)⇒∃_x ∈ Xψ(x))

●∃_x ∈ Xφ(x) ∧ ∀_x ∈ Xψ(x) ⇒ ∃_x ∈ X(φ(x)∧ψ(x))

Tw.9. Niech φ(x) i ψ(x) będą funkcjami zdaniowymi o zakresie zmienności X. Wówczas mamy własności:

●{x∈X: φ(x)∧ψ(x)} = {x∈X:φ(x)} ∩ {x∈X:ψ(x)}

●{x∈X: φ(x)∨ψ(x)} = {x∈X:φ(x)} ∪ {x∈X:ψ(x)}

●{x∈X:∼φ(x)} = X − {x∈X:φ(x)}

Tw.10. Niech φ(x) będzie funkcją zdaniową o zakresie zmienności X oraz p niech będzie zdaniem, wówczas:

●∀_x ∈ X(φ(x)∧p) ⇔ (∀_x ∈ Xφ(x)) ∧ p

●∃_x ∈ X(φ(x)∧p) ⇔ (∃_x ∈ Xφ(x)) ∧ p

●∀_x ∈ X(φ(x)∨p) ⇔ (∀_x ∈ Xφ(x)) ∨ p

●∃_x ∈ X(φ(x)∨p) ⇔ (∃_x ∈ Xφ(x)) ∨ p

Kwantyfikatory o ograniczonym zakresie

Def.5. ∀_σ(x)φ(x) ⇔ ∀_x ∈ X(σ(x)⇒φ(x))

∃_σ(x)φ(x) ⇒ (∃_x ∈ Xσ(x)∧φ(x)).

Wszystkie prawa rachunku kwantyfikatorów sformułowane dotychczas pozostają prawdziwe dla kwantyfikatorów o ograniczonym zakresie.

Iloczyn kartezjański

Tw.11. Dla dowolnych elementów a i b istnieje dokładnie jeden zbiór, który zawiera wyłącznie elementy a i b. Zbiór ten oznaczamy {a, b} i nazywamy parą nieuporządkowaną.

Jeśli a = b to {a,b} = {a}

Dla dowolnych elementów a i b istnieje dokładnie jedne zbiór, który składa się z elementów {a} i {a, b}. Zbiór ten oznaczamy {{a},{a,b}} i nazywamy parą uporządkowaną. Stosujemy dla pary uporządkowanej oznaczenie <a, b>, gdzie a nazywamy poprzednikiem, zaś b następnikiem.

Tw.12. <a, b > = < c, d > ⇔a = c ∧ b = d.

Def.6. Niech A ≠ ⌀ i B ≠ ⌀. Wówczas zbiór C = {<a,b>, a∈A, b∈B } nazywamy iloczynem kartezjańskim zbiorów A i B i oznaczamy A × B. Jeśli któryś ze zbiorów A i B jest pusty to A × B = ⌀. Iloczyn kartezjański nie jest przemienny.

Tw.13. Dla dowolnych zbiorów A, B, C, D mamy:

●A × (B∩C) = (A×B) ∩ (A×C)

●A × (B∪C) = (A×B) ∪ (A×C)

●A × (B−C) = A × B − A × C

●A ⊂ B ∧ C ⊂ D ⇒ A × C ⊂ B × D

●Ponadto jeśli A ⊂ X i B ⊂ Y, to (X×Y) − (A×B) = (X−A) × Y ∪ X × (Y − B)

Relacje

Def.7. Niech X, Y ≠ ⌀. Wówczas dowolny zbiór 𝒫⊂X × Y nazywamy relacją dwuczłonową. Jeśli 𝒫⊂X₁ × X₂ × … × X_n to 𝒫 jest relacją n-członową.

<x, y > ∈𝒫 = x𝒫y

Niech 𝒫⊂X × Y. Dziedziną lewostronną (prawostronną) nazywamy zbiór:

D_L = {x∈X:∃_y ∈ Yx𝒫y},

(D_P={y∈Y:∃_x ∈ Xx𝒫y}).

Typy relacji

●Zwrotność ∀_x ∈ Xx𝒫x

●Symetryczność ∀_x ∈ X∀_y ∈ X(x𝒫y = y𝒫x)

●Przechodniość ∀_x ∈ X∀_y ∈ X∀_z ∈ X(x𝒫y ∧ y𝒫z ⇒ x𝒫z)

●Przeciwsymetryczność: ∀_x ∈ X∀_y ∈ X(x𝒫y⇒∼(y𝒫x))

●Słabosymetryczność: ∀_x ∈ X∀_y ∈ X((x𝒫y ∧ y𝒫x)⇒x = y)

●Spójność ∀_x ∈ X∀_y ∈ X(x𝒫y∨y𝒫x∨x=y)

●Przeciwzwrotność ∀_x ∈ X ∼ (x𝒫x)

Def.8. Relację 𝒫⊂X × X, która jest zwrotna, symetryczna i przechodnia nazywa się relacją równoważności.

Def.9. Niech 𝒫⊂X × Y będzie relacją równoważności to dla dowolnego x ∈ X to zbiór {y ∈ X : x𝒫y} nazywamy klasą abstrakcji wyznaczoną przez element x w relacji 𝒫 i oznaczamy:

[x]_𝒫 = {y ∈ X : x𝒫y}

Własności klas abstrakcji: Dla dowolnego x,  x₁,  x₂ ∈ X zachodzą własności:

●x ∈ [x]_𝒫

●[x₁]_𝒫 = [x₂]_𝒫 ⇔ x₁𝒫x₂

●[x₁]_𝒫 ≠ [x₂]_𝒫 ⇒ [x₁]_𝒫 ∩ [x₂]_𝒫 = ⌀

Def.10. Niech X ≠ ⌀. Niech 𝒜 będzie rodziną podzbiorów zbioru X. Mówimy, że rodzina 𝒜 stanowi podział przestrzeni X jeśli spełnione są następujące warunki:

●∀_{A ∈ 𝒜}A ≠ ⌀

●∀_{A1, A2∈𝒜}A₁ ≠ A₂ ⇒ A₁ ∩ A₂ = ⌀

●⋃𝒜 = X

Tw.14. (Zasada abstrakcji) Jeśli X ≠ ⌀ i 𝒫⊂X × X jest relacją równoważności to rodzina wszystkich klas abstrakcji stanowi podział przestrzenie X.

Tw.15. Aksjomat wyboru. Dla dowolnej rodziny 𝒜 zbiorów niepustych i parami rozłącznych istnieje zbiór, który posiada dokładnie po jednym elemencie wspólnym z każdym ze zbiorów rodziny 𝒜.

Tw.16. Niech 𝒜 będzie rodziną zbiorów niepustych w przestrzeni X parami rozłącznych i ⋃𝒜 = X, to istnieje relacja 𝒫⊂X × X, która jest relacją równoważności i klasy abstrakcji tej rodziny pokrywają się ze zbiorami rodziny 𝒜.

Składanie relacji

Niech 𝒫⊂X × Y i 𝒮⊂Y × Z. Wówczas relację:

{<x,z>∈X×Z:∃_y ∈ Y(x𝒫y∧y𝒮z)},

nazywamy superpozycją (złożeniem) relacji 𝒫 i 𝒮 i oznaczamy 𝒮 ∘ 𝒫.

Tw.17. Składanie relacji jest łączne, a więc, jeśli 𝒫⊂X × Y, 𝒮⊂Y × Z, 𝒯⊂Z × W, to 𝒯 ∘ (𝒮∘𝒫) = (𝒯∘𝒮) ∘ 𝒫⊂X × W.

Def.11. Niech 𝒫⊂X × Y. Wówczas {<y,x>∈Y×X:x𝒫y} nazywamy relacją odwrotną i oznaczamy 𝒫⁻¹. Zatem jeśli 𝒫⊂X × Y i 𝒫⁻¹ ⊂ Y × X, to

y𝒫⁻¹x ⇔ x𝒫y

Tw.18. Niech 𝒫⊂X × Y i 𝒮⊂Y × Z. Wówczas

(𝒮∘𝒫)⁻¹ = 𝒫⁻¹ ∘ 𝒮⁻¹ ⊂ Z × X

Def.12. Niech X ≠ ⌀ i niech 𝒫⊂X × Y. Mówimy, że 𝒫 jest relacją częściowego porządku, jeśli 𝒫 jest zwrotna, antysymetryczna (słabo symetryczna) i przechodnia.

Def.13. Niech X ≠ ⌀ i niech 𝒫⊂X × X. Mówimy, że 𝒫 jest relacją liniowego porządku, jeśli 𝒫 jest relacją częściowego porządku i jest spójna.

Def.14. Zbiorem częściowo uporządkowanym nazywamy parę <X, 𝒫>, gdzie ≤jest relacją częściowego porządku w X × X.

Def.15. Zbiorem liniowo uporządkowanym nazywamy parę <X, 𝒫>, gdzie ≤ jest relacją liniowego porządku w X × X.

Def.16. Jeśli zbiór X jest częściowo uporządkowana przez relację ≤ , zaś Y ⊂ X  jest liniowo uporządkowany przez relację ≤ to Y nazywamy łańcuchem.

Def.17 Niech <X, ≤> będzie zbiorem częściowo uporządkowanym. Wówczas element x₀ ∈ X jest elementem największym (najmniejszym) ze względu na relację ≤ jeśli jest spełniony warunek: ∀_x ∈ Xx ≤ x₀ (lub ∀_x ∈ Xx₀ ≤ x). Jeśli istnieje element największy (najmniejszy) to tylko jeden.

Def.18. Niech <X, ≤> będzie zbiorem częściowo uporządkowanym, mówimy że x₀ jest elementem maksymalnym (minimalnym) w zbiorze X, gdy nie istnieje x ∈ X takie, że x ≠ x₀ i x₀ ≤ x (lub x ≤ x₀ dla elementu minimalnego), a zatem:

∼(∃_x ∈ X(x≠x₀∧x₀≤x)) ⇔ ∀_x ∈ X(x=x₀∨∼(x₀≤x)).

Def.19. Niech <X, ≤> będzie zbiorem liniowo uporządkowanym. Jeśli dla każdego niepustego zbioru A ⊂ X istnieje element najmniejszy w zbiorze A względem relacji ≤ to taką relację nazywamy relacją dobrego porządku, a parę <X, ≤> zbiorem dobrze uporządkowanym.

Tw.19. (Fermallo) Dla każdego zbioru X ≠ ⌀ istnieje relacja ≤ w zbiorze X, która jest relacją dobrego porządku. Twierdzenie to jest równoważne aksjomatowi wyboru.

Funkcje

Def.20 Niech f ⊂ X × Y będzie relacją. Mówimy, że relacja f jest funkcją, jeśli spełniony jest następujący warunek:

∀_x ∈ X∀_y1 ∈ Y∀_y2 ∈ Y(xfy₁ ∧ xfy₂ ⇒ y₁ = y₂).

(relacja jest prawostronnie jednoznaczna)

D_L = {x∈X:∃_y ∈ Yxfy} – dziedzina lewostronna funkcji

Jeśli D_L = X to mówimy, że funkcja f jest określona na zbiorze X i oznaczamy: f : X → Y.

D_P = {y∈Y:∃_x ∈ Xxfy} - przeciwdziedzina (zbiór wartości) funkcji f, dziedzina prawostronna.

Jeśli D_P = Y to mówimy, że funkcja f jest typu „na” (jest określona na cały Y) i oznaczamy: f : XY.

Funkcja jest „na”, gdy: ∀_y ∈ Y∃_x ∈ Xy = f(x)

Def.21 Funkcja f : X → Y jest różnowartościowa, jeśli spełniony jest warunek:

∀_x1 ∈ X∀_x2 ∈ X(x₁≠x₂⇒f(x₁)≠f(x₂))

Z faktu, że (p⇒q) ⇔ ( ∼ q ⇒ ∼p), wynika:

∀_x1 ∈ X∀_x2 ∈ X(f(x₁)=f(x₂)⇒x₁=x₂)

Jeśli funkcja jest różnowartościowa i „na” to mówimy, że jest to funkcja wzajemnie jednoznaczna i oznaczamy: f : XY.

Jeśli f : X → Y jest różnowartościowa (lub „na”) i g : Y → Z jest różnowartościowa („na”) to g ∘ f też jest różnowartościowa („na”).

Jeśli f : X → Y jest wzajemnie jednoznaczna to f⁻¹ : X → Y też jest wzajemnie jednoznaczna.

Tw.20. Istnieje (na mocy aksjomatu) zbiór wszystkich funkcji określonych na zbiorze X o wartościach w zbiorze Y i oznaczamy go Y^X.

Tw.21. Jeśli f : X → Y jest funkcją, to relacja f⁻¹ jest funkcją wtedy i tylko wtedy, gdy funkcja f jest różnowartościowa. Ponadto f⁻¹ : Y₁ → X, gdzie Y₁ = D_P jest funkcją różnowartościową.

Tw.22. Niech f : X → Y i g : Y → Z będą funkcjami. Wówczas relacja g ∘ f jest funkcją (złożeniem funkcji) i g ∘ f : X → Z.

Def.22 Obrazem zbioru A ⊂ X przy pomocy funkcji f nazywamy zbiór

{y∈Y:∃_x ∈ Ay=f(x)}

_­­i oznaczamy f(A).

Def.23 Przeciwobrazem zbioru B ⊂ Y przy pomocy funkcji f nazywamy zbiór:

{x∈X:f(x)∈B}

i oznaczamy f⁻¹(B).

Działania uogólnione

Def.24 Niech 𝒜⊂2^X nazywamy rodziną indeksowaną, jeśli istnieje zbiór T ≠ ⌀ i istnieje funkcja f : T𝒜. Zatem

∀_{A ∈ 𝒜}∃_t ∈ TA = f(t) lub f(t) = A_t

Jeśli T jest zbiorem skończonym T = {1, 2, …, n}, to {A_t:t∈T} = {A₁,A₂,…,A_n}. Jeśli T = ℕ, to mamy ciąg zbiorów. Jeśli 𝒜 jest dowolną rodzina zbiorów, to:

●x ∈ ⋃𝒜⇔∃_{A ∈ 𝒜}x ∈ A

●x ∈ ⋂𝒜⇔∀_{A ∈ 𝒜}x ∈ A

Niech 𝒜 będzie rodziną indeksowaną postaci {A_t:t∈T}

●$x \in \bigcup_{t \in T}^{}A_{t} \Leftrightarrow \exists_{t \in T}x \in A_{t}$

●$x \in \bigcap_{t \in T}^{}{A_{t} \Leftrightarrow \forall_{t \in T}x \in A_{t}}$

Jeśli T = {1,2,…,n} to zapisy te można zastąpić odpowiednio:

$$\bigcup_{k = 1}^{n}A_{k}\mathrm{\text{\ i\ }}\bigcap_{k = 1}^{n}A_{k}$$

Tw.23. Niech {A_t:t∈T} i {B_t:t∈T} będą rodzinami indeksowanymi zbiorów. Wówczas:

●Dla dowolnego t₀ ∈ T: $\bigcap_{t \in T}^{}A_{t} \subset A_{t_{0}} \subset \bigcup_{t \in T}^{}A_{t}$

●Prawa de Morgana: $\left( \bigcup_{t \in T}^{}A_{t} \right)^{'} = \bigcap_{t \in T}^{}{\left( A_{t} \right)'}$ i $\left( \bigcap_{t \in T}^{}A_{t} \right)^{'} = \bigcup_{t \in T}^{}\left( A_{t} \right)^{'}$

●Jeśli dla dowolnego t ∈ T mamy, że A_t ⊂ B_t, to
$\bigcap_{t \in T}^{}A_{t} \subset \bigcap_{t \in T}^{}B_{t}$ i $\bigcup_{t \in T}^{}A_{t} \subset \bigcup_{t \in T}^{}B_{t}$

●Jeśli dla dowolnego t ∈ T mamy A ⊂ A_t ⊂ B, to $A \subset \bigcap_{t \in T}^{}A_{t}$ i $\bigcup_{t \in T}^{}{A_{t} \subset B}$.

Tw.24 Niech {A_t:t∈T} i {B_t:t∈T} będą rodzinami indeksowanymi. Wówczas:

●$\bigcup_{t \in T}^{}\left( A_{t} \cup B_{t} \right) = \bigcup_{t \in T}^{}A_{t} \cup \bigcup_{t \in T}^{}B_{t}$

●$\bigcap_{t \in T}^{}\left( A_{t} \cap B_{t} \right) = \bigcap_{t \in T}^{}{A_{t} \cap \bigcap_{t \in T}^{}B_{t}}$

●$\bigcup_{t \in T}^{}\left( A_{t} \cap B_{t} \right) \subset \bigcup_{t \in T}^{}A_{t} \cap \bigcup_{t \in T}^{}B_{t}$

●$\bigcap_{t \in T}^{}{A_{t} \cup \bigcap_{t \in T}^{}B_{t}} \subset \bigcap_{t \in T}^{}\left( A_{t} \cup B_{t} \right)$

●$\bigcup_{t \in T}^{}\left( A \cap B_{t} \right) = A \cap \left( \bigcup_{t \in T}^{}B_{t} \right)$

●$\bigcap_{t \in T}^{}\left( A \cup B_{t} \right) = A \cup \left( \bigcap_{t \in T}^{}B_{t} \right)$

Tw.25 Element x należący do granicy dolnej ciągu zbiorów {A_n}_n∈ℕ z wyjątkiem skończonej ilości. Element x należący do granicy górnej ciągu zbiorów {A_n}_n∈ℕ wtedy i tylko wtedy, gdy należy do nieskończenie wielu zbiorów {A_n}.

A_n ⊂ A_n.

Tw.26 Niech f : X → Y, {A_t:t∈T} ⊂ X, {B_t:t∈T} ⊂ Y. Wówczas:

●$f\left( \bigcup_{t \in T}^{}A_{t} \right) = \bigcup_{t \in T}^{}{f\left( A_{t} \right)}$

●$f\left( \bigcap_{t \in T}^{}A_{t} \right) = \bigcap_{t \in T}^{}{f\left( A_{t} \right)}$

●f(A) − f(B) ⊂ f(A−B)

Tw.27 Niech {B_t:t∈T} ⊂ Y, B₁, B₂ ⊂ Y, f : X → Y. Wtedy:

●$f^{- 1}\left( \bigcup_{t \in T}^{}B_{t} \right) = \bigcup_{t \in T}^{}{f^{- 1}\left( B_{t} \right)}$

●$f^{- 1}\left( \bigcap_{t \in T}^{}B_{t} \right) = \bigcap_{t \in T}^{}{f^{- 1}\left( B_{t} \right)}$

●f⁻¹(B₁∖B₂) = f⁻¹(B₁) ∖ f⁻¹(B₂)

Tw.28 Niech f : X → Y. Niech A ⊂ X i B ⊂ Y. Wówczas zachodzą następujące własności:

●f(f⁻¹(B)) ⊂ B

●A ⊂ f⁻¹(f(A))

Tw.29 Niech f : X → Y będzie funkcją typu „na”. Wówczas dla dowolnego zbioru B ⊂ Y mamy f(f⁻¹(B)) = B. Twierdzenie odwrotne jest także prawdziwe.

Tw.30 Niech f : X → Y będzie funkcją różnowartościową. Wówczas dla każdego dowolnego zbioru A ⊂ X mamy f⁻¹(f(A)) = A. Twierdzenie odwrotne jest także prawdziwe.

Równoliczność zbiorów

Def.25 Mówimy, że zbiory A, B ≠ ⌀ są równoliczne, jeśli istnieje taka funkcja f jest różnowartościowa, taka że f : AB i oznaczamy A ∼ B.

Tw.31 Dla dowolnych niepustych zbiorów A, B, C mamy:

●A ∼ A

●A ∼ B ⇔ B ∼ A

●A ∼ B ∧ B ∼ C ⇒ A ∼ C

Def.26 Zbiór A jest skończony, jeśli jest pusty lub istnieje liczba naturalna n∈ℕ, taka że A jest równoliczny ze zbiorem {1, 2, …, n}.

Tw.32 Zbiór liczb naturalnych nie jest zbiorem skończonym.

Lemat Dla każdej liczby naturalnej n∈ℕ nie istnieje funkcja różnowartościowa.

Def.27 Zbiór A nazywamy zbiorem przeliczalnym, jeśli A jest skończony lub równoliczny ze zbiorem liczb naturalnych lub istnieje f : ℕA.

Tw.33 Zbiór A jest przeliczalny wtedy i tylko wtedy, gdy jest zbiorem wartości pewnego ciągu nieskończonego, a więc istnieje funkcja f : ℕA.

Tw.34 Jeśli zbiór A jest przeliczalny i B ⊂ A, to B też jest przeliczalny.

Tw.35 Jeśli A,B są przeliczalne, to A ∪ B też jest przeliczalny.

Lemat Zbiory ℕ × ℕ oraz ℕ są równoliczne.

Tw.36 Jeśli A,B są przeliczalne, to A × B też jest przeliczalny.

Tw.37 Suma dowolnej rodziny {A_n:n∈ℕ}, gdzie A_n są przeliczalne, jest zbiorem przeliczalnym.

Def.28 Każdemu zbiorowi A przyporządkowujemy pewien obiekt, zwany mocą zbiorów, przy czym zbiory A i B mają tę samą moc wtedy i tylko wtedy, gdy A i B są równoliczne (A ∼ B). Oznacza się card A, $\overset{}{A}$, #A. Jeśli A jest skończony, czyli A ∼ {1,2,…,n} to card A = n. Przyjmuje się oznaczenie:

card ℕ = ℵ_o

Moce zbiorów nazywane są liczbami kardynalnymi.

Def.29 Mówimy, że liczba kardynalna 𝔪 (oznaczamy literami gotyckimi) jest nie większa od liczby kardynalnej 𝔫, co zapisujemy 𝔪 ≤ 𝔫, jeśli istnieją zbiory A i B, takie, że card A = 𝔪, card B = 𝔫 praz zbiór A jest równoliczny z pewnym podzbiorem zbioru B.

Def.30 Mówimy, że liczba kardynalna 𝔪 < n, jeśli 𝔪 ≤ 𝔫 i 𝔪 ≠ 𝔫.

Lemat (przekątniowy Cantora) Niech A będzie dowolnym zbiorem, zaś T ⊂ A dowolnym jego podzbiorem. Nie istnieje funkcja F : T → 2^A (lub teżF : T → P(2)), która jest typu „na”.

Def.31 Przyjmuje się oznaczenie card 2^ℕ = ℭ (continuum)

Tw.38 Dla dowolnego zbioru A mamy card A < card 2^A, nawet jeśli A = ⌀.

Hipoteza continuum (CH) Nie istnieje liczba kardynalna 𝔪 taka, że ℵ₀ < m < C. Hipoteza continuum jest niezależna od układu aksjomatów ZF (Zermello Frankla).

Tw.39 (Cantora – Bernsteina) Niech 𝔪, 𝔫 są dowolnymi liczbami kardynalnymi, wówczas:

𝔪 ≤ 𝔫 ∧ 𝔫 ≤ 𝔪 ⇒ 𝔪 = 𝔫

Tw.40 Zbiór [0, 1] jest nieprzeliczalny.

Tw.41 Dowodzi się, że jeśli card ℝ = ℭ to card (0,1) = ℭ, bo istnieje funkcja f(0,1)ℝ.

Tw.42 Nie istnieje zbiór wszystkich zbiorów.