Zoran Skoda partitivni skup

Neka je SS skup. Skup čiji elementi su svi mogući podskupovi skupa SS zovemo partitivni skup skupa SS (etimološki bi to mogli tumačiti kao skup svih dijelova skupa SS (Lat. pars (fem.), gen. partis ‘dio’); ili skup svih podskupova od SS). Engleski naziv je power set. Tako se i u hrvatskom i u engleskom uvriježila notacija 𝒫(S)\mathcal{P}(S). Simbolički,

𝒫(S)={P|PS} \mathcal{P}(S) = \{ P | P\subseteq S\}

Kardinalni broj skupa 𝒫(S)\mathcal{P}(S) je 2 kard(S)2^{kard(S)}. Npr. kardinalnost praznog skupa je 00, a partitivni skup praznog skupa ima jedan element i taj element je upravo prazan skup. Dakle 𝒫()={}\mathcal{P}(\emptyset) = \{\emptyset\}\neq \emptyset. Za svaki skup (konačan ili beskonačan), kardinalnost partitivnog skupa je strogo veća od kardinalnosti početnog skupa. Dakle, 2 K>K2^K\gt K.

Ako je KK konačan broj, onda je 2 K2^K zaista broj koji dobijamo potenciranjem broja 22. Zaista, svaki podskup PP skupa SS određuje karakterističnom funkcijom tog podskupa, χ 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 podskupa od SS, naime skupa

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

Drugim riječima, vrijednost ϕ(s)=1\phi(s) = 1 signalizira 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.

category: zadarmat1

Last revised on November 6, 2017 at 01:53:24. See the history of this page for a list of all contributions to it.