Cześć :)
Iniekcje umiem zliczać. Suriekcje też. Ale jak zliczyć bijekcje. Trzeba by wziąć część wspólną, tylko jak to zliczyć? Chodzi mi oczywiście o zbiory przeliczalne.
zliczanie bijekcji
-
sebnorth
- Użytkownik
- Posty: 635
- Rejestracja: 12 sty 2011, o 16:27
- Płeć: Mężczyzna
- Lokalizacja: Puck i Trójmiasto
- Pomógł: 201 razy
zliczanie bijekcji
weźmy bijekcje zbioru liczb naturalnych
jeśli \(\displaystyle{ f}\) jest taką bijekcją to można z nią stowarzyszyć ciąg \(\displaystyle{ 0-1}\):
\(\displaystyle{ a_{f,n} = \begin{cases} 0 \mbox{ jeśli} f(n) = n \\ 1 \mbox{ jeśli} f(n) \neq n \end{cases}}\)
Dla ciągów, powiedzmy b_n, które nie mają jedynek lub mają więcej niż jedną jedynkę istnieje f, takie, że \(\displaystyle{ b_n = b_{f,n}.}\)
Dla ciągów, które mają dokładnie jedną jedynkę takie f nie istnieje. (jeśli \(\displaystyle{ f(n) = m \neq n}\) to musi istnieć jakieś \(\displaystyle{ k}\), że \(\displaystyle{ f(k) = n}\), czyli \(\displaystyle{ b_n = 1}\) oraz \(\displaystyle{ b_k = 1}\))
Ciągów, które mają dokładnie jedną jedynkę jest przeliczalnie wiele.
Ostatecznie bijekcji jest co najmniej tyle ile ciągów 0-1 z wyjątkiem przeliczalnej ich ilości a to łącznie jest nieprzeliczalnie wiele, dokładnie mocy continuum.
jeśli \(\displaystyle{ f}\) jest taką bijekcją to można z nią stowarzyszyć ciąg \(\displaystyle{ 0-1}\):
\(\displaystyle{ a_{f,n} = \begin{cases} 0 \mbox{ jeśli} f(n) = n \\ 1 \mbox{ jeśli} f(n) \neq n \end{cases}}\)
Dla ciągów, powiedzmy b_n, które nie mają jedynek lub mają więcej niż jedną jedynkę istnieje f, takie, że \(\displaystyle{ b_n = b_{f,n}.}\)
Dla ciągów, które mają dokładnie jedną jedynkę takie f nie istnieje. (jeśli \(\displaystyle{ f(n) = m \neq n}\) to musi istnieć jakieś \(\displaystyle{ k}\), że \(\displaystyle{ f(k) = n}\), czyli \(\displaystyle{ b_n = 1}\) oraz \(\displaystyle{ b_k = 1}\))
Ciągów, które mają dokładnie jedną jedynkę jest przeliczalnie wiele.
Ostatecznie bijekcji jest co najmniej tyle ile ciągów 0-1 z wyjątkiem przeliczalnej ich ilości a to łącznie jest nieprzeliczalnie wiele, dokładnie mocy continuum.