Insiemi finiti ed infiniti - (2)
Insiemi finiti ed infiniti - (2)
Scrivere una funzione φ iniettiva da Z in PN (dove con PN si indica l’insieme costituito da tutti i sottoinsiemi di N, l'insieme dei numeri naturali). Dire se tale funzione può essere suriettiva.
Qualche idea sulla soluzione, please?
Qualche idea sulla soluzione, please?
Una funzione $ \varphi $ di quel tipo può essere ad esempio
$ \varphi \colon \mathbb{Z} \to \wp ( \mathbb{N}) $
$ a \in \mathbb{Z} \mapsto \{a\} \in \wp( \mathbb{N}) $ se $ a>0 $
$ a \in \mathbb{Z} \mapsto \{-a,1\} \in \wp( \mathbb{N}) $ se $ a \leq 0 $
Nessuna funzione $ \varphi $ del tipo richiesto può essere suriettiva, poichè se fosse suriettiva ed iniettiva allo stesso tempo sarebbe una biiezione, ma questo non è possibile poichè $ \mathbb{Z} $ e $ \wp (\mathbb{N}) $ non sono equipotenti. Infatti il primo è numerabile, il secondo ha la cardinalità del continuo.
$ \varphi \colon \mathbb{Z} \to \wp ( \mathbb{N}) $
$ a \in \mathbb{Z} \mapsto \{a\} \in \wp( \mathbb{N}) $ se $ a>0 $
$ a \in \mathbb{Z} \mapsto \{-a,1\} \in \wp( \mathbb{N}) $ se $ a \leq 0 $
Nessuna funzione $ \varphi $ del tipo richiesto può essere suriettiva, poichè se fosse suriettiva ed iniettiva allo stesso tempo sarebbe una biiezione, ma questo non è possibile poichè $ \mathbb{Z} $ e $ \wp (\mathbb{N}) $ non sono equipotenti. Infatti il primo è numerabile, il secondo ha la cardinalità del continuo.
Va anche precisato che A non è vuoto
Se A è finito ciò è ovvio: se |A|=n, esistono n sottoinsiemi di A (elementi quindi di $ \mathcal{P}({A}) $) formati ciascuno da uno solo elemento di A (quindi $ |\mathcal{P}({A})| $ è almeno pari a n) più il sottoinsieme vuoto (e con questo abbiamo la disuguaglianza in senso stretto).
E con gli insiemi infiniti, notoriamente più "giocherelloni"? Si può fare: supponiamo infatti che A e $ \mathcal{P}({A}) $ siano equipotenti per qualche A avente infiniti elementi. Ciò comporta che esiste una funzione biiettiva da A a $ \mathcal{P}({A}) $, cioè una funzione che associa a ogni sottoinsieme $ S_i $ di A uno e un solo elemento $ a_i $ di A. Alcuni $ S_i $ (che chiameremo di qui in poi, con ardita innovazione lessicale, autocontenuti) conterranno l'elemento a loro associato $ a_i $ e altri no. Chiamiamo S' il sottoinsieme formato da tutti gli $ a_i $ tali che il sottoinsieme a loro associato non è autocontenuto. Qual'è l'elemento associato a S'? Di sicuro tale elemento non fa parte di S': se così fosse, S' sarebbe autocontenuto e conterrebbe quindi l'elemento associato a un sottoinsieme autocontenuto, in contrasto con definizione di S' data. Ma nemmeno può essere esterno ad S': in tal caso S' sarebbe non-autocontenuto e l'elemento ad esso associato dovrebbe far parte di S', in contrasto con quanto appena detto. Ne consegue che è impossibile associare a S' un elemento di A e quindi $ \mathcal{P}({A}) $ ha cardinalità superiore a n=|A|.
Lo so, non sono stato molto chiaro ma abbiate pazienza...
Salut
Ob
Se A è finito ciò è ovvio: se |A|=n, esistono n sottoinsiemi di A (elementi quindi di $ \mathcal{P}({A}) $) formati ciascuno da uno solo elemento di A (quindi $ |\mathcal{P}({A})| $ è almeno pari a n) più il sottoinsieme vuoto (e con questo abbiamo la disuguaglianza in senso stretto).
E con gli insiemi infiniti, notoriamente più "giocherelloni"? Si può fare: supponiamo infatti che A e $ \mathcal{P}({A}) $ siano equipotenti per qualche A avente infiniti elementi. Ciò comporta che esiste una funzione biiettiva da A a $ \mathcal{P}({A}) $, cioè una funzione che associa a ogni sottoinsieme $ S_i $ di A uno e un solo elemento $ a_i $ di A. Alcuni $ S_i $ (che chiameremo di qui in poi, con ardita innovazione lessicale, autocontenuti) conterranno l'elemento a loro associato $ a_i $ e altri no. Chiamiamo S' il sottoinsieme formato da tutti gli $ a_i $ tali che il sottoinsieme a loro associato non è autocontenuto. Qual'è l'elemento associato a S'? Di sicuro tale elemento non fa parte di S': se così fosse, S' sarebbe autocontenuto e conterrebbe quindi l'elemento associato a un sottoinsieme autocontenuto, in contrasto con definizione di S' data. Ma nemmeno può essere esterno ad S': in tal caso S' sarebbe non-autocontenuto e l'elemento ad esso associato dovrebbe far parte di S', in contrasto con quanto appena detto. Ne consegue che è impossibile associare a S' un elemento di A e quindi $ \mathcal{P}({A}) $ ha cardinalità superiore a n=|A|.
Lo so, non sono stato molto chiaro ma abbiate pazienza...
Salut
Ob
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös
Secondo me non è una causa ma una conseguenza!!!hydro ha scritto: Nessuna funzione $ \varphi $ del tipo richiesto può essere suriettiva, poichè se fosse suriettiva ed iniettiva allo stesso tempo sarebbe una biiezione, ma questo non è possibile poichè $ \mathbb{Z} $ e $ \wp (\mathbb{N}) $ non sono equipotenti. Infatti il primo è numerabile, il secondo ha la cardinalità del continuo.
Ma esiste una dimostrazione dell'equipotenza di P(N) e R?
[tex] wHy \matchal{ALBERT}_K ? [/tex]
Hemm...ma_go ha scritto:ehm.. funziona anche per l'insieme vuoto, ob: 2^0 = 1, che è abbastanza diverso da 0...
Non so perché ma mi ero convinto che l'insieme vuoto contenesse un solo elemento, cioè il vuoto (abbiate pietà,quella dimostrazione l'ho scritta decisamente troppo tardi per essere ancora capace di intendere e di volere).
Ciao
Ob
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös
Hmm i numeri tra 0 e 1 con la loro espressione binaria in cui si evitano sequenze infinite di soli 1 individuano ognuno una parte di N (quella dei numeri per cui all'n-esimo posto c'è 1 nel numero scelto). ad esempio 0,11101 è l'insieme {0,1,2,4}.albert_K ha scritto: Ma esiste una dimostrazione dell'equipotenza di P(N) e R?
Del resto, ogni parte di N individua una sequenza di zeri e uni che può essere interpretata come numero dopo la virgola in base 3 (per non creare problemi con infinite sfilze di 1). Quindi, avendo ottenuto due iniettive, Cantor-Bernstein ci da la tesi.
-
- Messaggi: 4
- Iscritto il: 08 gen 2008, 14:44
la dimostrazione di oblomov può funzionare ma bisogna dimostrare che tale insieme S', il sottoinsieme formato da tutti gli a(i) tali che il sottoinsieme a loro associato non è autocontenuto, cioè l'insieme che genera la contraddizione, sia ben definito, cioè che effettivamente esista e che sia unico!