Zbiory przeliczalne

Własności przestrzeni; metryczność, zwartość, spójność... Przekształcenia i deformacje... Teoria wymiaru... słowem - topologia.
mmarry
Użytkownik
Użytkownik
Posty: 101
Rejestracja: 12 wrz 2007, o 11:06
Płeć: Kobieta
Lokalizacja: Wrocław
Podziękował: 42 razy

Zbiory przeliczalne

Post autor: mmarry » 16 paź 2007, o 20:10

Pilnie proszę o pomoc, znam definicje zbiorów przeliczalnych, ale nie mogę tego jakoś pojąć i udowodnić...

Zad.1. Udowodnić, że zbiór skończonych ciągów 0-1 jest przeliczalny.
Zad.2. J.w. ciągi liczb naturalnych.
Zad.3. Udowodnić, że zbiór wszystkich ciągów 0-1 nieskończonej długości nie jest przeliczalny.
Zad.4. P(N) nieprzeliczalny.
Zad.5. P(sk)(N)={Xzaw.N:X-skończony} przeliczalny.
Zad.6. Wywnioskować z zad.1 że zbiór wszystkich programów jest zbiorem przeliczalnym.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 4140
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 98 razy
Pomógł: 414 razy

Zbiory przeliczalne

Post autor: arek1357 » 23 paź 2007, o 15:29

Wystarczy że każdemu 0 - 1 ciągowi skończonemu przyporządkujesz liczbę naturalną której zapis dwójkowy jest nieskończony.
Możesz jeszcze nawet do każdego ciągu 0 1 dołożyć 1 na początku żeby wyeliminować zera na początku...

Awatar użytkownika
Sir George
Użytkownik
Użytkownik
Posty: 1145
Rejestracja: 27 kwie 2006, o 10:19
Płeć: Mężczyzna
Lokalizacja: z Konopii
Podziękował: 4 razy
Pomógł: 203 razy

Zbiory przeliczalne

Post autor: Sir George » 23 paź 2007, o 15:51

Ad. zad.2. Podobnie jak zaproponował arek1357 w zad.1.: dopisujesz 1 na początku takowego ciągu, a następnie utożsamiasz ów ciąg z wykładnikami w rozkładzie liczby naturalnej na czynniki pierwsze (i korzystasz z jednoznaczności rozkładu), np. \(\displaystyle{ (0,0,1,0,2,4,0) \ \longrightarrow\ 2^0\cdot3^4\cdot5^2\cdot7^0\cdot11^1\cdot13^0\cdot17^0\cdot19^1}\)

[ Dodano: 23 Października 2007, 16:54 ]
Ad. zad.3. zwykły argument przekątniowy... tj. elementy każdego zbioru przeliczalnego można ustawić w ciąg (innymi słowy istnieje bijekcja między owym zbiorem a zbiorem liczb naturalnych). Popatrz, gdzie w owym ciągu może znajdować się element, który na n-tym miejscu różni się z n-tym elementem owego ciągu...

[ Dodano: 23 Października 2007, 16:56 ]
Ad. zad.4. Wprost przez utożsamienie podzbioru zbioru liczb naturalnych z ciągiem zerojedynkowym (jedynka na n-tym miejscu oznacza, że n należy do podzbioru)

[ Dodano: 23 Października 2007, 16:57 ]
Ad. zad.5. Podobnie jak zad.4 (plus zad.1.)

ODPOWIEDZ