Ekvipotentnost nizova nad {0,1} i intervala <0,1> (objasnjenje gradiva)

[koryanshea]

na predavanjima iz TS je dokazivana ekvipotentnost svih nizova nula i jedinica pomocu Cantor-Schroeder-Bernsteinovog teorema na slijedeci nacin:

1) injekcija sa <0,1> u {0,1}^IN:
binarni zapis broja 0,x0x1x2.... -> (xn) i s tim nemam problema

2) injekcija sa {0,1}^IN u <0,1> sa
(x_n) -> 0,x_0x_1.... tj. elementi niza su redom znamenke realnog br nakon decimalne tocke.
i pise da je to injekcija. međutim, zapis realnog broja nije jedinstven (tj. postoje takvi), pa su
0,x1...xm1000000000000000000000... i
0,x1...xm0111111111111111111111...
dva zapisa za isti realan broj. Dakle, dva razlicita niza se ocito preslikavaju u jedan broj, pa to ne moze biti injekcija. Ako na neki nacin zelimo "ukinit" jedan oblik zapisa realnog broja, onda preslikavanje nije definirano za sve nizove.

what am i missing???

_________________
"Download the files to a non-networked, firewalled computer."
- Dr. Elizabeth Weir

[koryanshea]

hm, evo jedno rjesenje ovog problema ali bih voljela znati da li postoji nesto elegantnije jer imam dojam da bi profesor spomenio ovu pricu:

znaci zbog 1) imamo da je k(<0,1>) ⇐ k({0,1}^IN)

tj, binarnih nizova ima "barem c" tj. definitivno ih ima neprebrojivo mnogo.
svi ovi "problematicni" realni brojevi su u binarnom zapisu oblika
0,konacan binaran niz pa beskonacno mnogo nula (ili jedinica, svejedno)
Konacnih binarnih nizova ima prebrojivo mnogo, pa i tih "problematicnih" brojeva ima prebrojivo mnogo.

Kad skupu svih binarnih nizova oduzmemo nizove gornjeg oblika, dobijemo skup binarnih nizova ekvipotentan originalnom skupu nizova (neprebrojivom skupu smo oduzeli prebrojiv skup), i sada sa tog novog skupa mozemo dobro definirati injekciju na <0,1>.

_________________
"Download the files to a non-networked, firewalled computer."
- Dr. Elizabeth Weir