Wykład drugi

Temat IV

Logika i matematyka

Wprowadzenie do teorii mnogości

Tworząc teorię mnogości G. Cantor - inaczej niż Euklides - nie podał żadnych aksjomatów czy postulatów, lecz sformułował definicje głównych jej pojęć: zbioru, liczby kardynalnej, równoliczności, zbioru uporządkowanego i typu porządkowego. W książce, która była systematyzacją i podsumowaniem uzyskanych wcześniejszych wyników, Cantor pisze:

Przez `zbiór' rozumiemy każde zebranie w jedną całość M określonych, dobrze odróżnionych przedmiotów m naszej naoczności albo naszego myślenia (które są nazywane `elementarni' [zbioru] M) Beiträge zur Begründung der transfiniten Mengelehre(1895-1897).

Intuicyjna teoria zbiorów

Zbudowana przez Georga Cantora w latach 1871-1883 teoria mnogości operuje dwoma pojęciami pierwotnymi: pojęciem zbioru oraz relacji bycia elementem (należenia). Zbiór dany jest enumeracją elementów lub ogółem obiektów, którym na wspólna własność._. W pierwszym przypadku nazwy elementów zapisuje się w nawiasie klamrowym, np.

{ a₁, a₂, ... , a_n}, dla n-elementowego zbioru, gdy n > 1 jest liczbą naturalną.

W drugim przypadku zbiór jest ogółem obiektów, które posiadają własność_. wy­rażoną funkcją zdaniową jednej zmiennej x,

(1) Z_φ={x: φ(x)}

Założenie, że dla dowolnej funkcji zdaniowej φ(x) istnieje zbiór Z postaci (1), tj. zbiór elementów spełniających tę funkcję nazywane jest aksjomatem abstrakcji.

G. Malinowski Logika ogólna, s. 166

------------------------------------

1. Terminologia i definicje

Zbiór jest złożony, składa się z pewnych przedmiotów

A, B, C … - zmienne przebiegające zbiory

x - nazwa (dowolnego) przedmiotu

W(x) - funkcja zdaniowa o zmiennej wolnej x

{x: W(x)} - operator abstrakcji; {x: } wiąże zmienną x

y∈{x: W(x)} - y jest elementem zbioru takich x, że zachodzi W(x)

Prawo eliminacji operatora abstrakcji

y∈{x: W(x)} ≡ W(y)

Relacje między elementami a zbiorami:

Należenie elementu do zbioru: x∈A - x jest elementem zbioru A, x należy do A

Nienależenie elementu do zbioru: x∉A - x nie jest elementem zbioru A, x nie należy do A. Zachodzi: x∉A ≡ ∼(x∈A) ≡ ∼x∈A

Działania na zbiorach, ich określenie

A ∪ B - suma zbiorów A i B; sumą zbiorów A i B jest zbiór tych i tylko elementów, które należą do zbioru A lub należą do zbioru B

A ∪ B = {x: x∈A ∨ x∈B}; x∈ A ∪ B ≡ x∈A ∨ x∈B

A ∩ B - iloczyn zbiorów A i B; iloczynem zbiorów A i B jest zbiór tych i tylko elementów, które należą do zbioru A i należą do zbioru B

A ∩ B = {x: x∈A ∧ x∈B}; x∈ A ∩ B ≡ x∈A ∧ x∈B

A − B - różnica zbiorów A i B; różnicą zbiorów A i B jest zbiór tych i tylko elementów zbioru A, które nie są elementami zbioru B

A − B = {x: x∈A ∧ x∉B}; x∈ A − B ≡ x∈ A ∧ x∉B

Różnica symetryczna dwóch zbiorów: A

(A

V - zbiór uniwersalny; zbiór pełny, zbiór wszystkich przedmiotów

V = {x: x = x}; x∈V ≡ x = x

∅ - zbiór pusty

∅ = {x: x ≠ x}; x∈∅ ≡ x ≠ x

Właściwości zbioru pustego:

∼∃x (x∈∅) ≡ ∼∃x (x ≠ x)

∀x (x∉∅) - żaden przedmiot nie jest elementem zbioru pustego

A' - dopełnienie zbioru A; dopełnieniem zbioru A jest zbiór tych i tylko przedmiotów, które nie są elementami zbioru A

A' = {x: x∉A}; x∈A' ≡ x∉A

Właściwości dopełnienia zbioru:

x∈A' ≡ x∈V ∧ x∉A ≡ x∈V − A

Relacje między zbiorami

Równość (identyczność) zbiorów: A = B

Zasada ekstensjonalności: A = B ≡ ∀x (x∈A ≡ x∈ B); zbiory identyczne składają się z tych samych elementów.

Różność (nierówność) zbiorów: A
B

Zbiory A i B są różne wtedy i tylko wtedy, gdy nie są równe (identyczne).

A ⊂ B - relacja inkluzji; zbiór A zawiera się w zbiorze B; zbiór A jest podzbiorem zbioru B; zbiór A jest częścią zbioru B.

Zbiór A zawiera się w zbiorze B wtedy i tylko wtedy, gdy każdy element zbioru A jest elementem zbioru B: A ⊂ B ≡ ∀x (x∈A → x∈B)

Właściwości zawierania się zbiorów: A ⊂ B ≡ ∼∃x (x∈A ∧ x∉B)

A
B - inkluzja właściwa; zbiór A jest podzbiorem właściwym zbioru B wtedy i tylko wtedy, gdy każdy element zbioru A jest elementem zbioru B, ale istnieje taki element zbioru B, który nie jest elementem zbioru A.

A
B ≡ A ⊂ B ∧ A
B

Rozłączność zbiorów A i B: A)(B

Zbiory A i B są rozłączne wtedy i tylko wtedy, gdy nie mają elementów wspólnych.

A)(B ≡ (A ∩ B =∅)

Krzyżowanie się zbiorów A i B: A



Zbiory A i B krzyżują się wtedy i tylko wtedy, gdy mają pewne elementy wspólne, ale ponadto, gdy każdy z nich ma elementy, które nie należą do drugiego z tych zbiorów.

A

B ≡ [(A ∩ B ≠ ∅ ∧ A−B ≠ ∅ ∧ B−A ≠ ∅]

2. Prawa teorii mnogości

1) (A')' = A

Dopełnienie dopełnienia zbioru A jest identyczne ze zbiorem A

Dowód:

a) x∈(A')' ≡ x∉A' - na podstawie definicji dopełnienia zbioru

b) x∉A' ≡ ∼x∈A' - na podstawie definicji nie należenia elementu do zbioru

c) ∼x∈A' ≡ ∼[∼(x∈A)] - na podstawie definicji dopełnienia zbioru

d) ∼[∼(x∈A)] ≡ x∈A - na podstawie prawa podwójnej negacji

e) x∈(A')' ≡ x∈A - na podstawie prawa przechodniości równoważności

2) A ⊂ B ≡ B' ⊂ A'

Zbiór A zawiera się w zbiorze B wtedy i tylko wtedy, gdy dopełnienie zbioru B zawiera się w dopełnieniu zbioru A.

Dowód na podstawie: definicji zawierania się zbiorów, prawa transpozycji prostej i definicji dopełnienia zbioru.

3) A = B ≡ A' = B'

Zbiory są identyczne wtedy i tylko wtedy, gdy ich dopełnienia są identyczne.

4) A = B' ≡ B = A'

Zbiór A jest dopełnieniem zbioru B wtedy i tylko wtedy, gdy zbiór B jest dopełnieniem zbioru A.

5) (A∪B)' ≡ A'∩ B' - prawo de Morgana dla sumy zbiorów

Dopełnienie sumy dwóch zbiorów jest równe iloczynowi dopełnień tych zbiorów.

6) (A ∩B)' ≡ A'∪ B' - prawo de Morgana dla iloczynu zbiorów

Dopełnienie iloczynu dwóch zbiorów jest równe sumie dopełnień tych zbiorów.

7) A∪A' ≡ V

8) A ⊂ V

Dowolny zbiór jest zawarty w zbiorze uniwersalnym.

9) A ∩ V = A

Iloczyn dowolnego zbioru A i zbioru uniwersalnego jest równy zbiorowi A.

Zbiór uniwersalny odgrywa w teorii mnogości przy mnożeniu zbiorów rolę analogiczną do liczby 1 przy mnożeniu liczb, gdzie a⋅ 1 = a.

10) ∅ ⊂ A

Zbiór pusty jest podzbiorem dowolnego zbioru.

11) A ∪ ∅ = A

Suma dowolnego zbioru A i zbioru pustego jest równa zbiorowi A.

Zbiór pusty odgrywa przy dodawaniu zbiorów rolę analogiczną do liczby 0 przy dodawaniu liczb, gdzie a + 0 = a.

12) V' = ∅

Dopełnieniem zbioru uniwersalnego jest zbiór pusty.

13) ∅'= V

Dopełnieniem zbioru pustego jest zbiór uniwersalny.

Inne prawa

A = A ∪ (A ∩ B)

A = (A ∩ B) ∪ (A ∩ B')

A = A ∩ (A ∪ B)

A ⊂ B ≡ A ∪ B = B ≡ A ∩ B = A

A ⊂ B ≡ A ∩ B' = ∅

A ⊂ B' ≡ A ∩ B = ∅

A ⊂ B' ≡ A ∪ B = V

A ∪ B = A ∪ (B −A)

A ∩ B = A − (A − B)

A − B = A − (A ∩ B)

A − B = A ∩ B'

A ∩ (A∪B) = A ∪(A ∩B) = A - prawo pochłaniania

A=B ≡ [(A∩ B') ∪(A' ∩ B) = ∅]

A=∅ ≡ [(A∩ B') ∪ (A' ∩ B) = B]

Rodzina zbiorów

A - zbiór

Definicja

Rodziną zbioru A jest zbiorem podzbiorów tego zbioru. Oznaczamy ją przez R(A)

R(A) = {X: X ⊂ A} X∈R(A) ≡ X ⊂ A

Rodziny zbiorów to zbiory zbiorów, tj. są to takie zbiory, których wszystkie elementy są zbiorami.

3. Iloczyn kartezjański zbiorów

A, B, C, D - zbiory

x ∈ A, y ∈ B, z ∈ C, u ∈ D

Definicja. Para uporządkowana <x, y> o pierwszym elemencie x i drugim elemencie y:

< x, y>
{{x}, {x, y}}

Właściwości par uporządkowanych:

1) (< x, y> = < z, u>) ≡ (x = z ∧ y = u)

Pary uporządkowane są identyczne wtedy i tylko wtedy, gdy ich pierwsze elementy są ze sobą identyczne i ich drugie elementy są ze sobą identyczne.

2) < y, x > ≠ < x, y >, zachodzi bowiem {{x}, {x, y}} ≠ {{y}, {y, x}}

3) (< x, y > ≠ < z, u >) ≡ (x ≠ z ∨ y ≠ u)

Dwie pary uporządkowane są różne wtedy i tylko wtedy, gdy ich pierwsze elementy są od siebie różne lub ich drugie elementy są od siebie różne.

- trójka uporządkowana: {< x, y, z >: x ∈ A, y ∈ B, z ∈ C}

- układ uporządkowany o n-elementach: {< x₁, x₂, … , x_n > : x_i ∈ X_i}

Definicja

A x B - iloczyn kartezjański zbiorów A i B to zbiór wszystkich par

uporządkowanych: <x, y>, gdzie x ∈ A, y ∈ B

A x B = {<x, y>: x∈A, y∈B}

Jeśli A = B, piszemy: A² = A x A, ogólnie: Aⁿ = A x A x … x A (n razy)

Przykłady

R - zbiór liczb rzeczywistych

R ² = R x R

R ³ = R x R x R,

1) R ² = R x R - płaszczyzna; {<x, y>: x, y ∈R}

2) R ³ = R x R x R - przestrzeń 3-wymiarowa: {< x, y, z >: x, y, z ∈R}

3) R ⁴ = R x R x R x R - przestrzeń euklidesowa 4-wym.: {<x, y, z, v >: x, y, z, v ∈ R}

Rys. Iloczyn kartezjański zbiorów A i B

Właściwości iloczynu kartezjańskiego zbiorów

1) (A ∪ B) x C = (A x C) ∪ (B x C)

2) (A − B) x C = (A x C) − (B x C)

3) (A ∩ B) x (C ∩ D)= (A ∩ C) x (B ∩ D)

Jeżeli C ⊂ A, D ⊂ B, to:

4) (C x D) = (C x B) ∩ (A x D)

5) (C x D)' = (C' x B) ∩ (A x D')

Zapis funkcji za pomocą iloczynu kartezjańskiego

X - dziedzina funkcji; Y - przeciwdziedzina funkcji

f - funkcja (matematyczna); f: X → Y, ∀y ∃x y = f (x)

Funkcja f jako podzbiór iloczynu kartezjańskiego dziedziny i przeciwdziedziny (X x Y):

f ⊂ X x Y, gdzie X x Y = {< x, f (x) >: x∈X ∧ f(x)∈Y}

< x, f (x) >∈ f ≡ y = f (x)

f = {<x, f (x)>}

4. Algebra Boole'a zbiorów

Terminologia

A, B, C, A' - zbiory

1 - V (zbiór uniwersalny)

0 - ∅ (zbiór pusty)

Algebrą Boole'a zbiorów jest aksjomatyczny system teorii mnogości, zbudowany w oparciu o następujące aksjomaty:

l) A
B

2) A
B

3) A
(B

4) A
(B

5) A
(B
)

6) A
(B

)

7) A
0

8) A
1

9) A
A'

10) A
A'

Na podstawie aksjomatów 1-10 można, stosując reguły dowodowe (pod­stawiania i zastępowania) udowodnić każde prawo teorii mnogości.

Na podstawie tych aksjomatów można też wprowadzić, za pomocą odpowiednich definicji dalsze działania nazw zbiorach oraz relacje między zbiorami, np.

A - B
A
B'

A )( B
A
B

1

---