OliForum Matematico

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?

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.

Rilancio ovvio: provare che $ A $ e $ \mathcal{P}(A) $ non sono equipotenti per ogni insieme A.

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

ehm.. funziona anche per l'insieme vuoto, ob: 2^0 = 1, che è abbastanza diverso da 0...

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.

Secondo me non è una causa ma una conseguenza!!!

Ma esiste una dimostrazione dell'equipotenza di P(N) e R?

ma_go ha scritto:ehm.. funziona anche per l'insieme vuoto, ob: 2^0 = 1, che è abbastanza diverso da 0...

Hemm...
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

albert_K ha scritto: Ma esiste una dimostrazione dell'equipotenza di P(N) e R?

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}.
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.

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!