[logica di base] Intersezione fra Relazioni

Messaggioda AlexanderSC » 15/02/2019, 21:11

Buondì,
non riesco a capire perché la domanda:
"Siano R ed S relazioni di equivalenza su un insieme finito non vuoto, con rispettivamente n ed m classi di equivalenza, quali delle seguenti proposizioni è vera?"
ha la seguente risposta:
Risposta:" \( R\cap S \) è sempre una relazione di equivalenza con al più n*m classi di equivalenza"

Sò che l'intersezione, se le condizioni sono rispettate, preserva determinate proprietà dei due insiemi intersecati ( Se esiste la chiusura rispetto a P per ogni insieme P-Maggiorabile, la P sarà preservata dall'intersezione di due insiemi per cui è valida), quindi su quello non ho dubbi, ma non capisco perché poi il numero di classi di equivalenza totali risulta essere il prodotto fra le classi di equivalenza m con le classi di equivalenza n.

Fra le opzioni c'era una che recitava invece:
" \( R\cap S \) è sempre una relazione di equivalenza con al più n+m classi di equivalenza"
Il punto è che non capisco come possiamo arrivare a stabilire che fra le due opzioni, è proprio quella che ha n*m, quella giusta.

Aiutino? :(
AlexanderSC
Junior Member
Junior Member
 
Messaggio: 26 di 234
Iscritto il: 10/02/2019, 19:57

Re: [logica di base] Intersezione fra Relazioni

Messaggioda fmnq » 16/02/2019, 01:09

Che l'intersezione di relazioni di equivalenza su un insieme $A$ sia una relazione di equivalenza, è evidente perché le proprietà di una relazione di equivalenza sono quantificate universalmente, e queste proprietà sono stabili per intersezione.

Rimane da vedere che il quoziente \(A_{RS} = A/(R\cap S)\) ha al più $nm$ elementi, se \(n = \#(A/R)\) e \(m = \#(A/S)\). Per questo ti è sufficiente trovare una funzione iniettiva \(A_{RS}\to A/R \times A/S\); ti suggerisco di prendere la mappa indotta da
\[
\varphi : A \to A/R \times A/S : x \mapsto ([x]_R, [x]_S)
\] che manda $x\in A$ nella coppia fatta dalla classe di equivalenza cui appartiene, modulo $R$ e modulo $S$ rispettivamente. Questa induce un'unica funzione \(\tilde\varphi : A_{RS} \to A/R\times A/S\) (dimostralo), la quale è iniettiva (dimostralo).
fmnq
Average Member
Average Member
 
Messaggio: 216 di 764
Iscritto il: 03/10/2017, 23:14

Re: [logica di base] Intersezione fra Relazioni

Messaggioda AlexanderSC » 16/02/2019, 12:36

Ok, quello che ho fatto è il seguente:
Ho preso un insieme A non vuoto formato da 2 elementi \( A = \) { \( 1, 2 \) }, e mi sono trovato due relazioni d'equivalenza R ed S su A, dove \( R \) \( = \) { \( (1,1),(2,2),(1,2),(2,1) \) } e \( S = \) { \( (1,1),(2,2) \) }.


\( A/R = \) { \( |1| \) } Perché \( |1| = |2| \)
\( A/S = \) { \( |1|,|2| \) }

Il prodotto cartesiano fra \( A/R XA/S \) avrà le seguenti coppie: { \( (|1|r,|1|s), (|1|r, |2|s) \) }

E qui c'è un problema, seguendo il modello in cui ho una funzione che associa \( \forall x \in A \) una \( x \) ad un elemento \( (|x|r, |x|s) \) , il |2| rimarrà escluso, andando contro le regole che definiscono una funzione e quindi un punto di stop.

La mia logica almeno mi porta a questo risultato, sai cosa posso aver sbagliato? (p.s. nella 2° opzione diceva " al più n+m" vuol dire che invece del prodotto cartesiano fra n ed m, avrei dovuto considerare l'unione?)
AlexanderSC
Junior Member
Junior Member
 
Messaggio: 27 di 234
Iscritto il: 10/02/2019, 19:57

Re: [logica di base] Intersezione fra Relazioni

Messaggioda fmnq » 16/02/2019, 12:43

Non fare la dimostrazione in un esempio particolare; fai la dimostrazione in generale.

L'intersezione di $R$ ed $S$ in quel caso specifico è $S$, che è la relazione identica, sicché \(A/S\cong A\), che ha 2 elementi.
fmnq
Average Member
Average Member
 
Messaggio: 219 di 764
Iscritto il: 03/10/2017, 23:14

Re: [logica di base] Intersezione fra Relazioni

Messaggioda AlexanderSC » 16/02/2019, 20:38

Me la potresti fare te perfavore, che non ci sto capendo niente. :( :( :(
Poi cosa vuol dire $ ~= $ ?
AlexanderSC
Junior Member
Junior Member
 
Messaggio: 31 di 234
Iscritto il: 10/02/2019, 19:57

Re: [logica di base] Intersezione fra Relazioni

Messaggioda fmnq » 16/02/2019, 22:11

AlexanderSC ha scritto:Me la potresti fare te perfavore, che non ci sto capendo niente.

Ti ho detto cosa devi fare: dimostra che esiste una funzione \[ \varphi : A \to A/R \times A/S : x \mapsto ([x]_R, [x]_S) \] che manda $ x\in A $ nella coppia fatta dalla classe di equivalenza cui appartiene, modulo $ R $ e modulo $ S $ rispettivamente. Questa funzione induce un'unica funzione \( \tilde\varphi : A_{RS} \to A/R\times A/S \) (dimostralo: è costante sulle classi di $R\cap S$-equivalenza, quindi...), la quale è iniettiva (dimostralo, con la definizione di iniettiva, e usando il fatto che se $([x]_R, [x]_S)=([y]_R,[y]_S)$, allora...).
Poi cosa vuol dire $ ~= $ ?
$X\cong Y$ vuol dire che esiste un isomorfismo (in questo caso, una biiezione) tra $X$ e $Y$.
fmnq
Average Member
Average Member
 
Messaggio: 227 di 764
Iscritto il: 03/10/2017, 23:14


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite