Matematyka.pl

Pokazać, że zbiór potęgowy zbioru \(\displaystyle{ A}\) jest równoliczny ze zbiorem funkcji określonych na \(\displaystyle{ A}\) i o wartościach w zbiorze \(\displaystyle{ \{0, 1\}}\), czyli ze zbiorem \(\displaystyle{ \{f | f : A \rightarrow \{0, 1\}\}.}\)

Podzbiorowi zbioru \(\displaystyle{ A}\) przypisujesz jego funkcję charakterystyczną.

Tylko co to ma wspólnego z przeliczalnością?!

JK

Aby to udowodnić, definiujemy funkcję \(\displaystyle{ \alpha : \left\{ 0,1\right\} ^{A} \rightarrow P\left( A\right) }\), tak, że:

\(\displaystyle{ \alpha \left( f\right) = \stackrel { \rightarrow }{f ^{-1} } \left( \left\{ 1\right\} \right);}\)

czyli funkcji \(\displaystyle{ f:A \rightarrow \left\{ 0,1\right\} }\) przypisujemy jej przeciwobraz zbioru jednoelementowego \(\displaystyle{ \left\{ 1\right\}}\); wtedy \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left( \left\{ 1\right\} \right) \subset A}\), i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.

Aby wykazać, że jest to bijekcja, wykażemy po kolei, że jest to funkcja różnowartościowa, i że jest to funkcja 'na' zbiór potęgowy \(\displaystyle{ P\left( A\right).}\)
Aby wykazać, że jest to funkcja różnowartościowa, to jeśli \(\displaystyle{ \alpha \left( f_1\right) = \alpha \left( f_2\right)}\), to, z definicji tej funkcji:

\(\displaystyle{ \stackrel { \rightarrow }{f _{1}^{-1} } \left( \left\{ 1\right\} \right)= \stackrel { \rightarrow }{f _{2}^{-1} } \left( \left\{ 1\right\} \right);}\)

a ponieważ przeciwobraz dopełnienia podzbioru przeciwdziedziny funkcji jest dopełnieniem przeciwobrazu, więc:

\(\displaystyle{ \stackrel { \rightarrow }{f _{1}^{-1} } \left( \left\{ 0\right\} \right)= \stackrel { \rightarrow }{f _{1}^{-1} } \left( \left\{ 1\right\}' \right)= A \setminus \stackrel { \rightarrow }{f _{1}^{-1} } \left( \left\{ 1\right\} \right)= A \setminus \stackrel { \rightarrow }{f _{2}^{-1} } \left( \left\{ 1\right\} \right)= \stackrel { \rightarrow }{f _2^{-1} } \left( \left\{ 0\right\} \right);}\)

czyli:

\(\displaystyle{ \stackrel { \rightarrow }{f _{1}^{-1} } \left( \left\{ 0\right\} \right)=\stackrel { \rightarrow }{f _2^{-1} } \left( \left\{ 0\right\} \right)}\);

i mamy:

\(\displaystyle{ \stackrel { \rightarrow }{f _{1}^{-1} } \left( \left\{ 1\right\} \right)= \stackrel { \rightarrow }{f _{2}^{-1} } \left( \left\{ 1\right\} \right);}\)

i ponieważ \(\displaystyle{ f_1, f_2:A \rightarrow \left\{ 0,1\right\}}\), więc stąd łatwo jest pokazać, że \(\displaystyle{ f_1=f_2}\), i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

Aby wykazać, że jest to funkcja 'na', to niech \(\displaystyle{ B \subset A}\); i zdefiniujmy funkcję \(\displaystyle{ f: A \rightarrow \left\{ 0,1\right\}}\), jako:

\(\displaystyle{ f\left( x\right) = \begin{cases} 1, \hbox{ gdy } x \in B; \\ 0, \hbox{ gdy } x\not\in B. \end{cases}}\)

Wtedy \(\displaystyle{ f \in \left\{ 0,1\right\} ^{A} }\), a zatem:

\(\displaystyle{ \alpha \left( f\right) =\stackrel { \rightarrow }{f ^{-1} } \left( \left\{ 1\right\} \right)= B,}\)

czyli zbiór \(\displaystyle{ B}\) jest wartością funkcji \(\displaystyle{ \alpha}\).
Z dowolności wyboru takiego zbioru, otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.

A zatem:

\(\displaystyle{ \left\{ 0,1\right\} ^{A}\sim P\left( A\right).\square}\)

Gotowiec...

JK