Relazione di equivalenza

[Neptune]

Salve a tutti,
sto ripassando le relazion di equivalenza, tra cui le relazioni "modulo R" e le relazioni sulle partizioni (insomma trova la classi di equivalenza e l'insieme quoziente).
Il punto è che avrei bisogno di esercizi da fare ma non ne riesco a trovare che facciano al caso mio.

Avete qualche suggerimento?

Sarebbe però utile che ci fossero le soluzioni, per essere sicuro del risultato.

Vi ringrazio in anticipo,
Neptune.

[WiZaRd]

Prova un poco qui.

[Neptune]

Sinceramente non ho trovato granchè riguardo a ciò che cercavo, cercavo più qualcosa di orientato alle relazioni di congruenza (come dicevo prima isniemi quozieenti eccetera).

[Neptune]

Credo sia inutile che apro un nuovo thread e quindi ne continuo a parlare qui, vorrei fare un piccolo reassunto concettuale delle classi di equivalenza, insieme quoziente e partizione per vedere se ho le idee chiare.

In pratica una classe di equivalenza non è altro che un'estensione delle relazioni di equivalenza, e questa classe non è altro che un sottoinsieme di elementi "tutti equivalenti" tra loro rispetto ad una determinata "relazione di equivalenza".

L'insieme quoziente invece è l'insieme di tutte le classi di equivalenza, di uno stesso insieme, che non sono in relazione di equivalenza tra loro? o no? questa non me la so spiegare bene. Ad esempio se ho la relazione di equivalenza che definisce l'insieme dei numeri pari. l'altra classe di equivalenza sarà l'insieme dei numeri dispari? o semplicemente non c'è perchè dovrebbe essere "una classe sempre di numeri pari non in relazione con la precedente classe" ?

Ed invece, le partizioni, non sono altro che un modo diverso di chiamare gli insiemi quozienti? e se si che senso hanno?

Si scusate ma su questo argomento ho un pò di confusione in testa.

[Martino]

Una relazione di equivalenza su un insieme \( \displaystyle {A} \) è una relazione su \( \displaystyle {A} \) che sia riflessiva, simmetrica e transitiva. Per esempio prendi come \( \displaystyle {A} \) l'insieme delle persone che ci sono nel mondo. La relazione definita da

"\( \displaystyle {x}\sim{y} \) se \( \displaystyle {x} \) e \( \displaystyle {y} \) hanno la stessa età"

è di equivalenza (puoi verificarlo facilmente). La classe di Fabio Fazio è l'insieme delle persone che hanno la stessa età di Fabio Fazio. Naturalmente due persone che sono nella stessa classe di Fabio Fazio sono in relazione tra loro (cioè hanno la stessa età). Se ci pensi, puoi identificare la classe di Fabio Fazio col numero che rappresenta la sua età, 45. 45 è il nome convenzionalmente dato alla classe di Fabio Fazio in questo momento.
In questo caso l'insieme quoziente è quindi identificabile all'insieme delle età che hanno le persone nel mondo.

Puoi vedere una relazione di equivalenza su \( \displaystyle {A} \) come una partizione dell'insieme \( \displaystyle {A} \), perché dall'insieme quoziente (che determina una partizione di \( \displaystyle {A} \)) puoi ricostruire la relazione dicendo che due elementi stanno in relazione se appartengono alla stessa classe (allo stesso insieme della partizione).

Per capire bene ti conviene fare esercizi. Ne trovi su internet, basta che scrivi "relazione di equivalenza esercizi" o simili su Google.

[Neptune]

Stavo provando a fare questo esercizio (anche se in rete non è che se ne trovino a bizzeffe, o forse non sono bravo io a cercare):

Verificare che la relazione binaria \( \displaystyle {R} \) su \( \displaystyle \mathbb{Z} \) definita da:
\( \displaystyle {x}{R}{y} \) se e solo se \( \displaystyle {x}-{y} \) è multiplo di 3
è una relazione di equivalenza;
Determinare tutti gli elementi della classe di \( \displaystyle {\left[{5}\right]} \)

Riflessività:

\( \displaystyle {x}{R}{y}\rightarrow{x}{R}{x} \) ovvero \( \displaystyle {3}{\mid}{x}-{x} \)
Ovvero \( \displaystyle {3}{\mid}{0} \) che è vero quindi riflessiva;

Simmetria:

\( \displaystyle {x}{R}{y}\rightarrow{y}{R}{x} \) ovvero \( \displaystyle {3}{\left|{x}-{y}\rightarrow{3}\right|}{y}-{x} \)

A questo punto, non si tratta della congruenza \( \displaystyle {x}\equiv{y}{\left(\text{mod}{3}\right)}\rightarrow{y}\equiv{x}{\left(\text{mod}{3}\right)} \) ? e non posso semplicemente portare i membri da una parte all'altra nella congruenza?

Transitività:

\( \displaystyle {x}{R}{{y}}^{{y}}{R}{z}\rightarrow{x}{R}{z} \) e questa è banale perchè diciamo che \( \displaystyle {3}{\mid}{x}-{y}+{y}-{z} \) ovvero \( \displaystyle {3}{\mid}{x}-{z} \)

Quindi abbiamo dimostrato che è di equivalenza anche se non sono sicurissimo sul come ho dimostrato la ismmetria.

Ora per indivdurare gli elementi individuati da \( \displaystyle {\left[{5}\right]}_{{r}} \) dico che:

\( \displaystyle {\left[{5}\right]}_{{r}}={\left\lbrace{y}\in\mathbb{Z}{\mid}{5}{R}{y}\right\rbrace} \) ovvero \( \displaystyle {\left\lbrace{y}\in\mathbb{Z}{\left|{3}\right|}{5}-{y}\right\rbrace} \)

A questo punto si denilinea facilmente la congruenza \( \displaystyle {5}\equiv{y}{\left(\text{mod}{3}\right)} \) ovvero \( \displaystyle {y}={2} \) e quindi posso dire che sono in relazione con 5 tutti gli elementi che, \( \displaystyle \text{mod}{3} \) danno resto 2?

E quindi qui, l'insieme quoziente come me lo ricavo? uno è la classe individuata da \( \displaystyle {5} \), e le altre?

[adaBTTLS]

per la simmetria, se \( \displaystyle {3}{\mid}{x}-{y} \) allora è anche \( \displaystyle {3}{\mid}-{\left({x}-{y}\right)}={y}-{x} \).
le classi di equivalenza sono le classi resto \( \displaystyle {\left[{0}\right]},{\left[{1}\right]},{\left[{2}\right]} \), \( \displaystyle {\left[{5}\right]}={\left[{2}\right]} \), \( \displaystyle {5} \) è solo un rappresentante della classe resto \( \displaystyle {\left[{2}\right]} \).
spero sia chiaro. ciao.

[Neptune]

per la simmetria, se \( \displaystyle {3}{\mid}{x}-{y} \) allora è anche \( \displaystyle {3}{\mid}-{\left({x}-{y}\right)}={y}-{x} \).
le classi di equivalenza sono le classi resto \( \displaystyle {\left[{0}\right]},{\left[{1}\right]},{\left[{2}\right]} \), \( \displaystyle {\left[{5}\right]}={\left[{2}\right]} \), \( \displaystyle {5} \) è solo un rappresentante della classe resto \( \displaystyle {\left[{2}\right]} \).
spero sia chiaro. ciao.

Giusto perchè il resto di una divione per \( \displaystyle {n} \) va da \( \displaystyle {0} \) a \( \displaystyle {n}-{1} \). Ovviamente 5 è nella classe di resto di \( \displaystyle {2} \).

Quindi possiamo dire che quelle sono tutte le classi di resto \( \displaystyle \text{mod}{3} \) e a seconda delle y che ci capitano svolgendo la congruenza vediamo in che classe di resto ricade, giusto?

Ma come formalizzo la classe di resto di 5, ovvero di 2? nel senso scrivo scemplicemente come ho scritto prima, ovvero t.c \( \displaystyle {3}{\mid}{5}-{y} \) ? posso anche scrivere t.c \( \displaystyle {y}\equiv{2}{\left(\text{mod}{3}\right)} \) ? o c'è una formula più specifica per dirlo?

Ovvero devo scrivere "tutti quei numeri che, divisi per 3 mi diano resto 2". Come posso scriverlo nella maniera più appropriata mediante formule matematiche?

[Neptune]

Pensandoci, alla domanda "individua gli elementi identificati da \( \displaystyle {\left[{5}\right]}_{{R}} \) posso scrivere:

\( \displaystyle {\left[{5}\right]}_{{R}}={\left\lbrace{y}\in\mathbb{Z}{\left|{3}\right|}{5}-{y}\right\rbrace}={\left[{y}\right]}_{{3}} \) ? mi sembra la maniera piu corta e "matematica" che si possa scrivere, o no?

[adaBTTLS]

mi pare corretto, a parte quell'\( \displaystyle {y} \) che immagino volesse essere un \( \displaystyle {2} \).