Trovare le classi di equivalenza di una relazione

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Trovare le classi di equivalenza di una relazione #64832

avt
Toro
Punto
Ciao! Ecco un esercizio in cui devo determinare alcune classi di equivalenza per una relazione data. So che cos'è teoricamente una classe di equivalenza ma non so determinarle.

Ad esempio se ho come insieme

V := \{3h + 1\ |\ h \in N_0\}

e come relazione d'equivalenza

3h + 1\ R\ 3k + 1\ \Leftrightarrow\ |h - k| \in 2N_0

devo determinare le classi  [1], [4], [7], [10].


Allora devo trovare il sottoinsieme di V costituito da tutti e soli gli elementi di V che sono in relazione con x. La traccia mi dice di trovare [1], quindi devo determinare la classe di equivalenza dell'elemento 1.

Ponendo h = 0 mi trovo 3(0) + 1 = 1 .

Il libro non mi dà il risultato e quindi solo voi mi potete dare una mano. Grazie mille.
 
 

Trovare le classi di equivalenza di una relazione #64907

avt
Galois
Amministratore
Ciao Toro, iniziamo!

Premetto che nel corso nella risposta intenderò \mathbb{N}_0 = \mathbb{N} \cup \{0\}

Cos'è una classe d'equivalenza?

Definizione: data una relazione d'equivalenza \mathfrak{R} definita in un insieme A, si chiama classe di equivalenza di un elemento a \in A modulo \mathfrak{R} e si indica con [a]_{\mathfrak{R}} il sottoinsieme di A così definito:

[a]_{\mathfrak{R}} = \{x \in A \ | \ x \ \mathfrak{R} \ a\}

Bene! Noterai che nella definizione ho messo in grassetto alcune parti. Sono gli elementi che ci servono per poter parlare di classi di equivalenza.

La prima cosa da fare è quindi assicurarci di avere tali "ingredienti".

Primo ingrediente: insieme da cui partire. Lo abbiamo? Sì, è l'insieme

V=\{3h+1 \ | \ h \in \mathbb{N}_0 \}

Secondo ingrediente: ci serve una relazione di equivalenza tra gli elementi di V. Noi una relazione la abbiamo ed è la seguente:

Dati: 3h+1 \ \mbox{e} \ 3k+1 appartenenti a V:

(3h+1) \ \mathfrak{R} \ (3k+1) \ :\iff \ |h-k| \in 2\mathbb{N}_0

Osserva che ho (stra)evidenziato "d'equivalenza". Perché? Rileggi la definizione di classe di equivalenza. Per poterla definire devo innanzitutto assicurarmi che la mia relazione è una relazione d'equivalenza, cioè che sia:

- riflessiva: a \ \mathfrak{R} \ a

- simmetrica: a \ \mathfrak{R} \ b \ \Rightarrow \ b \ \mathfrak{R} \ a

- transitiva: a \ \mathfrak{R} \ b \ \mbox{e} \ b \ \mathfrak{R} \ c \ \ \Rightarrow \ a \ \mathfrak{R} \ c

Il tutto per ogni a,b,c \ \in V

Quella del tuo esercizio è una relazione d'equivalenza e lascio a te il compito di verificarlo.

-----------------------

A questo punto, e solo a questo punto, possiamo parlare di classe di equivalenza di un elemento a che appartiene al nostro insieme.

Il testo ci chiede di determinare le classi di equivalenza di 1, 4, 7 e 10, ovvero dobbiamo vedere da quali elementi sono composte:

\left[1\right]_{\mathfrak{R}}, \ \left[4\right]_{\mathfrak{R}}, \ \left[7\right]_{\mathfrak{R}}, \ \left[10\right]_{\mathfrak{R}}

La prima cosa da fare è assicurarci che tali elementi appartengano a V (sempre per definizione di classe).

Ora, chiediamoci: quando un elemento appartiene all'insieme V?

Un elemento appartiene a V se lo si può scrivere nella forma 3h+1, con h \in \mathbb{N}_0 = \mathbb{N} \cup \{0\}

Poiché:

\\ 1=3\cdot \underbrace{0}_{h}+1\\ \\ 4=3\cdot \underbrace{1}_{h}+1\\ \\ 7=3\cdot \underbrace{2}_{h}+1\\ \\ 10=3\cdot \underbrace{3}_{h}+1

Ha senso parlare di

\left[1\right]_{\mathfrak{R}}, \ \left[4\right]_{\mathfrak{R}}, \ \left[7\right]_{\mathfrak{R}}, \ \left[10\right]_{\mathfrak{R}}

Chiarito questo, ricordando che, in generale:

[a]_{\mathfrak{R}} = \{x \in A \ | \ x \ \mathfrak{R} \ a\}

e quindi, nel nostro caso:

\left[1\right]_{\mathfrak{R}}=\{x \ \in V \ | \ x \ \mathfrak{R} \ 1 \}

Per determinare i suoi elementi prendiamo quindi un generico elemento x \in V che, come tale, sarà della forma x=3t+1, \ t \in \mathbb{N}_0 e vediamo quando esso è in relazione con 1.

x \ \mathfrak{R} \ 1 \ \iff \ (3t+1) \ \mathfrak{R} \ \underbrace{(3 \cdot \overbrace{0}^{h} + 1)}_{=1} \iff

(per com'è definita la nostra relazione)

\iff \ |t-0| \in 2\mathbb{N}_0 \ \iff \ |t| \in 2\mathbb{N}_0

Abbiamo quindi:

\left[1\right]_{\mathfrak{R}}=\{3t+1 \ | \ t \in 2\mathbb{N}_0\}

(possiamo trascurare il valore assoluto in quanto t deve appartenere all'insieme dei numeri naturali)

Stesso identico discorso (che lascio a te) per le rimanenti classi.
Ringraziano: Omega, CarFaby
  • Pagina:
  • 1
Os