Zoran Skoda ekvipotentni skupovi

Relacija ekvipotentnosti

Dva skupa $A$ i $B$ su jednakobrojni ili ekvipotentni ako postoji bijekcija s $A$ na $B$. Biti ekvipotentan je relacija ekvivalencije na klasi svih skupova. Zaista,

• (TRANZITIVNOST) Moramo pokazati da ako su $A$ i $B$ ekvipotentni i $B$ i $C$ ekvipotetni, tada su $A$ i $C$ ekvipotentni. Zaista, ako su $A$ i $B$ ekvipotentni tada postoji bijekcija $f:A\to B$. Ako postoji bijekcija $f:A\to B$ i bijekcija $g:B\to C$ tada je kompozicija $g\circ f: A\to C$ također bijekcija, dakle $A$ i $C$ su zaista ekvipotentni.

• (SIMETRIČNOST) Ako su $A$ i $B$ ekvipotentni tada postoji bijekcija $f:A\to B$. Inverzna funkcija je tada također bijekcija $f^{-1}:B\to A$. Dakle $B$ i $A$ su ekvipotentni.

• (REFLEKSIVNOST) Identiteta $id_A:A\to A$ je injekcija i surjekcija, dakle bijekcija. Dakle za svaki skup $A$ postoji barem jedna bijekcija s $A$ na $A$ (naime identiteta) pa je $A$ ekvipotentan sa samim sobom.

Kardinalni brojevi

Razredi (klase) ekvivalencije s obzirom na relaciju ekvipotentnosti zovemo kardinalni brojevi ili kardinali. Kardinalni broj je dakle klasa svih skupova za svaki par kojih postoji bijekcija s jednog na drugi. Intuitivno, kardinalni broj $5$ je apstraktno svojstvo koje karakterizira sve skupove od $5$ elemenata. Skup od $5$ salveta je predstavnik te klase, dakle predstavnik kardinalnog broja $5$. Ako je skup $S$ predstavnik kardinalnog broja $\kappa$, kažemo da je $S$ kardinalnosti $\kappa$.

Prazan skup je ekvipotentan samom sebi; kažemo da prazni skup ima nula elemenata. Sve ostale kardinalnosti imaju mnogo predstavnika.

Kardinalnosti skupova možemo uspoređivati: $kard(S)\leq kard(T)$ ako postoji injekcija iz $S$ u $T$. U teoriji skupova (s aksiomom izbora) svaka dva skupa su usporediva u smislu da ili $kard(S)\leq kard(T)$ ili $kard(T)\leq kard (S)$, a (prema Cantor-Schroeder-Bernsteinovom teoremu) oboje vrijedi akko $kard(S) = kard(T)$. Dakle, $\leq$ je relacija nestrogog linearnog uređaja na klasi svih kardinala, štoviše taj uređaj je dobar (svaki podskup ima minimalni element). Kao i obično, nestrogom uređaju $\leq$ odgovara relacija strogog linearnog uređaja $\lt$

$$K\lt H \Leftrightarrow (L\leq H \wedge L\neq H).$$

Skup je konačan ako nije ekvipotentan ni jednom svom pravom podskupu (podskup nekog skupa je pravi podskup ako je podskup i različit od tog skupa). Inače je beskonačan. Za kardinalni broj kažemo da je konačan ako je on kardinalni broj konačnog skupa, te kažemo da je beskonačan inače. Kardinalne brojeve nepraznih konačnih skupova možemo identificirati s prirodnim brojevima. Zbrajanje prirodnih brojeva odgovara kardinalnom broju disjunktne unije. Nulu tada identificiramo s kardinalnim brojem praznog skupa. Kako svaka klasa kardinala ima minimalni element, to postoji najmanji beskonačni kardinal, a to je kardinalni broj skupa prirodnih brojeva. Taj kardinal zovemo $\aleph_0$ (hebrejski znak koji se čita alef nula). Ako je skup ekvipotentan sa skupom prirodnih brojeva kažemo da je prebrojivo beskonačan ili da je prebrojiv. Skup je najviše prebrojiv ako je konačan ili prebrojiv. Kardinalnost skupa realnih brojeva je $2^{\aleph_0}$, tj. postoji bijekcija $\mathbb{R}\to \mathcal{P}(\mathbb{N})$ (notacija $2^\kappa$ gdje je $\kappa$ kardinalni broj je objašnjena niže).

Jedan prikaz teme o kardinalnim brojevima je u dijelu lekcije mat1-171120-1 i u lekciji mat1-171120-2.

Kardinalnost partitivnog skupa i skupa funkcija

Ako je $K = kard(S)$ kardinalnost nekog skupa $S$ tada je kardinalnost partitivnog skupa $\mathcal{P}(S)$ (tj. skupa svih podskupova od $S$) označena s $2^K$. Ako je $K$ konačan broj, onda je $2^K$ zaista broj koji dobijamo običnim potenciranjem? broja $2$. Zaista, svaki podskup $P$ skupa $S$ određuje karakterističnom funkcijom tog skupa, $\chi_P:S\to \{0,1\}$ koja je zadana s $\chi_P(s) = 1$ ako je $s\in P$ i $\chi_P(s) = 0$ ako je $s\notin P$. S druge strane, svaka funkcija $\phi: S\to \{0, 1\}$ je karakteristična funkcija nekog skupa, naime skupa

$$P_\phi = \{ s\in S | \phi(s) = 1\}.$$

Drugim riječima, vrijednost $\phi(s) = 1$ je signal da je $s\in P$; kako je svaki skup određen svojim elementima to znači da su podskupovi od $S$ u bijekciji s funkcijama iz $S$ u $\{0, 1\}$. Koliko ima takvih funkcija ? Pa za svaki element imamo dva izbora: zadati $0$ na tom elementu i zadati $1$ na tom elementu. Dakle, za dva elementa imamo $2\times 2$ načina, za tri elementa, $2\times 2\times 2$ načina itd. Na kraju za $K$ elemenata, ako je $K$ konačan imamo $2^K$ elemenata.

Ako je kardinal $K$ beskonačan, onda je $2^K$ samo oznaka kardinalnosti partitivnog skupa od skupa s $K$ elemenata (to možemo uzeti kao definiciju potenciranja za moguće beskonačne kardinale).

Općenitije, ako su $A$ i $B$ skupovi, tada s

$$B^A = \{ funkcija\,\,\,f: A\to B \}$$

označavamo skup svih funkcija iz $A$ u $B$.

Za konačne brojeve vrijedi da je $kard(B^A) = kard(B)^{kard(A)}$ pa tako definiramo potenciranje kardinalnih brojeva koji mogu biti i beskonačni, a $2^{kard(A)}$ je poseban slučaj kad je $kard(B) = 2$. Riječima, potencija $L^K$ kardinalnog broja $L$ na kardinalni broj $K$ je kardinalni broj skupa funkcija $B^A$ iz (ma kojeg) skupa $A$ koji je predstavnik od $K$ u (ma koji) skup $B$ koji je predstavnik od $L$.

Cantorov teorem

Cantorov teorem. Za svaki kardinal $K$ vrijedi $K\lt 2^K$.

Dokaz. Tvrdnja je očita ako je $K = 0 = kard(\emptyset)$ (postoji injekcija iz praznog skupa u ma koji skup, ali ne postoji injekcija iz jednočlanog skupa $\{\emptyset\}$ u $\emptyset$).

Neka je $K = kard(S)\gt 0$. Tada postoji injekcija iz $S$ u $\mathcal{P}(S)$, naime funkcija zadana formulom $x\mapsto \{ x\}$, $\forall x\in S$ je injekcija. To znači da je $kard(S)\leq 2^{kard(S)}$. Preostaje pokazati $kard(S)\neq 2^{kard(S)}$. To znači da $S$ nije ekvipotentan s $\mathcal{P}(S)$. Pretpostavimo suprotno, dakle da neka bijekcija $f: S\to\mathcal{P}(S)$ postoji; mi ćemo sad pokazati da čak i slabija tvrdnja da postoji surjekcija $f:S\to\mathcal{P}(S)$ vodi na proturječje. Promatrajmo skup $R \in\mathcal{P}(S)$,

$$R := \{ x\in S | x\notin f(x)\}.$$

Tada postoji element $u\in S$ takav da je $f(u) = R$ (jer je $f$ surjekcija). Ako je $u\in R$ tada $u\in f(u)$ pa $u\notin R$ po definiciji od $R$, a ako $u\notin R$ onda $u\notin f(u)$ pa $u\in R$ po definiciji od $R$. Dakle, ni jedna od mogućnosti $u\in R$, $u\notin R$ nije konzistentna. Dakle, nije moguće da postoji surjekcija s $S$ na $\mathcal{P}(S)$. Time je Cantorov teorem dokazan. Ova ideja dokaza poznata je kao Cantorov dijagonalni argument.

category: zadarmat1, zadarmat4