Insiemi finiti ed infiniti - (2)

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Jean-Paul
Messaggi: 36
Iscritto il: 16 lug 2007, 12:16

Insiemi finiti ed infiniti - (2)

Messaggio da Jean-Paul » 04 mag 2008, 14:15

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? :?

Avatar utente
hydro
Messaggi: 216
Iscritto il: 07 apr 2005, 17:11
Località: milano

Messaggio da hydro » 04 mag 2008, 17:03

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.

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 » 04 mag 2008, 17:24

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

Avatar utente
Oblomov
Messaggi: 284
Iscritto il: 23 ott 2005, 13:18
Località: Bologna

Messaggio da Oblomov » 05 mag 2008, 00:41

Va anche precisato che A non è vuoto :mrgreen:
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

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 05 mag 2008, 08:44

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

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 05 mag 2008, 23:28

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?
[tex] wHy \matchal{ALBERT}_K ? [/tex]

Avatar utente
Oblomov
Messaggi: 284
Iscritto il: 23 ott 2005, 13:18
Località: Bologna

Messaggio da Oblomov » 06 mag 2008, 00:00

ma_go ha scritto:ehm.. funziona anche per l'insieme vuoto, ob: 2^0 = 1, che è abbastanza diverso da 0...
Hemm... :oops:
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

EvaristeG
Site Admin
Messaggi: 4782
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 06 mag 2008, 01:31

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.

karletto0688
Messaggi: 4
Iscritto il: 08 gen 2008, 14:44

Messaggio da karletto0688 » 09 mag 2008, 00:05

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!

Rispondi