Relazione di equivalenza e classe di equivalenza
Ciao ragazzi, ho svolto questo esercizio ma su questo argomento non mi sento molto preparato...conosco la teoria ma ho difficoltà a metterla in pratica quindi avrei bisogno che qualcuno dia un occhio rapido al mio esercizio:
$RR={(n, m) in ZZxZZ : 6|5n+m}$ devo dimostrare che è di equivalenza e calcolare la classe di equivalenza di 4
detto questo io ho fatto così, innanzi tutto ho "trasformato" la relazione in:
$5n -= -m (mod6)$ ; $5n+m=6h$
Riflessiva: $AA a in ZZ$ significa che $5a+a=6h$ e quindi $a=h$
Simmetrica: $AA (n,m) in ZZ$, $5m + n = 6h$ ed è vero
Transitiva: $AA x, y, z in ZZ, (x,y)inZZ ^^ (y,z) in ZZ => (x,z) in ZZ, EE h, k in ZZ$ tale che:
$5x + y = 6h$ e $5y+z = 6k$ allora $ 5(6h - 5x) + z = 6k => 30h - 25x + z = 6k => -25x + z = 6(k + h) => 5x - y = -6[(k+h)/5] $ e qui trovo il primo problema...basta dire questo??? Non credo viso che a occhio c'è qualcosa che non mi torna
per quanto riguarda la classe di equivalenza 4:
$6|20 + m$, giusto? quindi, dopo la trasformazione in congruenza lineare $20+m -= 0(mod6) --> m -= -20(mod6) --> m -= 2 (mod 6)$
corretto?
P.S: il punto sulla transitivià l'ho corretto... ho sommato $5x+y+5y+z = 6h +6k$ ottenendo $5x+z = 6(h+k-y)$ che è in Z
$RR={(n, m) in ZZxZZ : 6|5n+m}$ devo dimostrare che è di equivalenza e calcolare la classe di equivalenza di 4
detto questo io ho fatto così, innanzi tutto ho "trasformato" la relazione in:
$5n -= -m (mod6)$ ; $5n+m=6h$
Riflessiva: $AA a in ZZ$ significa che $5a+a=6h$ e quindi $a=h$
Simmetrica: $AA (n,m) in ZZ$, $5m + n = 6h$ ed è vero
Transitiva: $AA x, y, z in ZZ, (x,y)inZZ ^^ (y,z) in ZZ => (x,z) in ZZ, EE h, k in ZZ$ tale che:
$5x + y = 6h$ e $5y+z = 6k$ allora $ 5(6h - 5x) + z = 6k => 30h - 25x + z = 6k => -25x + z = 6(k + h) => 5x - y = -6[(k+h)/5] $ e qui trovo il primo problema...basta dire questo??? Non credo viso che a occhio c'è qualcosa che non mi torna
per quanto riguarda la classe di equivalenza 4:
$6|20 + m$, giusto? quindi, dopo la trasformazione in congruenza lineare $20+m -= 0(mod6) --> m -= -20(mod6) --> m -= 2 (mod 6)$
corretto?
P.S: il punto sulla transitivià l'ho corretto... ho sommato $5x+y+5y+z = 6h +6k$ ottenendo $5x+z = 6(h+k-y)$ che è in Z
Risposte
Andiamo con ordine: Non hai dimostrato la simmetrica.
Vale la proprietà simmetrica se $AA m,n in ZZ$, $(m,n) in R => (n,m) in R$
Ovvero se $AA m,n in ZZ$, $EE h in ZZ : 5m+n=6h => EE k in ZZ : 5n+m=6k$ Pertanto:
Ipotesi: $EE h in ZZ$ tale che $5m+n=6h$
Tesi: $EE k in ZZ$ tale che $5n+m=6k$
Riesci a dimostrarlo?
Vale la proprietà simmetrica se $AA m,n in ZZ$, $(m,n) in R => (n,m) in R$
Ovvero se $AA m,n in ZZ$, $EE h in ZZ : 5m+n=6h => EE k in ZZ : 5n+m=6k$ Pertanto:
Ipotesi: $EE h in ZZ$ tale che $5m+n=6h$
Tesi: $EE k in ZZ$ tale che $5n+m=6k$
Riesci a dimostrarlo?
Per quanto riguarda la transitiva e la classe di equivalenza di $4$, invece, tutto ok 
"Gi8":
Andiamo con ordine: Non hai dimostrato la simmetrica.
Vale la proprietà simmetrica se $AA m,n in ZZ$, $(m,n) in R => (n,m) in R$
Ovvero se $AA m,n in ZZ$, $EE h in ZZ : 5m+n=6h => EE k in ZZ : 5n+m=6k$ Pertanto:
Ipotesi: $EE h in ZZ$ tale che $5m+n=6h$
Tesi: $EE k in ZZ$ tale che $5n+m=6k$
Riesci a dimostrarlo?
se sommo l'ipotesi e la tesi ottengo n = k + h - m ed è $in Z$...corretto?
ora però ho un altro problema con un esercizio dello stesso tipo solo che usa le potenze...vediamo se mi è chiaro tutto
$a = 2^h b$
riflessiva: $a = 2^h a$ ed è vero per ogni a a patto che h sia 0
simm: $b=2^h a => a=2^k b$ cioè $2^(h+k) = 1$
trans: $x = 2^h y EE y = 2^k z $ cioè$x=2^h 2^k z = 2 ^(h+k)z$
ora, come passo alla congruenza per poi calcolarmi la classe di equivalenza? non mi era mai capitata na roba simile
C'è un piccolo errore anche nella classe di equivalenza a cui appartiene 4
Nell'ultimo passaggio, non è $m-=2(mod 6)$, ma $m-=4(mod6)$
Torniamo alla simmetrica:
Ehm, no. Non puoi sommare l'ipotesi e la tesi. Per farlo dovresti avere che entrambe sono vere.
L'ipotesi è vera, ma la tesi no (o, meglio, ancora non lo sai... lo devi dimostrare)
Devi partire scrivendo $5n+m=...$, poi effettuare degli artifici (sfruttando ovviamente l'ipotesi)
e arrivare ad ottenere qualcosa che è multiplo di $6$
"Max861126":
per quanto riguarda la classe di equivalenza 4:
$6|20 + m$, giusto? quindi, dopo la trasformazione in congruenza lineare $20+m -= 0(mod6) --> m -= -20(mod6) --> m -= 2 (mod 6)$
Nell'ultimo passaggio, non è $m-=2(mod 6)$, ma $m-=4(mod6)$
Torniamo alla simmetrica:
"Max861126":
se sommo l'ipotesi e la tesi ottengo n = k + h - m ed è $in Z$...corretto?
Ehm, no. Non puoi sommare l'ipotesi e la tesi. Per farlo dovresti avere che entrambe sono vere.
L'ipotesi è vera, ma la tesi no (o, meglio, ancora non lo sai... lo devi dimostrare)
Devi partire scrivendo $5n+m=...$, poi effettuare degli artifici (sfruttando ovviamente l'ipotesi)
e arrivare ad ottenere qualcosa che è multiplo di $6$
"Gi8":
C'è un piccolo errore anche nella classe di equivalenza a cui appartiene 4
[quote="Max861126"]per quanto riguarda la classe di equivalenza 4:
$6|20 + m$, giusto? quindi, dopo la trasformazione in congruenza lineare $20+m -= 0(mod6) --> m -= -20(mod6) --> m -= 2 (mod 6)$
Nell'ultimo passaggio, non è $m-=2(mod 6)$, ma $m-=4(mod6)$
Torniamo alla simmetrica:
"Max861126":
se sommo l'ipotesi e la tesi ottengo n = k + h - m ed è $in Z$...corretto?
Ehm, no. Non puoi sommare l'ipotesi e la tesi. Per farlo dovresti avere che entrambe sono vere.
L'ipotesi è vera, ma la tesi no (o, meglio, ancora non lo sai... lo devi dimostrare)
Devi partire scrivendo $5n+m=...$, poi effettuare degli artifici (sfruttando ovviamente l'ipotesi)
e arrivare ad ottenere qualcosa che è multiplo di $6$[/quote]
per la congruenza hai ragione, era un -2 che è congruo a 4 ^__^...ma per la dimostrazione brancolo nel buio....aiutino secondario?
Ipotesi: $EE h in ZZ$ tale che $5m+n=6h$
Tesi: $EE k in ZZ$ tale che $5n+m=6k$
$5n+m=(6n-n)+(6m-5m)= 6n+6m-(5m+n)=6n+6m-6h=6(n+m-h)$
Quindi $EE k in Z$ tale che $5n+m=6k$, e cioè $k=n+m-h$
Tesi: $EE k in ZZ$ tale che $5n+m=6k$
$5n+m=(6n-n)+(6m-5m)= 6n+6m-(5m+n)=6n+6m-6h=6(n+m-h)$
Quindi $EE k in Z$ tale che $5n+m=6k$, e cioè $k=n+m-h$
Ok, chiarissimo, quindi in generale devo rendere il secondo membro dell'ugualgianza in un formato tale che mi permetta la sostituzione con il secondo membro dell'ipotesi.... ma nell'altro esercizio che ho messo, posso sostituire direttamente la b con l'equazione dell'ipotesi? in questo modo ottengo $2^(h+k) = 1$ quindi esiste un k tale che $h+k=0$ Corretto?
e come passo alla congruenza?
e come passo alla congruenza?
"Max861126":
Ok, chiarissimo, quindi in generale devo rendere il secondo membro dell'ugualgianza in un formato tale che mi permetta la sostituzione con il secondo membro dell'ipotesi.... ma nell'altro esercizio che ho messo, posso sostituire direttamente la b con l'equazione dell'ipotesi? in questo modo ottengo $2^(h+k) = 1$ quindi esiste un k tale che $h+k=0$ Corretto?
Correttissmo! Puoi anche essere ancora più preciso dicendo quanto vale $k$
$h+k=0 => k= -h$
Dunque basta scegliere $k= -h$
"Max861126":
come passo alla congruenza?
Prova a rispondere a questo: quali sono gli elementi $x in ZZ$ che sono in relazione con $6$?
e con $5$? e con $2$?
in che senso scusa... in questo esercizio 5n+m = 6h passare alla congruenza è banale dato che 5n+m devono essere multipli di 6...
nell'altro esempio $a = 2^h b$ segue che $a/b = 2^h$ quindi tutti i numeri a/b = 1, 2, 4, 8, 16, ... intendi questo?
nell'altro esempio $a = 2^h b$ segue che $a/b = 2^h$ quindi tutti i numeri a/b = 1, 2, 4, 8, 16, ... intendi questo?
No, non intendevo questo. Mi spiego meglio.
Ora che hai dimostrato che la relazione è di equivalenza, l'obiettivo è trovare le classi di equivalenza (non necessariamente sfruttando le congruenze).
Piccola parentesi: Sai cosa sono le classi di equivalenza di una relazione di equivalenza? Se non lo sai chiedi pure.
Torniamo un attimo all'esercizio precedente:
Lì è stato tutto sommato semplice trovarle perchè, sfruttando le congruenze modulo $6$, hai potuto affermare che
$(4,x) in R <=> x -=4(mod 6)$.
Pertanto qual è la classe di equivalenza a cui appartiene 4? è la seguente:
$[4]_R={...,-8,-2,4,10,16,....}=[4]_6$,
(in generale, $AA a in ZZ, [a]_6:={x in ZZ | x-=a(mod 6)}$
Le classi di equivalenza di $R$ sono pertanto $[0]_6, [1]_6,[2]_6,[3]_6,[4]_6,[5]_6$
Anche nel nuovo esercizio bisogna trovare le classi di equivalenza.
Secondo me, però, non si può seguire la strada della congruenza modulo qualche numero.
Bisogna trovare le classi in qualche altro modo.
Per questo ti ho chiesto
Ad esempio, prendiamo $6$
$(6,x) in R <=> x=?$
$x=3,6,12,24,48,96,...$
ok?
Prova con $5$ e con $2$
Ora che hai dimostrato che la relazione è di equivalenza, l'obiettivo è trovare le classi di equivalenza (non necessariamente sfruttando le congruenze).
Piccola parentesi: Sai cosa sono le classi di equivalenza di una relazione di equivalenza? Se non lo sai chiedi pure.
Torniamo un attimo all'esercizio precedente:
Lì è stato tutto sommato semplice trovarle perchè, sfruttando le congruenze modulo $6$, hai potuto affermare che
$(4,x) in R <=> x -=4(mod 6)$.
Pertanto qual è la classe di equivalenza a cui appartiene 4? è la seguente:
$[4]_R={...,-8,-2,4,10,16,....}=[4]_6$,
(in generale, $AA a in ZZ, [a]_6:={x in ZZ | x-=a(mod 6)}$
Le classi di equivalenza di $R$ sono pertanto $[0]_6, [1]_6,[2]_6,[3]_6,[4]_6,[5]_6$
Anche nel nuovo esercizio bisogna trovare le classi di equivalenza.
Secondo me, però, non si può seguire la strada della congruenza modulo qualche numero.
Bisogna trovare le classi in qualche altro modo.
Per questo ti ho chiesto
"Gi8":
quali sono gli elementi $x in ZZ$ che sono in relazione con $6$? e con $5$? e con $2$?
Ad esempio, prendiamo $6$
$(6,x) in R <=> x=?$
$x=3,6,12,24,48,96,...$
ok?
Prova con $5$ e con $2$
Allora, ragiono un po'....
le classi di equivalenza come definizione presente nei miei appunti ho che:
$AA x in A, [x]_RR = {y in A | (x, y) in RR}$, quindi ciò che hai scritto nel riprendere l'esempio precedente è chiarissimo....il problema nasce per l'altro esercizio...non mi è chiaro da dove prendi quei valori...se la traccia è $a=2^h b$, cosa c'entra la x? ho pensato che intendessi $x=2^h y$, giusto?
quindi $x = 2^h * 6$ cioè $x = {1*6, 2*6, 4*6, 8*6, 16*6, .....}$
ora, considerando che c'è $2^h$ come fai a trovare il valore 3? sarà una stupidata grandissima ma io proprio non riesco a capire questo esercizio^__^
le classi di equivalenza come definizione presente nei miei appunti ho che:
$AA x in A, [x]_RR = {y in A | (x, y) in RR}$, quindi ciò che hai scritto nel riprendere l'esempio precedente è chiarissimo....il problema nasce per l'altro esercizio...non mi è chiaro da dove prendi quei valori...se la traccia è $a=2^h b$, cosa c'entra la x? ho pensato che intendessi $x=2^h y$, giusto?
quindi $x = 2^h * 6$ cioè $x = {1*6, 2*6, 4*6, 8*6, 16*6, .....}$
ora, considerando che c'è $2^h$ come fai a trovare il valore 3? sarà una stupidata grandissima ma io proprio non riesco a capire questo esercizio^__^
Se $h in ZZ$, allora puoi assegnare anche $h=-1$ da cui $2^(-1)*6=1/2*6=3$
Per caso $h in NN$? Se sì, allora $3$ va escluso
Per caso $h in NN$? Se sì, allora $3$ va escluso
hai ragione! che stupido^__^ in ogni caso grazie!!!!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo