Logika, zadanie nr 1364

Autor	Zadanie / Rozwiązanie
jehns postów: 10	2013-05-31 17:03:53 Jakiej mocy jest zbiór F wszystkich funkcji z N do N majacych skończony zbiór wartości? Odpowiedź uzasadnić

tumor postów: 8070	2013-05-31 19:05:19 a) jest tych funkcji co najmniej $ \mathfrak{c}$ Bo funkcji $f\colon N \to \{0,1\}$ jest dokładnie $ \mathfrak{c}$, te funkcje to ciągi zerojedynkowe nieskończone, które możemy utożsamiać z rozwinięciem dwójkowym liczb rzeczywistych z przedziału $[0,1]$. Utożsamienie nie jest ścisłe, bo $0,1=0,0(1)$, funkcji jest zatem co najmniej tyle ile liczb rzeczywistych w tym przedziale. Natomiast każda liczba ma najwyżej dwa przedstawienia w postaci ciągów, a $ \mathfrak{c}+\mathfrak{c}=\mathfrak{c}$ (i uwaga Zamiast zbioru $\{0,1\}$ można oczywiście wziąć $\{0,1,2,3,4,5,6,7,8,9\}$ i rozważać rozwinięcia dziesiętne, albo jeszcze inny zbiór i inne rozwinięcia) b) jest tych funkcji co najwyżej $ \mathfrak{c}$ Zapewne było na zajęciach, że skończonych podzbiorów $N$ jest przeliczalnie wiele. Uzasadnia się to ustalając $n$, pokazując, że n-elementowych podzbiorów N jest przeliczalnie wiele, bo $N^n\sim N$, a potem sumując po wszelkich $n\in N$, dostajemy przeliczalną sumę zbiorów przeliczalnych, równoliczną z $N^2$ czyli z $N$. W przypadku funkcji użyjemy podobnej argumentacji. Dla ustalonego skończonego podzbioru $A$ zbioru $N$ mamy co najwyżej $\mathfrak{c}$ funkcji $f\colon N\to A$, a zbiorów takich jest przeliczalnie wiele. Przeliczalna suma zbiorów mocy $\mathfrak{c}$ jest mocy $\mathfrak{c}$ (jako że $R\le N\times R \le R\times R \sim R$)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj