Esercizio su relazione di equivalenza.
Buonasera, ho accantonato l'algebra da un pò, ora la sto riprendendo, e ho qualche dubbio su vari passaggi.
Considero il seguente esercizio che sembra racchiudere i miei dubbi
Devo provare che
$ x,y \in NN, \ xRy <=> x+y \in NN_p$ è una relazione di equivalenza e descrivere l'insieme quoziente associato.
Per verificare che la relazione sia di equivalenza, dobbiamo verificare che la relazione $R$ sia riflessiva, simmetrica e transitiva, quindi
-1) Riflessività: Sia $x in NN$ si ha per definizione di moltiplicazione in $NN$ che $ x+x=2x$ pertanto $2x$ è pari, quindi è verificata la riflessività.
-2) Simmetrica: $ x,y \in NN : x+y=2n$, poiché $+$ è un commutativa, segue che $ y+x=2n$
-3) Transitivita': $ x,y,z in NN : x+y=2n, y+z=2m$, pertanto sommando a membro a membro ho
$ x+y+y+z=(x+y)+(y+z)= 2n+2m$, dall'altra parte $ x+y+y+z=x+(y+y)+z=x+2y+z=x+(2y+z)=x+(z+2y)=(x+z)+2y$ quindi combinando si ottiene $ (x+z)+2y=2n+2m$, essendo $ a+b=c -> a=c-b$ , allora $ (x+z)=2n+2m-2y=2(n+m-y)$, quindi $ R$ è anche transitiva.
Mi fermo qui con la discussione, vorrei verificare se ci sono errori su questi passaggi.
Ciao
Considero il seguente esercizio che sembra racchiudere i miei dubbi
Devo provare che
$ x,y \in NN, \ xRy <=> x+y \in NN_p$ è una relazione di equivalenza e descrivere l'insieme quoziente associato.
Per verificare che la relazione sia di equivalenza, dobbiamo verificare che la relazione $R$ sia riflessiva, simmetrica e transitiva, quindi
-1) Riflessività: Sia $x in NN$ si ha per definizione di moltiplicazione in $NN$ che $ x+x=2x$ pertanto $2x$ è pari, quindi è verificata la riflessività.
-2) Simmetrica: $ x,y \in NN : x+y=2n$, poiché $+$ è un commutativa, segue che $ y+x=2n$
-3) Transitivita': $ x,y,z in NN : x+y=2n, y+z=2m$, pertanto sommando a membro a membro ho
$ x+y+y+z=(x+y)+(y+z)= 2n+2m$, dall'altra parte $ x+y+y+z=x+(y+y)+z=x+2y+z=x+(2y+z)=x+(z+2y)=(x+z)+2y$ quindi combinando si ottiene $ (x+z)+2y=2n+2m$, essendo $ a+b=c -> a=c-b$ , allora $ (x+z)=2n+2m-2y=2(n+m-y)$, quindi $ R$ è anche transitiva.
Mi fermo qui con la discussione, vorrei verificare se ci sono errori su questi passaggi.
Ciao
Risposte
Credo, anche se non l'ho mai vista prima come notazione, che $NN_p$ siano i numeri pari, cioè che $NN_p = 2NN$.
Per riflessività e simmetria tutto ok.
Per la transitività ok pure, e ti puoi fermare anche qui $x+z=2n+2m-2y$ se hai già stabilito che $2NN$ è chiuso rispetto alla sottrazione (i.e., che la differenza di due pari è ancora pari).
Per il quoziente, cerca di capire com'è fatta è la classe di $R$-equivalenza di qualche $x in NN$, il che è molto semplice (ad esempio, potresti chiederti chi sono $[0]_R$ ed $[1]_R$?).
Fatto ciò il quoziente lo determini facilmente.
Per riflessività e simmetria tutto ok.
Per la transitività ok pure, e ti puoi fermare anche qui $x+z=2n+2m-2y$ se hai già stabilito che $2NN$ è chiuso rispetto alla sottrazione (i.e., che la differenza di due pari è ancora pari).
Per il quoziente, cerca di capire com'è fatta è la classe di $R$-equivalenza di qualche $x in NN$, il che è molto semplice (ad esempio, potresti chiederti chi sono $[0]_R$ ed $[1]_R$?).
Fatto ciò il quoziente lo determini facilmente.
Ciao, si con il simbolo $NN_p$ intendo l'insieme dei naturali pari, provo che è chiuso rispetto alla sottrazione, perché non sono sicuro di aver compreso la definizione di sottrazione in $NN$, quindi in $2NN$.
Allora, dal libro da cui sto studiando, cioè "Lezioni di algebra di Curzio-Longobardi-Maj", vengono introdotti i principali insiemi numerici, ed in particolare, si parte dalla terne di Peano, che ho se ho ben compreso, la terna $(NN,+,0)$ è una terna di Peano.
In una terna di Peano, si introduce la differenza nel seguente modo:
Siano $x,y in S$ con $x<=y$ si definisce differenza $ d in S : x+d=y$, e tale $ d:=y-x$
Quindi, la differenza $ d$ in una terna di Peano esiste solo quando $y>=x$, quindi anche in $NN$ e in $2NN$.
Se voglio provare che $2NN$ è chiuso rispetto alla sottrazione, devo far vedere che presi comunque $ a,b in 2NN$ allora $ a-b in 2NN$.
Siano $ a,b in 2NN -> a=2n, b=2m$, con $n>=m -> a>=b$, allora dalla definizione segue $ 2n-2m in 2NN$.
Allora, dal libro da cui sto studiando, cioè "Lezioni di algebra di Curzio-Longobardi-Maj", vengono introdotti i principali insiemi numerici, ed in particolare, si parte dalla terne di Peano, che ho se ho ben compreso, la terna $(NN,+,0)$ è una terna di Peano.
In una terna di Peano, si introduce la differenza nel seguente modo:
Siano $x,y in S$ con $x<=y$ si definisce differenza $ d in S : x+d=y$, e tale $ d:=y-x$
Quindi, la differenza $ d$ in una terna di Peano esiste solo quando $y>=x$, quindi anche in $NN$ e in $2NN$.
Se voglio provare che $2NN$ è chiuso rispetto alla sottrazione, devo far vedere che presi comunque $ a,b in 2NN$ allora $ a-b in 2NN$.
Siano $ a,b in 2NN -> a=2n, b=2m$, con $n>=m -> a>=b$, allora dalla definizione segue $ 2n-2m in 2NN$.
Che $2NN$ sia chiuso rispetto alla sottrazione segue da un fatto base dell'aritmetica di $NN$: la somma di numeri con stessa parità [nota]Cioè, entrambi pari o entrambi dispari.[/nota][risp. parità differenti [nota]Ossia, uno pari l'altro dispari.[/nota]] è pari [risp. dispari] è un numero pari [risp. dispari].[nota]Ciò si prova, ad esempio, sfruttando la proprietà distributiva della moltiplicazione rispetto all'addizione.[/nota]
Infatti, se $y >= x$ sono pari, allora esiste $d in NN$ tale che $x + d = y$; e se, per assurdo, $d$ fosse dispari, tale sarebbe anche $y$ (somma di numeri con parità diverse), ma ciò è assurdo perché contro l'ipotesi; dunque $d$ è pari.
P.S.: Il libro di Curzio, pur non avendoci mai studiato, lo conosco un po'. Non ricordo di averci mai guardato la definizione di $NN$, quindi non so cosa intenda con "terna di Peano" o come faccia la costruzione assiomatica di $NN$. Tuttavia, passati gli assiomi e cominciata a costruire la teoria, le proprietà fondamentali delle operazioni e le definizioni aritmetiche quelle sono.
Infatti, se $y >= x$ sono pari, allora esiste $d in NN$ tale che $x + d = y$; e se, per assurdo, $d$ fosse dispari, tale sarebbe anche $y$ (somma di numeri con parità diverse), ma ciò è assurdo perché contro l'ipotesi; dunque $d$ è pari.
P.S.: Il libro di Curzio, pur non avendoci mai studiato, lo conosco un po'. Non ricordo di averci mai guardato la definizione di $NN$, quindi non so cosa intenda con "terna di Peano" o come faccia la costruzione assiomatica di $NN$. Tuttavia, passati gli assiomi e cominciata a costruire la teoria, le proprietà fondamentali delle operazioni e le definizioni aritmetiche quelle sono.
Grazie per il chiarimento.
Classi di equivalenza
$ [0]={x \in NN \ : x=2n, n \in NN}={0,2,4,6,8,...$
$ [1]={x \in NN \ : x+1=2n, n \in NN}$, essendo che $a,b,c \in NN$ tale che $a+b=c -> b=c-a$, con $c\geb$, allora si ha
$ [1]={x \in NN \ : x=2n-1, n \in NN}={2*1-1,2*2-1,2*3-1,2*4-1,.... = {1,3,5,7,...$
Ora non ho più bisogno di continuare, per via di una proprietà delle classi di equivalenza, quindi, l'insieme quoziente è formato dalle classe di equivalenza i cui rappresentanti sono $[0], [1]$
Come vedi la classe $[1]$ ho esplicitato l'espressione dei termini che la definiscono per mostrare che il valore $n$ varia da $1$ e non da $0$.
Ora, sulle slide vedo che le classi sono $[1], [2]$, questo perché la prof. considera $NN$ senza lo zero ?
Ciao
Classi di equivalenza
$ [0]={x \in NN \ : x=2n, n \in NN}={0,2,4,6,8,...$
$ [1]={x \in NN \ : x+1=2n, n \in NN}$, essendo che $a,b,c \in NN$ tale che $a+b=c -> b=c-a$, con $c\geb$, allora si ha
$ [1]={x \in NN \ : x=2n-1, n \in NN}={2*1-1,2*2-1,2*3-1,2*4-1,.... = {1,3,5,7,...$
Ora non ho più bisogno di continuare, per via di una proprietà delle classi di equivalenza, quindi, l'insieme quoziente è formato dalle classe di equivalenza i cui rappresentanti sono $[0], [1]$
Come vedi la classe $[1]$ ho esplicitato l'espressione dei termini che la definiscono per mostrare che il valore $n$ varia da $1$ e non da $0$.
Ora, sulle slide vedo che le classi sono $[1], [2]$, questo perché la prof. considera $NN$ senza lo zero ?
Ciao
Confrontando le proprietà caratteristiche con cui definisci $[0]$ ed $[1]$ non si capisce se $0 in NN$ o $0 notin NN$: infatti, la prima $x = 2n$ funziona se $0 in NN$, ma la seconda $x = 2n - 1$ funziona solo se $0 notin NN$.
A parte questo dettaglio, che comunque va corretto, il fatto interessante è che $[0] = 2 NN = NN_p$ e $[1]= 1 +2NN = NN_d$ (fondamentalmente, perché vale quel fatto sulla somma di numeri con parità uguale/diversa che citavo sopra), quindi hai finito.
Per quanto riguarda le slide, è chiaro che $[0]=[2]$, quindi di lì non puoi concludere che $0 notin NN$, ma solo che alla tua docente non piace tanto usare lo $0$... Forse perché abituata ad usare gli interi positivi, i.e. $ZZ^+ =\{ 1,2,3,4,...\}$.
Per essere sicuro, conviene chiedere.
A parte questo dettaglio, che comunque va corretto, il fatto interessante è che $[0] = 2 NN = NN_p$ e $[1]= 1 +2NN = NN_d$ (fondamentalmente, perché vale quel fatto sulla somma di numeri con parità uguale/diversa che citavo sopra), quindi hai finito.
Per quanto riguarda le slide, è chiaro che $[0]=[2]$, quindi di lì non puoi concludere che $0 notin NN$, ma solo che alla tua docente non piace tanto usare lo $0$... Forse perché abituata ad usare gli interi positivi, i.e. $ZZ^+ =\{ 1,2,3,4,...\}$.
Per essere sicuro, conviene chiedere.
gugo82 io presumo che la professoressa intenda $NN$ l'insieme dei numeri interi positivi $ZZ_+$, perché, con il simbolo $NN_0$ indica l'insieme $ZZ_+ \cup{0}$. Fatta questa precisazione, non so come continuare, cioè, saprei continuare se intendo $ NN={0,1,2....$ perché preso $ x \in NN$ ho che $ [x]={y \in NN \ : x+y=2n, \ n \in NN }$, cioè la classe di equivalenza di $x$ è il sottoinsieme di $NN$ formato termini $y$ la cui somma con $x$ da un numero pari; osservo che $x+y$ è pari sse $x,y$ hanno la stessa parità: Infatti, se $x,y$ pari, allora esistono $h_1,h_2 \in NN \: x=2h_1, y=2h_2 -> x+y=2h_1+2h_2=2(h_1+h_2)$,
se $x,y$ dispari, allora esistono $h_1,h_2 \in NN \: x=2h_1+1, y=2h_2+1 -> x+y=(2h_1+1)+(2h_2+1)=2h_1+(1+2h_2)+1=2h_1+(2h_2+1)+1=2h_1+2h_2+2=2(h_1+h_2+1)$
Viceversa, se $x+y$ è pari, allora esiste un $n \in NN$ tale che $x+y=2n$, suppongo per assurdo che $x,y$ non hanno la stessa parità, pertanto, esistono due naturali $h_1, h_2$ per cui $x=2h_1, y=2h_2+1$ allora si ha
$2n=x+y=2h_1+(2h_2+1)=2(h_1+h_2)+1 ->^1 2n-2(h_1+h_2)=1 ->2(n-h_1-h_2)=1$, cioè $1$ è divisibile per $2$ assurdo.
Quindi, le classe di equivalenza sono $[0], [1]$ per l'osservazione fatta sopra.
Può andare bene ?
In $1$ la differenza è valutabile, perché $2n\ge 2h_1+(2h_2+1) $
se $x,y$ dispari, allora esistono $h_1,h_2 \in NN \: x=2h_1+1, y=2h_2+1 -> x+y=(2h_1+1)+(2h_2+1)=2h_1+(1+2h_2)+1=2h_1+(2h_2+1)+1=2h_1+2h_2+2=2(h_1+h_2+1)$
Viceversa, se $x+y$ è pari, allora esiste un $n \in NN$ tale che $x+y=2n$, suppongo per assurdo che $x,y$ non hanno la stessa parità, pertanto, esistono due naturali $h_1, h_2$ per cui $x=2h_1, y=2h_2+1$ allora si ha
$2n=x+y=2h_1+(2h_2+1)=2(h_1+h_2)+1 ->^1 2n-2(h_1+h_2)=1 ->2(n-h_1-h_2)=1$, cioè $1$ è divisibile per $2$ assurdo.
Quindi, le classe di equivalenza sono $[0], [1]$ per l'osservazione fatta sopra.
Può andare bene ?
In $1$ la differenza è valutabile, perché $2n\ge 2h_1+(2h_2+1) $
La tua relazione è esattamente uguale alla "congruenza modulo 2", sebbene essa sia definita sugli interi e non sui naturali (le congruenze di monoidi sono dei pokémon rari).
Questo significa che due elementi sono in relazione se e solo se sono entrambi pari o entrambi dispari, come ti è stato già detto.
Questo, a sua volta, vuol dire che l'insieme \(S=\{1,2\}\) è un insieme trasversale rispetto alla relazione in questione,[nota]Se $R$ è una relazione su un insieme $X$, \(S\subseteq X\) è un "trasversale" rispetto a $R$ se per ogni \(x\in X\), l'intersezione \(S\cap [x]_R\), dove \([x]_R = \{y\in X\mid xRy\}\), ha esattamente un elemento.[/nota] e come conseguenza l'insieme \(\{[1],[2]\}\) è il tuo quoziente.
Prova a dimostrare questa ultima cosa che ho detto, cioè che \(\{1,2\}\) è un trasversale per la tua relazione.
Questo significa che due elementi sono in relazione se e solo se sono entrambi pari o entrambi dispari, come ti è stato già detto.
Questo, a sua volta, vuol dire che l'insieme \(S=\{1,2\}\) è un insieme trasversale rispetto alla relazione in questione,[nota]Se $R$ è una relazione su un insieme $X$, \(S\subseteq X\) è un "trasversale" rispetto a $R$ se per ogni \(x\in X\), l'intersezione \(S\cap [x]_R\), dove \([x]_R = \{y\in X\mid xRy\}\), ha esattamente un elemento.[/nota] e come conseguenza l'insieme \(\{[1],[2]\}\) è il tuo quoziente.
Prova a dimostrare questa ultima cosa che ho detto, cioè che \(\{1,2\}\) è un trasversale per la tua relazione.
megas_archon ti ringrazio per i suggerimenti; mi sembra di averlo dimostrato che la somma di due elementi è pari sse hanno la stessa parità, e questo dovrebbe determinare l'insieme quoziente.
Provo che \( S=\{0,1\} \) è trasversale; $x\in NN -> x=2p \vee x=2p+1, p \in NN $, per cui
Ora, ci vorrebbe, una proprietà che dice: Se $S\subseteqX$ è trasversale, e $R$ è una relazione di equivalenza in $S$, allora $Q={[x]\:\ x \in S}$
Provo che \( S=\{0,1\} \) è trasversale; $x\in NN -> x=2p \vee x=2p+1, p \in NN $, per cui
$[2p]={0,2,4,...,2p,... \qquad [2p+1]={1,3,5,...,2p+1,...$
dall'intersezione \( S\cap [2p]_R=\{0\} \vee S\cap [2p+1]_R=\{1\} \)Ora, ci vorrebbe, una proprietà che dice: Se $S\subseteqX$ è trasversale, e $R$ è una relazione di equivalenza in $S$, allora $Q={[x]\:\ x \in S}$
"compa90":
Ora, ci vorrebbe, una proprietà che dice: Se $S\subseteqX$ è trasversale, e $R$ è una relazione di equivalenza in $S$, allora $Q={[x]\:\ x \in S}$
Questo mi sembra abbastanza ovvio, non credi?
Quanti elementi di ogni classe di equivalenza ti occorre conoscere per scrivere un quoziente?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo