Classi di congruenza e Z
Ciao, come si può dimostrare che l'insieme delle classi di congruenza modulo n costituiscono una partizione di Z?
Risposte
Deve essere verificata la definizione di partizione:
Cioè ogni insieme deve essere non vuoto, gli insiemi devono essere disgiunti a due a due, e l'unione di tutti gli insiemi deve dare l'insieme $A$
Nel nostro caso, fissato $n in NN$, dobbiamo verificare che $ZZ_n$ è una partizione di $Z$, dove
$ZZ_n={[0]_n,[1]_n,...,[n-1]_n}$ , e
$[0]_n={x in ZZ | EE k in ZZ $ tale che $x=k*n}={...,-2n,-n,0,n,2n,....}$,
$[1]_n={x in ZZ | EE k in ZZ $ tale che $x-1=k*n}={...,-2n+1,-n+1,1,n+1,2n+1,...}$,
.
.
.
$[n-1]_n={x in ZZ | EE k in ZZ $ tale che $x-(n-1)=k*n}={....,-2n+(n-1),-n+(n-1),n-1,n+(n-1),2n+(n-1),...}$.
Riesci a mostrare che valgono le tre proprietà?
Sia $A$ un insieme, $S$ un insieme formato da alcuni sottoinsiemi di $A$ (ovvero $S sube P(A) $)
$S$ è detto partizione di $A$ se e solo se:
1)$AA B in S, B!= O/$
2)$AA B_1,B_2 in S, B_1 ^^ B_2=O/$
3) $ uu B_i=A$
Cioè ogni insieme deve essere non vuoto, gli insiemi devono essere disgiunti a due a due, e l'unione di tutti gli insiemi deve dare l'insieme $A$
Nel nostro caso, fissato $n in NN$, dobbiamo verificare che $ZZ_n$ è una partizione di $Z$, dove
$ZZ_n={[0]_n,[1]_n,...,[n-1]_n}$ , e
$[0]_n={x in ZZ | EE k in ZZ $ tale che $x=k*n}={...,-2n,-n,0,n,2n,....}$,
$[1]_n={x in ZZ | EE k in ZZ $ tale che $x-1=k*n}={...,-2n+1,-n+1,1,n+1,2n+1,...}$,
.
.
.
$[n-1]_n={x in ZZ | EE k in ZZ $ tale che $x-(n-1)=k*n}={....,-2n+(n-1),-n+(n-1),n-1,n+(n-1),2n+(n-1),...}$.
Riesci a mostrare che valgono le tre proprietà?
Mmm...la seconda, ovvero che le varie classi siano disgiunte la posso dimostrare tramite la proprietà transitiva, ovvero supponendo che esista [tex][a] \cap [/tex], allora esisterà un elemento c appartenente alla classe intersezione, ma tale c dovrà essere congruente sia con a che con b, quindi avremo [tex][a] \equiv \pmod{n}[/tex], ergo le classi sono distinte.
Le altre 2 non ho idea, se considerassimo solo [tex]Z_2[/tex] verrebbe facile capire che sono verificate perché effettivamente tutti gli elementi di Z o sono pari o sono dispari, ma con un n generico posso solo dire che i numeri fino a n di Z vanno nella rispettiva classe (1 nella classe [tex][1]_n[/tex],2 nella classe [tex][2]_n[/tex], ecc.) per la prop. riflessiva, ma non saprei che dire per i numeri maggiori di n...
Le altre 2 non ho idea, se considerassimo solo [tex]Z_2[/tex] verrebbe facile capire che sono verificate perché effettivamente tutti gli elementi di Z o sono pari o sono dispari, ma con un n generico posso solo dire che i numeri fino a n di Z vanno nella rispettiva classe (1 nella classe [tex][1]_n[/tex],2 nella classe [tex][2]_n[/tex], ecc.) per la prop. riflessiva, ma non saprei che dire per i numeri maggiori di n...
c'è un modo più semplice: basta osservare che la relazione "congruenza modulo n" è una relazione di equivalenza.
Il fatto che una relazione di equivalenza partizioni un insieme è molto facile da ricavare.
Il fatto che una relazione di equivalenza partizioni un insieme è molto facile da ricavare.
Ok hai dimostrato che sono disgiunte.
Devi dimostrare che ogni ogni insieme è non vuoto:
Tu sai che gli insiemi sono $n$ in tutto.
$AA i in {0,1,2,...,n-1}$ mostro che $_n!=O/$. Ma $_n={x in ZZ | EE k in ZZ $ tale che $ x-i=k*n}$.
Allora sicuramente $_n$ ha almeno un elemento, che sarà...
@blackbishop13: anch'io volevo suggerire la tua strada, ma poi ho letto che si parla di classi di congurenza modulo $n$, dunque l'esercizio sarebbe già finito, perchè, trattandosi di classi di equivalenza, esse sono indotte da una relazione di equivalenza. Quindi sono una partizione.
Devi dimostrare che ogni ogni insieme è non vuoto:
Tu sai che gli insiemi sono $n$ in tutto.
$AA i in {0,1,2,...,n-1}$ mostro che $_n!=O/$. Ma $_n={x in ZZ | EE k in ZZ $ tale che $ x-i=k*n}$.
Allora sicuramente $_n$ ha almeno un elemento, che sarà...
@blackbishop13: anch'io volevo suggerire la tua strada, ma poi ho letto che si parla di classi di congurenza modulo $n$, dunque l'esercizio sarebbe già finito, perchè, trattandosi di classi di equivalenza, esse sono indotte da una relazione di equivalenza. Quindi sono una partizione.
"Gi8":
Tu sai che gli insiemi sono $n$ in tutto.
$AA i in {0,1,2,...,n-1}$ mostro che $_n!=O/$. Ma $_n={x in ZZ | EE k in ZZ $ tale che $ x-i=k*n}$.
Allora sicuramente $_n$ ha almeno un elemento, che sarà...
...x=i, perché con [tex]x-i[/tex] avrei 0 che è sicuramente congruente modulo n, ok hanno tutti almeno un elemento.
Ora, come mai coprono tutto Z? Ripensandoci direi perché:
1)Fino a n-1 posso prendere tutti gli x uguali a n, quindi ad esempio con [tex]Z_3[/tex] 0,1 e 2 li posso mettere nella rispettiva classe di equivalenza.
2)Se prendo n questo lo posso mettere nella classe zero, in quanto [tex]n - 0 = k n[/tex] , n+1 lo posso mettere nella classe 1, infatti [tex](n+1) - 1 = kn[/tex], e così via, diciamo che la regola generale è: data una classe di congruenza [tex]Z_n[/tex] i numeri h
E' giusto?
Sì, tutto giusto. L'idea è quella che hai scritto. Va solo formalizzata meglio.
Io direi così:
Dobbiamo dimostrare che $ZZ=uu_(i=0)^(n-1) _n$, che è equivalente a $uu_(i=0)^(n-1) _n sube ZZ$ $ ^^ $ $ZZ sube uu_(i=0)^(n-1) _n$.
Che sia $uu_(i=0)^(n-1) _n sube ZZ$ è ovvio. Rimane da dimostrare che $ZZ sube uu_(i=0)^(n-1) _n$.
Sia $x in ZZ$. Grazie al teorema sulla divisione euclidea, $EE! m,k in ZZ, 0<=k<=n-1$ tali che $x=m*n+k=> x in [k]_n$
Pertanto $AA x$, $x in ZZ => x in uu_(i=0)^(n-1) _n$, che è proprio quello che volevamo dimostrare. Ok?
Io direi così:
Dobbiamo dimostrare che $ZZ=uu_(i=0)^(n-1) _n$, che è equivalente a $uu_(i=0)^(n-1) _n sube ZZ$ $ ^^ $ $ZZ sube uu_(i=0)^(n-1) _n$.
Che sia $uu_(i=0)^(n-1) _n sube ZZ$ è ovvio. Rimane da dimostrare che $ZZ sube uu_(i=0)^(n-1) _n$.
Sia $x in ZZ$. Grazie al teorema sulla divisione euclidea, $EE! m,k in ZZ, 0<=k<=n-1$ tali che $x=m*n+k=> x in [k]_n$
Pertanto $AA x$, $x in ZZ => x in uu_(i=0)^(n-1) _n$, che è proprio quello che volevamo dimostrare. Ok?
esatto, la mia idea è semplice e veloce, era proprio quello il punto. perché cercare una soluzione difficile quando ce n'è una immediata?
"Gi8":
Sì, tutto giusto. L'idea è quella che hai scritto. Va solo formalizzata meglio.
Io direi così:
Dobbiamo dimostrare che $ZZ=uu_(i=0)^(n-1) _n$, che è equivalente a $uu_(i=0)^(n-1) _n sube ZZ$ $ ^^ $ $ZZ sube uu_(i=0)^(n-1) _n$.
Che sia $uu_(i=0)^(n-1) _n sube ZZ$ è ovvio. Rimane da dimostrare che $ZZ sube uu_(i=0)^(n-1) _n$.
Sia $x in ZZ$. Grazie al teorema sulla divisione euclidea, $EE! m,k in ZZ, 0<=k<=n-1$ tali che $x=m*n+k=> x in [k]_n$
Pertanto $AA x$, $x in ZZ => x in uu_(i=0)^(n-1) _n$, che è proprio quello che volevamo dimostrare. Ok?
Chiarissimo, grazie!
@black
Il punto è che la dimostrazione mi serviva proprio così, partendo dall'insieme delle classi di equivalenza, grazie comunque per l'osservazione è comunque utile osservare un qualcosa da diversi punti di vista...aiuta senz'altro a capire le cose a fondo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo