Zbiory przeliczalne

mmarry · 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.

arek1357 · 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...

Sir George · 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.)