Równoliczność i bijekcja

[Szwanceneger]

Dzień dobry. Czy mógłby ktoś przedstawić dowód tego, że \(\displaystyle{ |P(A)|= \left\{0,1 \right\} ^{A} }\) ? Ponoć dowodzi się to pokazując, że istnieje bijekcja \(\displaystyle{ F:P(A) \rightarrow \left\{0,1 \right\} ^{A} }\) jednak nie jestem w stanie zrozumieć jak to można pokazać.

[janusz47]

Z każdym podzbiorem \(\displaystyle{ S \subseteq A }\) kojarzymy funkcję charakterystyczną \(\displaystyle{ \chi_{S}: \ \ S \rightarrow \{0, 1\}:}\)

\(\displaystyle{ \chi_{S}(x) = \begin{cases} 1 \ \ \text{gdy} \ \ x\in S \\ 0 \ \ \text{gdy} \ \ x\notin S \end{cases} }\)

Odwrotnie, każda funkcja \(\displaystyle{ \chi: A \rightarrow \{0, 1\} }\) postaci \(\displaystyle{ \chi_{S}: \ \ (S \subseteq A) }\) określa jednostkowy zbiór \(\displaystyle{ S = \{ x\in A : \ \ \chi(x) = 1 \}. }\)

Istnieje więc bijekcja taka, że

\(\displaystyle{ |P(A)| = |\{0, 1\}^{A}| = 2^{|A|}. }\)

\(\displaystyle{ \Box }\)

[Jan Kraszewski]

Z każdym podzbiorem \(\displaystyle{ S \subseteq A }\) kojarzymy funkcję charakterystyczną \(\displaystyle{ \chi_{S}: \ \red{S} \rightarrow \{0, 1\}}\)

Dziedziną funkcji charakterystycznej zbioru \(\displaystyle{ S}\) nie jest \(\displaystyle{ S}\), tylko \(\displaystyle{ A}\), zatem

\(\displaystyle{ \chi_{S}: A \rightarrow \{0, 1\}}\).

W ten sposób definiujemy funkcję \(\displaystyle{ F:P(A) \rightarrow \{0,1\}^A, F(S)=\chi_S}\), która jest szukaną bijekcją. Trzeba tylko pokazać, że jest ona różnowartościowa (co jest proste, ale nie zostało zrobione) oraz że jest "na", co zostało opisane tutaj:

Odwrotnie, każda funkcja \(\displaystyle{ \chi: A \rightarrow \{0, 1\} }\) postaci \(\displaystyle{ \chi_{S}: \ \ (S \subseteq A) }\) określa jednostkowy zbiór \(\displaystyle{ S = \{ x\in A : \ \ \chi(x) = 1 \}. }\)

ale sformułowanie wygląda średnio. Raczej tak:

Dla dowolnej funkcji \(\displaystyle{ \psi: A \rightarrow \{0, 1\} }\), jeśli weźmiemy zbiór \(\displaystyle{ S = \{ x\in A : \psi(x) = 1 \} }\), to mamy \(\displaystyle{ \psi=\chi_S=F(S)}\) (co tak naprawdę należałoby jeszcze sprawdzić, pokazując że dla dowolnego \(\displaystyle{ x\in A}\) mamy \(\displaystyle{ \psi(x)=\chi_S(x)}\)), zatem funkcja \(\displaystyle{ F}\) jest "na".

JK

[Jakub Gurak]

Albo inaczej, można zdefiniować funkcję \(\displaystyle{ \alpha : \left\{ 0,1\right\} ^{A} \rightarrow P\left( A\right), }\) jako \(\displaystyle{ \alpha \left( f\right)= \stackrel { \rightarrow }{f ^{-1} } \left\{ 1\right\}, }\) która funkcji \(\displaystyle{ f:A \rightarrow \left\{ 0,1\right\}}\) przypisuje jej przeciwobraz zbioru \(\displaystyle{ \left\{ 1\right\}, }\) i pokazać, że jest bijekcją, co udowodniłem TUTAJ. (I nie trzeba nic mówić o funkcjach charakterystycznych ). Polecam cały ten post przeczytać, są tam bardzo ciekawe rzeczy.

[Jan Kraszewski]

Albo inaczej, można zdefiniować funkcję \(\displaystyle{ \alpha : \left\{ 0,1\right\} ^{A} \rightarrow P\left( A\right), }\) jako \(\displaystyle{ \alpha \left( f\right)= \stackrel { \rightarrow }{f ^{-1} } \left\{ 1\right\}, }\)

Nie bardzo "inaczej", skoro \(\displaystyle{ \alpha=F^{-1}.}\)

(I nie trzeba nic mówić o funkcjach charakterystycznych ).

O funkcjach charakterystycznych mówi się nie dlatego, że "trzeba", ale dlatego, że "warto". U Ciebie też pojawia się funkcja charakterystyczna, tylko nie używasz tej nazwy - tak samo w swoim dowodzie mogę zdefiniować funkcję \(\displaystyle{ \chi_S}\), tylko nie nazywać jej funkcją charakterystyczną...

JK

[Jakub Gurak]

A z ciekawości, dlaczego warto

(Bo ja nie przepadam za natłokiem niepotrzebnych nazw i oznaczeń).

[Jan Kraszewski]

Ponieważ

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Indicator_function

pojawia się w matematyce w wielu miejscach.

JK