Zoran Skoda mat1-171120-2

Nastavljamo diskusiju o kardinalnim brojevima (kardinalima) započetu u predavanju mat1-171120-1. U literaturu spadaju wiki stranice kardinalni broj, prirodni broj te prvih nekoliko stranica iz knjige Veljana i Pavkovića Elementarna matematika I gdje, u dijelu o skupovima, možete naći i diskusiju beskonačnih kardinala, Cantorovog teorema i Cantor-Schroeder-Bernsteinovog teorema.

Neformalno, reći da dva skupa imaju isti broj elemenata je isto kao i reći da imaju jednaki kardinalni broj.

No sad promatramo novo pitanje: kada skup A ima manje elemenata od skupa B ?

Ako je A podskup od B, onda nam intuitivna verzija pojma kaže da on ne može imati više elemenata, može imati ili isto ili manje.

Hoćemo definirati kad je $kard(A)\leq kard(B)$

1) ako $A \subset B$

2) Općenitije, ako postoji injekcija iz A u B (tj. bijekcija između A i nekog podskupa od B, naime slike po toj injekciji), sve elemente iz A utrpamo u B, a da ni jedna dva ne spojimo zajedno)

$f:A\to B$, $Im(f) = f(A) = \{ f(x)| x\in A\}$ (to je podskup od B) f| korestrikcija na sliku je funkcija iz A na sliku f(A) i to je bijekcija na tu sliku.

Cantor-Schroeder-Bernsteinov teorem: pretpostavimo da vrijedi aksiom izbora. Za dva skupa A i B, ako postoji injekcija iz A u B i injekcija iz B u A tada postoji i bijekcija između A i B.

Idemo protumačiti posljedice za kardinalne brojeve. Ako pretpostavimo da vrijedi aksiom izbora za skupove onda je $\leq$ definiran preko injekcija relacija uređaja na klasi kardinalnih brojeva, odnosno, ta jerelacija tranzitivna, refleksivna i antisimetrična! Ovaj dio s antisimetrijom je problem koji je riješen teoremom.

Dakle
A stavimo injekcijom u B (to znači $kard(A)\leq kard(B)$), B stavimo injekcijom u A (to znači $kard(B)\leq kard(A)$), možemo li zaključiti da li je $kard(A) = kard(B)$ tj. postoji bijekcija s A na B. To je Cantor-Schroeder-Bernstein!

Tranzitivnost slijedi i bez aksioma izbora ako A uguramo u B injekcijom B uguramo u C onda i A možemo ugurati u C, naime kompozicijom funkcija.

Znači možemo poredati skupove po kardinalnosti (veličina).

Unija skupova, ako je disjunktna, njenu kardinalnost zovemo suma kardinalnih brojeva.

2+3 = 5 u smislu da {a,b,c} unija s {1,2} dobijemo {a,b,c,1,2}

Unija $I = \{a,b,c\}$ sa skupom $J = \{a,b\}$ je $\{a,b,c\}$ (samo 3 elementa, ne 2+3=5) ali disjunktna unija je $\{a_I, b_I, c_I, a_J, b_J\}$, gdje se razlikuje iz kojeg je skupa došao koji element, pa se a i b pojavljuju dva puta, i tu ima ukupno 2+3 = 5 elemenata.

To je zbrajanje kardinalnih brojeva. Neka je $\aleph_0 = kard(\mathbf{N})$ (čitamo alef nula, alef je slovo hebrejskog alfabeta) kardinalnost ma kojeg prebrojivo beskonačnog skupa (svi imaju jednaku kardinalnost), tada

$$\aleph_0 + \aleph_0 = \aleph_0$$

$$\aleph_0 + 8 = \aleph_0$$

MNOŽENJE kardinalnih brojeva

kard(A) x kard(B) := kard(A x B)

Neka je $A = \{1,2\}$ i $B = \{a,b,c\}$. Tada je njihov Kartezijev umnožak,

$$A x B = \{ (a, b) | a\in A, b\in B \} = \{(1,a), (1,b), (1,c), (2,a), (2,b),(2,c)\}$$

Partitivni skup $\mathcal{P}(X)$ skupa $X$ je po definiciji skup svih podskupova od X i ima $2^{kard(X)}$ elemenata.

Ajde da to najprije vidimo na primjeru, a onda što to znači općenito.

Neka je $X = \{1,2,3\}$. Tada je

$$\mathcal{P}(X) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\},\{1,2,3\}\},$$

dakle $kard(\mathcal{P}(X)) = 2^3 = 2 x 2 x 2 = 8$.

To je zato jer karakterističnih funkcija za podskupe skupa od 3 elementa ima 2 puta 2 puta 2. Ajde da to objasnimo.

Svaki podskup $S\subset X$ ima svoju karakterističnu funkciju $\chi_S$, koliko ima podskupova toliko funkcija iz $X$ u $\{0,1\}$.

$S\subset X$ tada je njegova karakteristična funkcija $\chi_S : X\to\{0,1\}$.

2 x 2 x 2 = 8 mogućnosti

Karakteristična funkcija $\chi_S:X\to \{0,1\}$ podskupa $S$ skupa $X$ je definirana s

$\chi_S (x) = 1$ ukoliko $x\in S$

$\chi_S(x) = 0$ ukoliko $x\notin S$

$\chi:X\to\{0,1\}$

Za svaki element (ima ih 3) odredimo je li unutra ili nije (2 mogućnosti!).

OPĆENITO: A, B skupovi

gledamo funkcije iz A u B

koliko ih ima ?

A = {a,b,c}

B = {0,1}

a se može preslikati na kard(B) mogućnosti

b na kard(B) mogućnosti

c na kard(B) mogućnosti

ukupno $kard(B)\times kard(B)\times kard(B) = kard(B)^3 = kard(B)^{kard(A)}$ mogućnosti.

Skup svih funkcija iz $A$ u $B$ je potencija skupova $B^A$ i ima kardinalnost $kard(B)^{kard(A)}$

Poseban slučaj su funkcije u skup od dva elementa $\{0,1\}$ koje možemo gledati kao karakteristične funkcije podskupova.