Relazioni di equivalenza e partizioni
Ciao a tutti.
Mi servirebbe sapere come si può dimostrare questo teorema:
Ogni relazione d'equivalenza determina una partizione e viceversa
Chiaramente so cosa sono una relazione d'equivalenza e una partizione, ma non non riesco a capire come poter dimostrare questa proposizione.
Ringrazio in anticipatamente chi avrà la pazienza e la voglia di rispondermi e aiutarmi
Mi servirebbe sapere come si può dimostrare questo teorema:
Ogni relazione d'equivalenza determina una partizione e viceversa
Chiaramente so cosa sono una relazione d'equivalenza e una partizione, ma non non riesco a capire come poter dimostrare questa proposizione.
Ringrazio in anticipatamente chi avrà la pazienza e la voglia di rispondermi e aiutarmi
Risposte
Sia $A$ un insieme non vuoto ed $R$ una relazione di equivalenza in $A$. Mostriamo che l'insieme $A/R$ è una partizione di $A$.
Poichè $R$ è riflessiva ogni classe di equivalenza contiene almeno il suo rappresentante quindi $\bigcup_{x \in A} [x]_R = A$
Mostriamo che date due classi di equivalenza $[x]$ e $[y]$ queste coincidono oppure sono disgiunte. Infatti se $z \in [x] \cap [y]$ allora $zRx$ e $zRy$ e quindi per la proprietà transitiva $xRy$ ovvero $[x]=[y]$
Pertanto $A/R$ è un insieme di parti di $A$ a due a due disgiunte la cui unione è $A$, in altre parole una partizione.
Viceversa sia $P$ una partizione di $A$. Definiamo in $A$ la relazione $xRy$ se e solo se $x$ e $y$ appartengono allo stesso elemento di $P$. Ovviamente $R$ è riflessiva e simmetrica. Se $x$ appartiene allo stesso insieme di $y$ e $y$ appartiene allo stesso insieme di $z$, ricordando che $y$ appartiene ad un unico elemento di $P$ (perchè $P$ è una partizione), concludiamo che $x$ e $z$ appartengono allo stesso elemento di $P$, cioè $xRz$. Pertanto $R$ è transitiva ed è una relazione di equivalenza.
Poichè $R$ è riflessiva ogni classe di equivalenza contiene almeno il suo rappresentante quindi $\bigcup_{x \in A} [x]_R = A$
Mostriamo che date due classi di equivalenza $[x]$ e $[y]$ queste coincidono oppure sono disgiunte. Infatti se $z \in [x] \cap [y]$ allora $zRx$ e $zRy$ e quindi per la proprietà transitiva $xRy$ ovvero $[x]=[y]$
Pertanto $A/R$ è un insieme di parti di $A$ a due a due disgiunte la cui unione è $A$, in altre parole una partizione.
Viceversa sia $P$ una partizione di $A$. Definiamo in $A$ la relazione $xRy$ se e solo se $x$ e $y$ appartengono allo stesso elemento di $P$. Ovviamente $R$ è riflessiva e simmetrica. Se $x$ appartiene allo stesso insieme di $y$ e $y$ appartiene allo stesso insieme di $z$, ricordando che $y$ appartiene ad un unico elemento di $P$ (perchè $P$ è una partizione), concludiamo che $x$ e $z$ appartengono allo stesso elemento di $P$, cioè $xRz$. Pertanto $R$ è transitiva ed è una relazione di equivalenza.
Innanzitutto ti ringrazio per la risposta.
Volevo se possibile chiederti delle delucidazioni ulteriori: ho capito il ragionamento che da una partizione porta a determinare una relazione di equivalenza.
Viceversa invece, ovvero nella prima parte, vi è una notazione che non conosco: $\bigcup_{x \in A} [x]_R = A$
E' per caso l'unione delle classi di equivalenza che danno l'insieme A di partenza?
Inoltre non ho compreso questa parte:
Ti ringrazio ancora, sperando potrai togliermi anche questi dubbi.
Volevo se possibile chiederti delle delucidazioni ulteriori: ho capito il ragionamento che da una partizione porta a determinare una relazione di equivalenza.
Viceversa invece, ovvero nella prima parte, vi è una notazione che non conosco: $\bigcup_{x \in A} [x]_R = A$
E' per caso l'unione delle classi di equivalenza che danno l'insieme A di partenza?
Inoltre non ho compreso questa parte:
"perplesso":
Mostriamo che date due classi di equivalenza $[x]$ e $[y]$ queste coincidono oppure sono disgiunte. Infatti se $z \in [x] \cap [y]$ allora $zRx$ e $zRy$ e quindi per la proprietà transitiva $xRy$ ovvero $[x]=[y]$
Ti ringrazio ancora, sperando potrai togliermi anche questi dubbi.
Per la prima domanda è esatto quella notazione indica l'unione di tutte le classi di equivalenza dell'insieme $A$.
Per la seconda domanda hai che due classi di equivalenza o sono uguali o sono disgiunte, perchè in caso contrario (cioè non fossero disgiunte) avrebbero almeno un elemento in comune:
$z in [x] nn [y] <=> z in [x] ^^ z in [y] <=> zRx ^^ zRy => xRy <=> [x]=[y]$ (per la proprietà transitiva delle relazioni).
Chiaro?
Per la seconda domanda hai che due classi di equivalenza o sono uguali o sono disgiunte, perchè in caso contrario (cioè non fossero disgiunte) avrebbero almeno un elemento in comune:
$z in [x] nn [y] <=> z in [x] ^^ z in [y] <=> zRx ^^ zRy => xRy <=> [x]=[y]$ (per la proprietà transitiva delle relazioni).
Chiaro?
"GundamRX91":
Per la prima domanda è esatto quella notazione indica l'unione di tutte le classi di equivalenza dell'insieme $A$.
Per la seconda domanda hai che due classi di equivalenza o sono uguali o sono disgiunte, perchè in caso contrario (cioè non fossero disgiunte) avrebbero almeno un elemento in comune:
$z in [x] nn [y] <=> z in [x] ^^ z in [y] <=> zRx ^^ zRy => xRy <=> [x]=[y]$ (per la proprietà transitiva delle relazioni).
Chiaro?
Si, ti ringrazio molto.
Ho letto il regolamento e so che il topic dovrebbe non trattare di argomenti diversi da quelli del titolo, ma ho un paio di dubbi riguardanti altri temi e li vorrei scrivere qui per non intasare la pagina con miei molteplici topic.
Se sbaglio chiedo scusa.
Un primo dubbio riguarda le congruenze lineari. Io ho questa congruenza: $108x -= 12 (mod 42)$
Ora, io so che la congruenza ha soluzioni se, per $ax -= b (mod n)$, ho che l'$ MCD(a,n)=d$ divide $b$; ed il numero di soluzioni sono appunto uguali a $d$.
Nell'esercizio, quindi, si hanno 6 soluzioni perchè l'$ MCD(108,42)=6$ divide $12$.
Devo percio determinarle, quindi imposto l'equazione diofantea in questa maniera: $108x + 42y = 12$, dividendo poi tutti i membri per l'$MCD$ ovvero $6$.
Trovandomi quindi: $18x + 7y = 2$. Come devo poi procedere per trovare l'$x$ particolare che mi serve poi per trovare tutte e 6 le soluzioni con la formula: $x + n/d *t$?
$108x-=12 _(mod 42)$ è quivalente, per il motivo che hai indicato, a $18x-=2_(mod 7)$ che significa che $7|18x-2$.
Però bisogna prima "semplificare" l'equazione congruenziale calcolando l'inverso moltiplicativo della $x$, quindi si ha che:
$18x-=1_(mod 7)$ (sai perché?), $7|18x-1 => EE y in ZZ$ tale che $18x-1=7y$ e $18x-7y=1$ che ha soluzione per $x=2$ e $y=5$.
A questo punto puoi semplificare la tua equazione moltiplicando il tutto per $2$, e ottieni: $x-=4_(mod 7)$, da cui:
$7|x-4 => EE k in ZZ$ tale che $x-4=7k$ e infine $x=4+7k$ che sono le soluzione all'equazione.
Però bisogna prima "semplificare" l'equazione congruenziale calcolando l'inverso moltiplicativo della $x$, quindi si ha che:
$18x-=1_(mod 7)$ (sai perché?), $7|18x-1 => EE y in ZZ$ tale che $18x-1=7y$ e $18x-7y=1$ che ha soluzione per $x=2$ e $y=5$.
A questo punto puoi semplificare la tua equazione moltiplicando il tutto per $2$, e ottieni: $x-=4_(mod 7)$, da cui:
$7|x-4 => EE k in ZZ$ tale che $x-4=7k$ e infine $x=4+7k$ che sono le soluzione all'equazione.
Ti ringrazio veramente moltissimo per la tua pazienza.
Per quanto riguarda la domanda che hai fatto tra parentesi, non so il perchè. Si tratta dell'equazione particolare?
Quando dici di moltiplicare per due la mia equazione per semplificarla, a che equazione ti riferisci? Lì mi sono perso.
Purtroppo ho ancora un grosso problema con le permutazioni che fatico a comprendere, ma creerò un altro topic più tardi per non fare troppo disordine.
Grazie ancora.
Per quanto riguarda la domanda che hai fatto tra parentesi, non so il perchè. Si tratta dell'equazione particolare?
Quando dici di moltiplicare per due la mia equazione per semplificarla, a che equazione ti riferisci? Lì mi sono perso.
Purtroppo ho ancora un grosso problema con le permutazioni che fatico a comprendere, ma creerò un altro topic più tardi per non fare troppo disordine.
Grazie ancora.
Uhmmm non si tratta di permutazioni ma della teoria che c'è dietro l'anello delle classi dei resti $(ZZ_n,+,*)$.
Per la domanda che ti ho fatto è legata al fatto che gli elementi di $ZZ_n$ invertibili sono congrui a $1$ modulo $n$, mentre per quanto riguarda la domanda sulla moltiplicazione mi riferisco all'equazione $18x-=2_(mod 7)$.
Per la domanda che ti ho fatto è legata al fatto che gli elementi di $ZZ_n$ invertibili sono congrui a $1$ modulo $n$, mentre per quanto riguarda la domanda sulla moltiplicazione mi riferisco all'equazione $18x-=2_(mod 7)$.
"GundamRX91":
Uhmmm non si tratta di permutazioni ma della teoria che c'è dietro l'anello delle classi dei resti $(ZZ_n,+,*)$.
Per la domanda che ti ho fatto è legata al fatto che gli elementi di $ZZ_n$ invertibili sono congrui a $1$ modulo $n$, mentre per quanto riguarda la domanda sulla moltiplicazione mi riferisco all'equazione $18x-=2_(mod 7)$.
No no lo so che questo non centra nulla con le permutazioni.
Con l'ultima frase (quella, per intenderci, sulle permutazioni appunto) mi riferivo ad un altro problema, completamente slegato da questo.
Rileggendo il mio messaggio ora, mi rendo conto che ho esposto male e il tuo fraintendimento è più che legittimo.
Ok, ok, spero comunque di essere stato chiaro, altrimenti chiedi pure 
ahahahah!! Avevo risposto prima che tu modificassi la tua ultima risposta
Comunque tranquillo non c'è nessun problema 
ahahahah!! Avevo risposto prima che tu modificassi la tua ultima risposta
Comunque tranquillo non c'è nessun problema
Sei stato chiarissimo
Avrei un altro quesito però...
Scusami so che sto approfittando della tua pazienza, il fatto è che tra qualche giorno ho l'orale di matematica discreta e avendo fatto lo scritto mesi fa (purtroppo cause di forza maggiore ovvero lavoro non ho potuto poi fare subito l'orale) mi sono scordato diverse cose e adesso ho qualche dubbio di troppo.
L'orale consta appunto, oltre che in domande di teoria su cui non ho problemi, nella correzione dello scritto (in cui ero anche andato bene, 27/30) ed è per questo che gli esercizi su cui ho dubbi sono così diversificati.
Tornando al problema, ho questa applicazione lineare $f : R^3 → R^3$ (non so come scriverla in verticale come andrebbe scritta): \[f:(x,y,z)\mapsto (x,-4x +y, 3x + y)\qquad \]
Mi si chiede di calcolare la dimensione di $Im f$ e di $Ker f$ e dire se l’applicazione è diagonalizzabile.
Ora, io l'unica cosa che ricordo è che la matrice associata è diagonalizzabile se la molteplicità algebrica è uguale a quella geometrica.
Quindi procedo creando la matrice associata:
\[A=\begin{pmatrix}
1&0&0\\
-4&0&1\\
3&1&0
\end{pmatrix}
\]
e successivamente sottraggo ad essa la $λI$, ottenendo:
\[A=\begin{pmatrix}
1-λ&0&0\\
-4&-λ&1\\
3&1&-λ
\end{pmatrix}
\]
Dovrei quindi calcolare il determinante per poi vedere la molteplicità algebrica e confrontarla con la molteplicità geometrica. Ma sicuramente sbaglio qualcosa nel calcolo del determinante, perchè mi vien fuori una roba strana che non saprei come raccapezzarmici.
In teoria dovrei bloccare la prima riga (perchè quella con più zeri) e moltiplicare $1-λ$ per il determinante della matrice quadrata formata dal secondo e terzo elemento della seconda e terza riga, giusto?
E già qui ho dei problemi; come continuare?
Inoltre chiede di trovare l'immagine e il ker (nucleo) dell'applicazione: come fare? Non ce lo ha mai spiegato e avendo solo appunti e nessun libro di testo non so nemmeno da dove si cominci. Oltre che non sapere bene cosa effettivamente siano immagine e nucleo.
Avrei un altro quesito però...
Scusami so che sto approfittando della tua pazienza, il fatto è che tra qualche giorno ho l'orale di matematica discreta e avendo fatto lo scritto mesi fa (purtroppo cause di forza maggiore ovvero lavoro non ho potuto poi fare subito l'orale) mi sono scordato diverse cose e adesso ho qualche dubbio di troppo.
L'orale consta appunto, oltre che in domande di teoria su cui non ho problemi, nella correzione dello scritto (in cui ero anche andato bene, 27/30) ed è per questo che gli esercizi su cui ho dubbi sono così diversificati.
Tornando al problema, ho questa applicazione lineare $f : R^3 → R^3$ (non so come scriverla in verticale come andrebbe scritta): \[f:(x,y,z)\mapsto (x,-4x +y, 3x + y)\qquad \]
Mi si chiede di calcolare la dimensione di $Im f$ e di $Ker f$ e dire se l’applicazione è diagonalizzabile.
Ora, io l'unica cosa che ricordo è che la matrice associata è diagonalizzabile se la molteplicità algebrica è uguale a quella geometrica.
Quindi procedo creando la matrice associata:
\[A=\begin{pmatrix}
1&0&0\\
-4&0&1\\
3&1&0
\end{pmatrix}
\]
e successivamente sottraggo ad essa la $λI$, ottenendo:
\[A=\begin{pmatrix}
1-λ&0&0\\
-4&-λ&1\\
3&1&-λ
\end{pmatrix}
\]
Dovrei quindi calcolare il determinante per poi vedere la molteplicità algebrica e confrontarla con la molteplicità geometrica. Ma sicuramente sbaglio qualcosa nel calcolo del determinante, perchè mi vien fuori una roba strana che non saprei come raccapezzarmici.
In teoria dovrei bloccare la prima riga (perchè quella con più zeri) e moltiplicare $1-λ$ per il determinante della matrice quadrata formata dal secondo e terzo elemento della seconda e terza riga, giusto?
E già qui ho dei problemi; come continuare?
Inoltre chiede di trovare l'immagine e il ker (nucleo) dell'applicazione: come fare? Non ce lo ha mai spiegato e avendo solo appunti e nessun libro di testo non so nemmeno da dove si cominci. Oltre che non sapere bene cosa effettivamente siano immagine e nucleo.
[xdom="Martino"]Giobbo, non è concesso andare fuori tema in questo modo. Per favore apri un nuovo argomento nella sezione apposita ("Geometria e Algebra Lineare"). Grazie.[/xdom]
"Martino":
[xdom="Martino"]Giobbo, non è concesso andare fuori tema in questo modo. Per favore apri un nuovo argomento nella sezione apposita ("Geometria e Algebra Lineare"). Grazie.[/xdom]
Ok, mi scuso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo