szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 maja 2018, o 22:58 
Użytkownik

Posty: 146
Niech A będzie n-elementowym zbiorem.

Dlaczego P(A) = 2^n?
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2018, o 23:04 
Użytkownik
Avatar użytkownika

Posty: 1395
Lokalizacja: hrubielowo
P(A) to zbiór wszystkich podzbiorów. Podzbiorów o 0 elementach jest {n \choose 0}, podzbiorów o 1 jest {n \choose 1}, podzbiorów o 2 elementach jest {n \choose 2}... i tak aż do {n \choose n}. Czyli wszystkich podzbiorów jest {n \choose 0} + {n \choose 1} + {n \choose 2} +...+ {n \choose n}. Z dwumianu Newtona wynika że suma ta zwija się do 2^n.


Można też jednoznacznie utożsamić dowolny podzbiór A z n wyrazowym ciągiem 0 i 1. Jeśli dany element jest w podzbiorze to na to miejsce kładziemy 1 a jeśli go nie ma to kładziemy 0. Taką bijekcją można zakodować wszystkie podzbiory których jest 2^n bo na każdym z n miejsc można wybrać 0 lub 1 (czyli 2 możliwości).
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2018, o 23:09 
Użytkownik

Posty: 146
A ma to może jakiś związek z faktem, że zbiór funkcji f: A  \rightarrow B (A,B - skończone, niepuste).

To \left| B^A\right|  = \left| B\right|^{\left| A\right| }?
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2018, o 23:13 
Użytkownik
Avatar użytkownika

Posty: 1395
Lokalizacja: hrubielowo
To co napisałeś jest raczej przypadkiem ogólniejszym. Jeśli B=\left\{ 0,1\right\} to można by się doszukiwać podobieństw z tą bijekcją o które już pisałem. Nie chce wyciągać pochopnych wniosków.
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2018, o 23:18 
Użytkownik

Posty: 146
Bijekcją?
Mam wątpliwości co do różnowartościowości tej funkcji.
Góra
Mężczyzna Offline
PostNapisane: 2 maja 2018, o 23:48 
Użytkownik
Avatar użytkownika

Posty: 1395
Lokalizacja: hrubielowo
To rozważ jakiś przykład. Oczywiście to nie jest dowód ale pozwala to uświadomić sobie jak miało by działać to "kodowanie". Niech A=\left\{ 1,2,3\right\} wtedy:

\emptyset \ \leftrightarrow \ 000
\left\{ 1\right\}  \ \leftrightarrow \ 100
\left\{ 2\right\} \ \leftrightarrow \ 010
\left\{ 3\right\}  \ \leftrightarrow \ 001
\left\{ 1,2\right\}  \ \leftrightarrow \ 110
\left\{ 1,3\right\}  \ \leftrightarrow \ 101
\left\{ 2,3\right\}  \ \leftrightarrow \ 011
\left\{ 1,2,3\right\}  \ \leftrightarrow \ 111

a taka bijekcja istnieje na pewno choćby dla tego że ciągów n elementowych z 0 lub 1 jest 2^n a moc zbioru potęgowego zbioru n elementowego to 2^n (co uzasadnia pierwszy argument).

-- 2 maja 2018, o 23:50 --

zresztą z każdym takim ciągiem jest spokrewniony odpowiadający mu podzbiór w zbiorze potęgowym więc jak niby mamy dostać coś różnowartościowego.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Iloczyny kartezjańskie zbioru  MakCis  5
 Wyznaczyć kres dolny i kres górny zbioru  bob1000  13
 Szikic Zbioru  sorlag123  1
 Czy dla dowolnego zbioru zachodzi  Arytmetyk  1
 Znajdź sumę nieskończoną zbioru  szymonber  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl