Esercizio sulle Relazioni

[gladior-votailprof]

Dimostare che la relazione definita dalla legge "nRm <=> n ed m divisi per quattro danno lo stesso resto" determinare su N una relazione di equivalenza. Calcolare l'insieme quoziente N/R.


Vorrei capire come si procede anche perchè non ho idea di come effettuare la dimostrazione................qualcuno potrebbe aiutarmi gentilmente.......................

[Paolo902]

Scusa, ma non mi è chiaro il testo del problema. Secondo me vuoi dimostrare che la relazione di congruenza $mod 4$ è una relazione d'equivalenza, ma non so se ho capito bene.

[gladior-votailprof]

"Paolo90":Scusa, ma non mi è chiaro il testo del problema. Secondo me vuoi dimostrare che la relazione di congruenza $mod 4$ è una relazione d'equivalenza, ma non so se ho capito bene.

Ho riportato il testo cosi come il prof lo ha scritto............

[adaBTTLS1]

puoi dimostrare che è riflessiva, simmetrica, transitiva.
puoi anche far vedere che genera una partizione, di rappresentanti $0,1,2,3$.
risposto a questo, il resto è banale.
prova e facci sapere. ciao.

[gladior-votailprof]

"adaBTTLS":puoi dimostrare che è riflessiva, simmetrica, transitiva.
puoi anche far vedere che genera una partizione, di rappresentanti $0,1,2,3$.
risposto a questo, il resto è banale.
prova e facci sapere. ciao.

Il problema è questo so cos' è una relazione di equivalenza solo che non so come procedere, non pretendo che tu risolva l'esercizio, magari conosci qualche link oppure possiedi del materiale che possa aiutarmi nel capire come procedre per la risoluzione del seguente esercizio. Grazie mille sei sempre pronto a rispondere alle mie problematiche.

[adaBTTLS1]

se non sai come procedere, ti conviene partire dalle definizioni.
scrivi che cosa significa che una relazione è riflessiva, simmetrica, transitiva, e poi traduci $xRy$ con "x ed y hanno lo stesso resto nella divisione per 4".
non devi fare molto di più, si tratta solo di scrivere in maniera sensata, ordinata e pertinente.
prova, ed eventualmente ti correggeremo.

[mistake89]

Provare che è una relazione di equivalenza è davvero facile... se ti è più comodo prova all'inizio a pensarla con i numeri magari ti aiuta a fissare le idee.
Se io prendo un numero, chessò 7 e lo divido per 4, mi dà resto 3 ... se prendo di nuovo 7, avrò lo stesso resto ovvero 3... quindi $7R7$ ora generalizza per qualsiasi $x$ e la prima è provata... con gli altri non devi fare tanto altro sforzo!

[gladior-votailprof]

"mistake89":Provare che è una relazione di equivalenza è davvero facile... se ti è più comodo prova all'inizio a pensarla con i numeri magari ti aiuta a fissare le idee.
Se io prendo un numero, chessò 7 e lo divido per 4, mi dà resto 3 ... se prendo di nuovo 7, avrò lo stesso resto ovvero 3... quindi $7R7$ ora generalizza per qualsiasi $x$ e la prima è provata... con gli altri non devi fare tanto altro sforzo!

Sei stato gentilissimo domani provo adesso devo andare sei stato a domani.

[gladior-votailprof]

Dimostare che la relazione definita dalla legge "nRm <=> n ed m divisi per quattro danno lo stesso resto" determinare su N una relazione di equivalenza. Calcolare l'insieme quoziente N/R.

Per prima cosa bisogna dimostare:(= ha il significato di congruo)
n=m (mod 4) giusto?

Bisogna dimostrare che è una relazione di equivalenza su N
Cioè:
1) Riflessiva cioè : n=n (mod4)
2) Simmetrica cioè : n=m (mod4) => m=n(mod4)
3) Transitiva cioè: n=m(mod4) e m=c(mod4) => n=c(mod4)

Qualcuno può dirmi se è giusto il ragionamento
controllando gli eventuali passaggi?

[gladior-votailprof]

Dimostrare che la relazione definita dalla legge:"nRm=>n ed m divisi per quattro danno lo stesso resto" determinare su N una relazione di equivalenza. Calcolare 'insieme quoziente N/R

Sono riuscito a svolgerlo solo che volevo sapere se il ragionamento che ho applicato è valido

Prima di tutto sfrutto l'equivalenza di queste 3 proposizioni:
1) a ≡ b (mod n)
2) a = b + kn, k ∈ ℤ (cioè per qualche valore k ∈ ℤ)
3) a e b hanno lo stesso resto se divisi per n


a ℛ b ⇔ a e b divisi per 4 danno lo stesso resto" ⇔ a = b + 4k (k ∈ ℤ)

Prop. riflessiva)
Provo che a ℛ a, cioè che ∃k ∈ ℤ: a = a + 4k.
Infatti:
a ℛ a ⇔ a = a + 4k (k ∈ ℤ) ⇔ a - a = 4k (k ∈ ℤ) ⇔ 0 = 4k (k ∈ ℤ) che è vero per k = 0 ∈ ℤ. Fine
Prop. simmetrica)
Sia a ℛ b, provo che vale anche b ℛ a, cioè che b = a + 4k' (k' ∈ ℤ) .
Infatti:
a ℛ b ⇔ a = b + 4k (k ∈ ℤ) ⇔ b = a - 4k (k ∈ ℤ) ⇔ b = a + 4(-k) (k ∈ ℤ)
Ma siccome k ∈ ℤ allora anche -k ∈ ℤ,
perciò posto k' = -k ∈ ℤ ho dimostrato la validità della proprietà. Fine
Prop. transitiva)
Siano a ℛ b e b ℛ c, provo che vale anche a ℛ c, cioè che a = c + 4k''' (k''' ∈ ℤ).
Infatti:
a ℛ b ⇔ a = b + 4k' (k' ∈ ℤ)
e
b ℛ c ⇔ b = c + 4k'' (k'' ∈ ℤ)

ma allora, unendo le proposizioni al secondo membro:
a = b + 4k' (k' ∈ ℤ)
a = c + 4k'' + 4k' (k', k'' ∈ ℤ)
a = c + 4(k'' + k') (k', k'' ∈ ℤ)

Sicome k', k'' ∈ ℤ, allora anche k'' + k' ∈ ℤ,
quindi posto k''' = k'' + k' ∈ ℤ ho dimostrato la validità della proprietà. Fine ∎

L'insieme quoziente è formato dalle classi di equivalenza della relazione ℛ, che sono sottoinsiemi di ℕ in ciascuno dei quali sono presenti tutti numeri che danno lo stesso resto se divisi per 4.
Siccome i resti della divisione per 4 sono proprio 4, e cioè i numeri {0, 1, 2, 3}, e siccome 0, 1, 2 e 3 sono tutti numeri il cui resto nella divisione per 4 è un numero vicendevolmente diverso (che guardacaso coincide con il numero stesso), posso sfruttare questi 4 numeri come rappresentanti per le singole classi di equivalenza, e ricordando che con [n]ℛ si indica la classe di equivalenza rispetto alla relaz. di equivalenza ℛ uno dei quali rappresentanti è n (cioè di cui n fa parte), posso scrivere:

ℕ/ℛ = {[0]ℛ, [1]ℛ, [2]ℛ, [3]ℛ}

In forma un po' più estesa e più esemplificativa, avremmo:
ℕ/ℛ = {{0, 4, 8, 12, ...}, {1, 5, 9, 13, ...}, {2, 6, 10, 14, ...}, {3, 7, 11, 15, ...}}