Relazioni di Equivalenza

[fermat_O]

Ragazzi potete darmi qualche dritta su questo quesito??
Si considerino le relazioni R nell'insieme N(naturali) così definite:
aRb se e solo se mcd(a,b)>1
aRb se e solo se a+b è pari.
Devo dir se le relazioni sono di equivalenza, motivando la risposta.

Altro esercizio simile, data R nell'insieme N così definita:
aRb se e solo se a^2-b^2 ≣ 0 (mod3)
Dimostrare che R è di equivalenza, determinare classi d'equivalenza, ed elencare almeno tre elementi di ogni classe.

Vi ringrazierei tanto se potreste "illuminarmi", non ho idea di come procedere..

[Gatto89]

Per dimostrare che una relazione NON è di equivalenza, basta che trovi un esempio in cui una delle tre proprietà non viene soddisfatta.

Per il primo esercizio, penso puoi trovare facilmente un esempio in cui la transitività non vale

Per il secondo esercizio, in cui la relazione è effettivamente d'equivalenza, devi dimostrare le tre proprietà in generale.
Per esempio, per la riflessività, puoi dire che $\forall a in R, a + a = 2a$ è pari.

[Gatto89]

Per il terzo esercizio, per prima cosa ti consiglio di dare un'occhiata a cosa succede $(mod 3)$ ad $a^2$ quando:

$a \equiv 0 (mod 3)$

$a \equiv 1 (mod 3)$

$a \equiv 2 (mod 3)$

così ti semplifichi molto la vita.
Comunque il terzo è (leggermente) più complicato dei primi due quindi ti consiglio di farlo solo dopo che li hai fatti e capiti

[G.D.]

Per il terzo basta notare che $a^2 - b^2$ è $0$ se $a=b$ (ergo vale la rifelssività), poi $b^2 - a^2 = - (a^2 - b^2)$ e al resto "non interessa il segno" (quindi vale la simmetria), infine se $a^2 - b^2 equiv 0 (mod 3)$ e $b^2 - c^2 equiv 0 (mod 3)$ ti basta scrivere tutto secondo multipli del $3$ (ergo vale la transitività).

[fermat_O]

Per dimostrare che una relazione NON è di equivalenza, basta che trovi un esempio in cui una delle tre proprietà non viene soddisfatta.

Per il primo esercizio, penso puoi trovare facilmente un esempio in cui la transitività non vale

Per il secondo esercizio, in cui la relazione è effettivamente d'equivalenza, devi dimostrare le tre proprietà in generale.
Per esempio, per la riflessività, puoi dire che $\forall a in R, a + a = 2a$ è pari.

La simmetrica e la transitiva sono vere solo se i numeri sono entrambi(a,b) dispari o pari, ma come lo scrivo? E' giusto quello che ho detto?

[fermat_O]

Grazie, capito

[@melia]

È giusto.
Vediamo di dimostrarlo:
Se $aRb$ allora $a+b$ è pari, ma per la proprietà commutativa della somma $a+b=b+a$ quindi anche $b+a$ è pari perciò $bRa$, così abbiamo liquidato la proprietà simmetrica.
Per la transitiva
Se $aRb$ allora $a+b$ è pari posso scrivere $a+b=2k$, e $bRc$ allora $b+c$ è pari posso scrivere $b+c=2k$, quindi $a+c=(a+b)+(b+c)-2b=2k+2h-2b=2(k+h-b)$ che è pari, quindi $aRc$.

[fermat_O]

Ultima cosa ma la classe di equivalenza di aRb se e solo se a^2-b^2 ≣ 0 (mod3) non è 1??
Ossia [0]

[Gatto89]

Ultima cosa ma la classe di equivalenza di aRb se e solo se a^2-b^2 ≣ 0 (mod3) non è 1??
Ossia [0]

$1^2 -0^2 = 1$ non è multiplo di 3, quindi $1 \notin [0]$.

Per le classi d'equivalenza sfrutta il mio secondo post (alla fine dovresti trovartene due, prova a scriverle esplicitamente )

[Pakserrion]

ciao a tutti , io non ho capito ancora bene come si individuano le classi di equivalenza per esempio

la classe di equivalenza di aRb se e solo se a^2-b^2 (mod3)

individua 3 classi in quanto le classi che si possono trovare sono sempre 0,1,2...m-1 giusto?

perciò in questo caso con m=3 le classi sono

[0]=0,3,6,9 multipli di 3
[1]=1,4,7,10 ?
[2]=2,5,8,11 ?


non sono sicuro dell'ultima parte se qualcuno può darmi conferma

Riporto un esercizio ditemi se cosi è corretto ^^

Trovare le seguenti classi d’equivalenza: [0]R e [1]R e [3]R.
[1]=1,4,7,10
[2]=2,5,8,11
[3]=3,6,9,12 giusto?

Quante sono le classi d’equivalenza individuate da R?

sono 3 !