Daca P(N) este multimea submultimilor multimii numerelor naturale ( ), demonstrati: card(P(N))=card(R), unde R este multimea numerelor reale.

Se foloseste teorema Cantor - Bernstein: date fiind doua multimi A si B; daca exista doua functii injective

, atunci cele doua multimi sunt echipotente (au acelasi cardinal)

Ati putea, va rog, sa fiti putin mai explicit? Am cautat pe wikipedia despre |R|(http://en.wikipedia.org/wiki/Cardinality_of_the_continuum) si nu imi este foarte clara nici macar explicatia intuitiva .

Mai concret...am inteles intuitiv ca putem pune zecimalele unui numar real intr-o corespondenta injectiva cu N si ca fiecare numar real are, de fapt, aleph-zero zecimale. Dar trecerea pentru simpificare la sistemul binar mi se pare un pic cam abrupta...isi atinge scopul, pentru ca asa e cel mai clar ca |R|=2^aleph-zero, dar...nu e cam "hocus-pocus, facem o magie si a iesit" ? In limbaj matematic...nu se pierde generalitatea presupunand ca suntem in binar?


Multumesc.

[Citat] Ati putea, va rog, sa fiti putin mai explicit? Am cautat pe wikipedia despre |R|(http://en.wikipedia.org/wiki/Cardinality_of_the_continuum) si nu imi este foarte clara nici macar explicatia intuitiva . Mai concret...am inteles intuitiv ca putem pune zecimalele unui numar real intr-o corespondenta injectiva cu N si ca fiecare numar real are, de fapt, aleph-zero zecimale. Dar trecerea pentru simpificare la sistemul binar mi se pare un pic cam abrupta...isi atinge scopul, pentru ca asa e cel mai clar ca |R|=2^aleph-zero, dar...nu e cam "hocus-pocus, facem o magie si a iesit" ? In limbaj matematic...nu se pierde generalitatea presupunand ca suntem in binar? Multumesc.

Nu e chiar asa. Corespondenta dintre partile multimii numerelor naturale si pozitia cifrelor egale cu 1 nu este bijectiva. Buba provine din exemplul urmator:

Demonstratia se bazeaza pe constructia a doua functii injective

, respectiv

, combinata cu teorema Cantor-Bernstein. In final, functia bijectiva cautata nu se exprima in mod explicit.

Intelesesem ideea inca din primul dumneavoastra raspuns. Insa nu cunosc teorema Cantor-Bernstein, dar o pot cauta.

Totusi, din spirit parazit, va rugasem sa imi oferiti o alternativa, eventual mai intuitiva.

Sincer, aceasta problema mi-a starnit curiozitatea inca din prima clipa cand am vazut-o, insa teoria multimilor e un domeniu pe care nu l-am aprofundat si nu intentionez sa o fac in viitorul apropiat. Daca nu se poate rezolva decat foarte riguros si necesita cunostinte avansate de teoria multimilor, va rog sa imi spuneti. Daca nu, ma multumesc si cu o explicatie intuitiva.

Multumesc.

O schita a demonstratiei teoremei Cantor-Bernstein. Fie

doua functii injective. Folosim urmatoarea

Lema (Tarski, adaptare). Fie

o functie monotona, adica o functie care verifica propozitia

Atunci functia

are cel putin un punct fix.

Ca idee un punct fix este construit 'explicit' astfel:

Revenind la teorema, definim functia

Aceasta functie este monotona (usor de observat), deci conform lemei exista

astfel incat

.

In final, o bijectie intre cele doua multimi din enunt se defineste astfel:

(nu este greu de vazut ca functia este bine definita, etc.)