Insiemi numerabili

[tommy_2222]

Salve a tutti.
Come faccio a sapere se un insieme è numerabile o meno?
Come faccio a dimostrare che Q(insieme dei razionali) elevato a N(insieme dei naturali) non sia numerabile?

[_GaS_11]

Un insieme e' numerabile se puo' essere messo in corrispondenza biunivoca con i numeri naturali.
Ad esempio: sia '' $EsubRR$ ''.
$E={1,3/2,20}$.
Puo' essere messo in corrispondenza biunivoca con i numeri naturali: $A={1,2,3}$.
Sia: '' $(x)inE,ninA$ ''. Quindi si puo' imporre una funzione '' $f:ErightarrowA:f(x)=n$ ''.
Invece un insieme ha la potenza del numerabile ( e soltanto gli insiemi infiniti hanno tale potenza, ed e' la potenza infinita '' piu' piccola '' ) se e' equipotente ad '' $NN$ ''. Nell'esempio di prima l'insieme e' finito, e ha potenza '' $3$ ''.
'' $QQ$ '' elevato alla '' $n,ninNN$ '' possiede ancora la potenza del numerabile. Ma non so aiutarti su '' $QQ^(NN)$ '', in quanto non so nemmeno come e' stato definito.

[theras]

@gas.
$A^B$(o $"Hom(A,B)$ in certi testi)è,per definizione,
l'insieme di tutte e sole le possibili applicazioni tra $A$ e $B$..
@Tommy.
Se $QQ^(NN)$ fosse numerabile sarebbe,al più,numerabile ${0,1}^(NN)$;
ma quest'ultimo,grazie alla funzione caratteristica tra un sottoinsieme di $NN$ ed $NN$ stesso,ha la potenza dell'insieme delle parti di $NN$:
e l'insieme delle parti d'un numerabile
($NN$ lo è ..)
ha la potenza del continuo,che è invece maggiore di quella del numerabile!
Saluti dal web.

[_GaS_11]

Grazie per la dritta, Theras!
Una domanda: allora '' $RR$ '' e' l'insieme delle parti di '' $NN$ ''? Ma sul fatto che la potenza del continuo sia quella successiva alla numerabile ( da cui '' $RR$ '' sarebbe l'insieme delle parti di '' $NN$ '' ) non e' legata quella questione sull'ipotesi del continuo?
Dalle mie sintetiche conoscenze a riguardo so che Godel dimostro' la non falsita' di tale ipotesi, ma successivamente un altro logico matematico ne dimostro' la falsita'. E quindi ci si trovava di fronte ad un'affermazione indecidibile. Questo si collegava, tra l'altro, a precedenti ricerche di Godel in un certo campo.

[gio73]

"_GaS_":
... allora '' $RR$ '' e' l'insieme delle parti di '' $NN$ ''? Ma sul fatto che la potenza del continuo sia quella successiva alla numerabile ( da cui '' $RR$ '' sarebbe l'insieme delle parti di '' $NN$ '' ) non e' legata quella questione sull'ipotesi del continuo? :-

Non mi piace tanto come hai scritto, magari sbaglio io... ma il numero delle parti di $NN$ è uguale al numero degli elementi di $RR$, sarebbe meglio scrivere: l'insieme delle parti di $NN$ e l'insieme $RR$ sono equipotenti. Che ne dici?

[_GaS_11]

Assolutamente si', grazie. E' vero.

[Plepp]

Ciao Theras

"theras":@gas.
$A^B$(o $"Hom(A,B)$ in certi testi)è,per definizione,
l'insieme di tutte e sole le possibili applicazioni tra $A$ e $B$.

Semplicemente applicazioni? Non l'ho mai visto utilizzato in questo modo...ho sempre letto di $\text{Hom}(U,V)$ come dell'insieme degli omomorfismi tra $U$ e $V$.

[tommy_2222]

Grazie a tutti! Questo forum è utilissimo(e io che pensavo fosse deserto)

Ma quindi(come continua l'esercizio) se dovessi dare un esempio di insiemi infiniti A1, A2, A3 con A1
(Ricordando che la notazione A
Potrei porre A1=N(insieme dei naturali) e A2=R(insieme dei reali)
Perché se ho capito bene N
Ma poi come faccio a trovare un A3 tale che R

Cita

Segnala

[Plepp]

Puoi prendere $\mathcal{P}(RR)$, l'insieme delle parti di $RR$, o anche $RR^{NN}$.

[tommy_2222]

Ottimo! Pensandoci avrei potuto fare anche N

Cita

Segnala

[Paolo902]

"_GaS_":Un insieme e' numerabile se puo' essere messo in corrispondenza biunivoca con i numeri naturali.
Ad esempio: sia '' $EsubRR$ ''.
$E={1,3/2,20}$.
Puo' essere messo in corrispondenza biunivoca con i numeri naturali: $A={1,2,3}$.
Sia: '' $(x)inE,ninA$ ''. Quindi si puo' imporre una funzione '' $f:ErightarrowA:f(x)=n$ ''.

Attenzione perché questo è falso. L'insieme $E$ è finito, quindi non può essere messo in biiezione con l'insieme $NN$ dei numeri naturali (d'altra parte, la $f$ che definisci non è ben definita). Può certamente essere messo in biiezione con $A$ (forse era questo che intendevi?)

"Plepp":[quote="theras"]@gas.
$A^B$(o $"Hom(A,B)$ in certi testi)è,per definizione,
l'insieme di tutte e sole le possibili applicazioni tra $A$ e $B$.

Semplicemente applicazioni? Non l'ho mai visto utilizzato in questo modo...ho sempre letto di $\text{Hom}(U,V)$ come dell'insieme degli omomorfismi tra $U$ e $V$.[/quote]

E' una notazione standard, dal punto di vista categoriale. In particolare, di solito, nella categoria \( \mathbf{ Set}\) gli oggetti sono gli insiemi e i morfismi sono le usuali applicazioni fra insiemi. Quindi, da questo punto di vista, è una notazione assolutamente lecita.

[gio73]

"tommy_2222":Grazie a tutti! Questo forum è utilissimo(e io che pensavo fosse deserto)

Deserto? E' affollatissimo: puoi leggere il numero di utenti connessi in ogni momento in fondo alla pagina dell'indice.

[_GaS_11]

Attenzione perché questo è falso. L'insieme $E$ è finito, quindi non può essere messo in biiezione con l'insieme $NN$ dei numeri naturali (d'altra parte, la f che definisci non è ben definita). Può certamente essere messo in biiezione con $A$ (forse era questo che intendevi?)

Si', intendevo corrispondenza biunivoca con '' $A$ ''. Effettivamente era corretto scrivere: un insieme e' numerabile se puo' essere messo in corrispondenza biunivoca con un sottoinsieme dei numeri naturali.
Per la funzione penso che vada bene quanto segue ( per essere chiaro descrivo in termini pratici, ovvero in base al grafico ):
consideriamo '' $RR^2$ '' ( tanto '' $NN$ '' ne e' un sottoinsieme ): sulle ascisse metto i punti di '' $E$ '', sulle ordinate considero i punti di '' $A$ '' ( entrambi nel post precedente definiti ). In pratica, la funzione che si puo' scegliere deve avere la caratteristica di essere biunivoca almeno nell'intervallo che contiene i punti di '' $E$ '' ( monotona crescente in questo caso ). In breve basta una qualsiasi funzione che passi per i tre punti '' $(1,1),(3/2,1),(20,3)$ '', che possieda le caratteristiche precedentemente esposte.
Dovrebbe andare bene, o almeno penso.

[theras]

Per evitare possibili equivoci,preferisco evidenziare all'OP che Plepp si riferiva a $mathcal(P)(RR^n)$,
come d'altronde è corretto fare poichè il prodotto cartesiano d'un numero finito d'insiemi con la potenza del
continuo(numerabile),quale ovviamente è $RR$($NN$),ha esso stesso la potenza del continuo(del numerabile);
pertanto $RR^n$ ha,$AA n in NN$,la potenza del continuo
(leggenda vuole che questa scoperta costò in primis l'inimicizia ostile di Kronecker a Cantor,
a mio modo di vedere vero capostipite della Teoria degli insiemi poi,infelicemente,ribattezzata "ingenua" da Russell,
e nel seguito l'equilibrio psicofisico ):
[ot]Ed altresi,lo dico per completezza $|NN_0 times NN|=|NN| rArr |QQ^+_0|=|NN|=|QQ^-_0|$
(per l'evidente biunivocità tra i razionali non negativi e non positivi e le coppie di naturali a seconda
componente non nulla)
$rArr |QQ|=|QQ^+_0 uu QQ^-_0|=|NN|$
(dato che l'unione di due numerabili è essa stessa numerabile)[/ot]
dunque $mathcal(P)(RR^n)$ ha potenza maggiore di quella del continuo..
Ma il vero punto della questione è da dove nasca quest'ultima deduzione
(e lo dico pure a Gas,che nel parlare d'ipotesi del continuo e sue parentele con l'indecidibilità affronta,lo ripeto,
un campo rischioso a quest'altezza dei suoi studi,e sopratutto corre un rischio inutile nel contesto di questo quesito );
per comprenderlo occorre ricordare innanzitutto che,se $B$ è sottoinsieme di $A ne emptyset$,
denomineremo "funzione caratteristica" di $B$ in $A$ l'applicazione $f(a)={ ( 1" " "se "binB ),( 0" " "se "b !inB ):}:A to {0,1}$
(che,per chiarirci,coincide con la funzione identicamente uguale ad $1$ su $A$,
qualora $B$ fosse scelto giusto giusto coincidente $A$,e con la funzione identicamente nulla su $A$ se facessimo coincidere $B$ con quell'altro sottoinsieme banale di $A$ che è $emptyset$):
non è allora concettualmente difficilissimo osservare che,
indicata con $g_A(B)$ la funzione caratteristica d'un qualunque sottoinsieme $B$ del generico insieme $A ne emptyset$,
l'applicazione $phi(B)=g_A(B):mathcal(P)(A) to {0,1}^A$ è biunivoca..
Da ciò si dedurrà,per definizione,che $|mathcal(P)(A)|=|{0,1}^A|$;
essendo poi noto,se ben ricordo sempre grazie al grande George,che $|{0,1}^A|>|A|$,
se ne importa che $|mathcal(P)(A)|>|A|$(1):
ponendo poi nella (1) $A=RR$,e riesumando pure quanto hai correttamente dedotto sulla potenza di $mathcal(P)(NN)$,
se ne deduce che $|NN|<|mathcal(P)(NN)|=|RR|<|mathcal(P)(RR)|$
(e vedo meno pericoloso,per quanto corretto una volta verificatolo,
aggiungere che quest'ultimo insieme è equipotente a $mathcal(P)(RR^n)$,ma forse solo perchè mi ricorda esteticamente il modo in cui il Benedetto Prof. M. c'introdusse la teoria di ordinali transfiniti e cardinali infiniti ..)!
Saluti dal web.

[_GaS_11]

Ciao Theras!
E' vero che al momento gli studi sull'ipotesi del continuo sono troppo avanzati per me ( d'altronde non rientrano nemmeno nel mio percorso, ma a tempo debito, piu' avanti vorro' approfondire da solo ), ma era semplice curiosita'.
Grazie della esauriente risposta che hai dato.

[Paolo902]

"_GaS_":

Attenzione perché questo è falso. L'insieme $E$ è finito, quindi non può essere messo in biiezione con l'insieme $NN$ dei numeri naturali (d'altra parte, la f che definisci non è ben definita). Può certamente essere messo in biiezione con $A$ (forse era questo che intendevi?)

Si', intendevo corrispondenza biunivoca con '' $A$ ''. Effettivamente era corretto scrivere: un insieme e' numerabile se puo' essere messo in corrispondenza biunivoca con un sottoinsieme dei numeri naturali.

No, qui sbagli ed era proprio quello che temevo. Un insieme è numerabile se può essere messo in corrispondenza biunivoca con l'insieme dei numeri naturali, $NN$. Capisci ciò che intendo?

L'insieme \( A:=\{\text{cane}, \text{gatto}, \text{cuore} \}\) è certamente in biiezione con $\{1,2,3\} \subset NN$ ma $A$ è finito e $A$ è non numerabile.

Invece, ad esempio, l'insieme $P$ dei numeri pari è in biiezione con $NN$, perché $f: P \to NN$ definita nel modo ovvio (mandi un pari nella sua metà) è chiaramente una bigezione. Ne consegue che l'insieme dei numeri pari è numerabile.

Un po' più chiaro ora?

[_GaS_11]

Ok, allora, semplicemente, un insieme finito ha potenza finita.
Un problema di definizione, in quanto intendevo male '' numerabile ''. Per l'esattezza dovevo specificare che '' $E$ '' e' un sottoinsieme di un campo ordinato.
Il discorsino del mio post precedente sulle funzioni andava bene?
Ti ringrazio.

[Paolo902]

A dire il vero non l'ho capito molto bene, in particolare non ho capito bene che cosa c'entra $RR^2$. Forse sei troppo legato al concetto di funzione come il "grafico di una funzione $f:RR to RR$". Ricorda che il concetto di funzione si può definire tranquillamente in astratto, come terna ordinata $A,B,\Gamma$ con $A,B$ insiemi (non vuoti) e $\Gamma$ sottoinsieme di $A \times B$ con opportune proprietà.
Ad ogni modo, quello che hai scritto è certamente il grafico di una biiezione tra i due insiemi (se questo è ciò che ti perplime ).

[tommy_2222]

Intervengo solo per precisare una cosa, la vostra discussione è molto interessante e mi sta chiarendo parecchi punti:

- Un insieme A è numerabile se A è equinumeroso(ha la stessa cardinalità) all'insieme N dei numeri naturali, ovvero esiste una funzione biiettiva f: A->N

-Un insieme A è al più numerabile se A è finito oppure se A è numerabile

[_GaS_11]

Si', una nozione di funzione generica mi era chiara. Ho usato l' esempio concreto di '' $RR^2$ '' proprio per la sua praticita', per visualizzare meglio quello che volevo dire ( la funzione ).
Ti ringrazio.

[Paolo902]

@tommy: sì, certo quanto dici è corretto.

@_GaS_: prego, figurati.