Zoran Skoda partitivni skup

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

$$\mathcal{P}(S) = \{ P | P\subseteq S\}$$

Kardinalni broj skupa $\mathcal{P}(S)$ je $2^{kard(S)}$. Npr. kardinalnost praznog skupa je $0$, 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\gt K$.

Ako je $K$ konačan broj, onda je $2^K$ zaista broj koji dobijamo potenciranjem broja $2$. Zaista, svaki podskup $P$ skupa $S$ određuje karakterističnom funkcijom tog podskupa, $\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 podskupa od $S$, naime skupa

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

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

category: zadarmat1