Zoran Skoda
ekvipotentni skupovi

Dva skupa AA i BB su ekvipotentni ako postoji bijekcija s AA na BB. Biti ekvipotentan je relacija ekvivalencije. Zaista,

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

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

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

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 55 je apstraktno svojstvo koje karakterizira sve skupove od 55 elemenata. Skup od 55 salveta je predstavnik te klase, dakle predstavnik kardinalnog broja 55. 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)kard(T)kard(S)\leq kard(T) ako postoji injekcija iz SS u TT. U teoriji skupova (s aksiomom izbora) svaka dva skupa su usporediva u smislu da ili kard(S)kard(T)kard(S)\leq kard(T) ili kard(T)kard(S)kard(T)\leq kard (S), a (prema Cantor-Schroeder-Bernsteinovom teoremu) oboje vrijedi akko kard(S)=kard(T)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<H(LHLH).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 0\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 02^{\aleph_0}, tj. postoji bijekcija 𝒫()\mathbb{R}\to \mathcal{P}(\mathbb{N}).

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

P ϕ={sS|ϕ(s)=1}. P_\phi = \{ s\in S | \phi(s) = 1\}.

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

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

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

Dokaz. To je očito ako je K=0=kard()K=0 = kard(\emptyset) (postoji injekcija u svaki skup, ali ne postoji injekcija iz jednočlanog skupa {}\{\emptyset\} u \emptyset).

Neka je K=kard(S)>0K = kard(S)\gt 0. Tada postoji injekcija iz SS u 𝒫(S)\mathcal{P}(S) zadana formulom x{x}x\mapsto \{ x\}, xS\forall x\in S. Trebamo pokazati da SS nije ekvipotentan s 𝒮\mathcal{S}. Pretpostavimo suprotno, dakle da neka surjekcija f:S𝒮f: S\to\mathcal{S} postoji. Promatrajmo skup R𝒫(S)R \in\mathcal{P}(S),

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

Tada postoji element uSu\in S takav da je f(u)=Rf(u) = R (jer je ff surjekcija). Ako je uRu\in R tada uf(u)u\in f(u) pa uRu\notin R po definiciji od RR, a ako uRu\notin R onda uf(u)u\notin f(u) pa uRu\in R po definiciji od RR. Dakle, ni jedna od mogućnosti uRu\in R, uRu\notin R nije konzistentna. Dakle, nije moguće da postoji surjekcija s SS na 𝒫(S)\mathcal{P}(S).

category: zadarmat1, zadarmat4

Last revised on May 18, 2017 at 14:05:32. See the history of this page for a list of all contributions to it.