Ingegneria Energetica - Analisi e Geometria 1

Relazioni di equivalenza e d'ordine

Divided by topic

Denizione 1. SianoAeBinsiemi. Si denisceprodotto cartesianol'insieme: AB=f(a; b) :a2A^b2Bg: Osservazione 1.Si osservi che nella Denizione 1. le coppie sonoordinate, vale a dire (x; y)6 = (y; x) sex6 =y. E quindi chiaro cheAB6 =BA, seA6 =B. Risulta inoltre:A ;=; A=;. Denizione 2.SianoAeBinsiemi. Si dicerelazione tra gliAelementi diAe gli elementi diBun qualunque sottoinsieme del prodotto cartesianoAB. SeA=B, si parla semplicemente di relazione tra gli elementi diA; quindi, in questo caso,R AA. Esempio 1.L'insieme R=f(x; y)2NZ:y=xg e una relazione tra gli elementi diNeZ. Si ha R=f(0;0);(1;1);(2;2);(3;3); : : :g: Esempio 2.L'insieme R0 =f(x; y)2ZZ:y=xg e una relazione tra gli elementi diZ. Risulta R0 =f: : : ;(2;2);(1;1);(0;0);(1;1);(2;2); : : :g: Denizione 3.SianoAun insieme non vuoto,Runa relazione tra gli elementi diA. Si dice cheReri essivase e vericata la sequente condizione: (8a2A) ((a; a)2 R): Osservazione 2.Ovviamente, percheRnon sia ri essiva, basta che esista un solo elementox2Atale che (x; x)= 2A. Esempio 3.Non ha senso chiedersi se la relazioneRdell'Esempio 1 sia ri essiva, visto che si tratta di una relazione tra elementi di due insiemi diversi. Esempi 1.Delle relazioni sull'insiemeA=f;  ; g R1= f(; );( ; );( ; );(; );(; )g R2= f(; );( ; );(; );( ; )g R3= f(; );( ; );( ; );( ; );( ; )g R4= f(; );( ; );(; )g R5= f(; );( ; );( ; );(; );( ; )g sono ri essiveR 1e R 5, mentre R 2, R 3, R 4non sono ri essive. Denizione 4.SianoAun insieme non vuoto,Runa relazione tra gli elementi diA. Si dice cheResimmetricase e vericata la sequente condizione: (8a; b2A) ((a; b)2 R )(b; a)2 R): Osservazione 3.Naturalmente e suciente che esista una sola coppia (x; y)2 R, x6 =y, tale che (y; x)= 2 RpercheRnon sia simmetrica. Denizione 5.Si dice cheReantisimmetricase e vericata la sequente condizione: (8a; b2A) ((a; b)2 R ^(b; a)2 R))a=b
: Osservazione 4.La condizione di antisimmetria puo essere riscritta nel modo che segue: (8a; b2A; a6 =b)((a; b)= 2 R)): 1 2 Esempi 2.R 1e R 2sono antisimmetriche, R 3e R 5sono simmetriche, R 4non e sim- metrica ne' antisimmetrica. Denizione 6.SianoAun insieme non vuoto,Runa relazione tra gli elementi diA. Si dice cheRetransitivase e vericata la sequente condizione: (8a; b; c2A) ((a; b)2 R ^(b; c)2 R))(a; c)2 R
: Osservazione 5.Anche in questo caso e suciente che esistano (x; y);(y; z)2 Rtali che (x; z)= 2 RpercheRnon sia transitiva. Esempi 3.R 1e R 5sono transitive, R 2, R 3e R 4non lo sono. Esempio 4.La relazioneR0 dell'Esempio 2 non e ri essiva perche, per esempio, (1;1)= 2 R; non e neppure antiri essiva perche (0;0)2 R. Sicuramente e simmetrica, perche (x; y)2 R0 )y=x)x=y)(y; x)2 R0 : InneR0 non e transitiva: (1;1)2 R ^(1;1)2 Rma (1;1)= 2 R Osservazione 6.Si osservi che spesso si usa la notazioneaRbin luogo di (a; b)2 R. Denizione 7.Si dice cheReuna relazione d'ordinese eri essiva, antisimmetrica e transitiva. La coppia ordinata (A;R) (ovvero l'insiemeAmunito della relazione d'ordine) si chiama insieme ordinato. Esempio 5.La relazione R1= f(; );( ; );( ; );(; );(; )g e d'ordine. Esempio 6.SiaXun insieme. Allora la relazione \" e una relazione d'ordine su P(X). Infatti si e osservato in precedenza che per ogniA; B; Csottoinsiemi diX (1)AA (2) seABeBAalloraA=B (3) seABeBCalloraAC Quindi (P(X);) e un insieme ordinato. Esempio 7.L'ordinamento naturale \" sull'insiemeZdei numeri relativi e la re- lazione denita come segue: 8m; n2Z; mn() 9h2Ntale chen=m+h . Si verica che \" e una relazione d'ordine suZ: ri essivita: sen2Z, allora902Ntale chen=n+ 0 e pertantonn antisimmetria: sianon; m2Z, in modo chenm^mn. Si ha: (nm^mn))(9h2Ntale chen=m+h)^(9k2Ntale chen=m+k) )n=m+h=n+k+h)h+k= 0)h=k= 0)n=m: transitivita: sianon; m; p2Z, in modo chemn^np. Allora: (mn^np))(9h2Ntale chem=m+h)^(9k2Ntale chep=n+k) )p=n+k=m+h+k) 9h+k2Ntale chep=m+ (h+k))mp: Esempio 8.Si puo considerare suZla seguente relazione:8m; n2Z, si ponem < n se e solo se9h2N tale chen=m+h. Questa relazione non e d'ordinein quanto non ri essiva. Si osservi che m < n,(mn^m6 =n): 3 Denizione 8.Sianoa; b2Z,a6 = 0. Si dice cheadividebo chee un divisore dibo anche chebmoltiplicaaobe un multiplo diae si scriveajbse esisteh2Ztale che b=ha. Quindi ajb() 9h2Ztale cheb=ha Esercizio 1.La relazione \j" sull'insiemeN dei numeri naturali non nulli e una relazione d'ordine. Si tratta di provare che la relazione denita8m; n2N da mjn() 9h2N tale chen=hm e ri essiva, antisimmetrica e transitiva. La verica e del tutto analoga a quella dell'E-sempio 7. Denizione 9.Siano (A;) un insieme ordinato,Xun sottoinsieme diA,X6 =;, x02 X. Si dice chex 0e minimo di X se: (8x2X) (x 0 x): Si dice chex 0e massimo di X se (8x2X) (xx 0) : SeX=A, si parla di minimo o di massimo diA. Proposizione 1.Siano(A;)un insieme ordinato,Xun sottoinsieme diA,X6 =;. Se esiste un massimo (o un minimo) diX, esso e unico. Dimostrazione.Siano, infatti,x 0e x 1due massimi di X. Allora, poichex 0e massimo ex 12 X, si hax 1 x 0; d'altra parte, poiche x 1e massimo e x 02 X, si hax 0 x 1. Allora, per la proprieta antisimmetrica delle relazioni d'ordine deve esserex 0= x 1. (Analoga la dimostrazione dell'unicita del minimo.) Siano (A;) un insieme ordinato,Xun sottoinsieme diA,X6 =;,x 02 X. Grazie alla Proposizione 1, e possibile utilizzare un simbolo specico per il minimo (che si dice ancheil piu piccolo elemento) diX, e per il massimo (che si dice ancheil piu grande elemento) diX, quando esistono. Essi si indicano, rispettivamenete, con: min(X) emax(X): Esempio 9.1. Sia (A;R 1) l'insieme ordinato dell'esempio 2. E evidente che=min(A) ma non esiste il massimo diA. 2. se si considera l'insieme (N;), dove \" e l'ordinamento naturale diN, risulta 0=min(N), ma non esiste il massimo 3. nell'insieme ordinato (N ;j) dell'esercizio 1, si ha 1 =min(N ), ma non esiste il massimo diN 4. considerando il sottoinsiemeX=f2;3;9;18gcome sottoinsieme dell'insieme ordinato (N ;j), esistemax(X) = 18 ma non esiste il minimo diX Denizione 10.Siano (A;) un insieme ordinato,XA,X6 =;. Un elementoy2A si diceminorantediXse (8x2X)(yx): Denizione 11.Siano (A;) un insieme ordinato,XA,X6 =;. Un elementoy2A si dicemaggiorantediXse (8x2X)(xy): Osservazione 7.Siano (A;) un insieme ordinato,XA,X6 =;. Si osservi che seX ha il minimo (rispettivamente il massimo), esso e sicuramente un minorante (rispettiva- mente un maggiorante), ma in generale un minorante (rispettivamente un maggiorante) non e un minimo (rispettivamente un massimo) perche non appartiene aX. 4 Denizione 12.SiaAinsieme, naturalmente non vuoto,Rrelazione suA. Si dice che Re unarelazione di equivalenzase eri essiva, simmetrica e transitiva. Esercizio 2.Sono di equivalenza le seguenti relazioni: (1)R=f(; );( ; );( ; );(; );( ; )gsull'insiemeA=f;  ; g (2)R0 =f(n; m)2ZZ: 2j(nm)g (3)R00 =f(a; b)2ZZ:a2 =b2 g (4)R000 =f(x; y)2Z Z :x
y >0g. Esercizio 3.SianoAun insieme non vuoto,f:A!Bun'applicazione. La relazione Rfcos denita: 8x; y2A(x; y)2 R f, f(x) =f(y) e una relazione di equivalenza. Denizione 13.SianoAun insieme,A=fA i: i2Igun sottoinsieme dell'insieme P(A) delle parti diA. Si dice unione degli elementi diAo unione degliA i, i2I, l'insieme[ i2IA i:= fa2A:9i2Itale chea2A ig Osservazione 8.Ovviamente si ha [ i2IA i A;8j2I ; A j[ i2IA i Denizione 14.SianoAun insieme,Runa relazione di equivalenza suA,a2A. Si diceclasse di equivalenza diail sottoinsieme diA: [a] R= fx2A: (a; x)2 Rg: Esempio 10.Considerata sull'insiemeA=fa; b; c; dgla relazione di equivalenza R1= f(a; a)(b; b);(c; c)(d; d);(a; b)(b; a);(a; c);(c; a);(b; c);(c; b)g si ha: [a] R1= [ b] R1= [ c] R1= fa; b; cg; [d] R1= fdg: Esempio 11.Sia  l'insieme delle rette di un piano ssato eEla relazione su  cos denita: per ognir; s2, (r; s)2 E ,re parallela as: Sapendo che ogni retta e parallela a se stessa, si si vede subito cheEe una relazione di equivalenza. Inoltre ssata una rettar, la sua classe di equivalenza e [r] E= insieme di tutte le rette parallele a r : Esempio 12.Nell'insieme  dell'Esempio 11, la perpendicolarita tra rette non e una relazione di equivalenza: infatti non e ri essiva ne' transitiva. Proposizione 2.SianoAun insieme,Runa relazione di equivalenza suA. Al lora si ha: (1) (8a2A) ([a] R6 =;) (2) (8a; b2A) ((a; b)= 2 R ()[a] R\ [b] R= ;) (3) (8a; b2A) ((a; b)2 R ()[a] R= [ b] R) (4)S a2A[ a] R= A: Dimostrazione.(1) discende subito dalla ri essivita: infatti 8a2A;(a; a)2 R=)a2[a] R Per provare (2), si considerinoa; b2Ain modo che (a; b)= 2 R. Usando la tecnica di dimostrazione per assurdo, si suppone che esistac2[a] R\ [b] R. Allora, per la denizione 5 di classe di equivalenza, risulterebbe: (a; c)2 R ^(b; c)2 Re quindi, per la simmetria diR(a; c)2 R ^(c; b)2 Rda cui, per la transitivita diR, (a; b)2 R, in contraddizione con (a; b)= 2 R. Viceversa, se [a] R\ [b] R= ;, non puo essere (a; b)2 R, altrimentia2[a] R\ [b] R, e risulterebbe [a] R\ [b] R6 =;. Per dimostrare (3), si considerinoa; b2A, con (a; b)2 R. Poiche si deve provare che i due insiemi [a] Re [ b] Rcoincidono, si dimostrano le due inclusioni: [a] R [b] R^ [b] R [a] R: Siax2[a] R; questo vuol dire che ( a; x)2 R. Pero anche (a; b)2 Re quindi, per la simmetria, (b; a)2 R. Per la transitivita diR, (b; x)2 Re cio signica chex2[b] R, pertanto [a] R [b] R. L'inclusione [ b] R [a] Rsi prova nella stessa maniera. Viceversa, se [a] R= [ b] R, allora a2[a] R= [ b] Re quindi ( a; b)2 R. Inne per l'Osservazione 8, si ha[ a2A[ a] R A: Per provare l'altra inclusione, si ssix2A; per (1),x2[x] Re quindi x2[ a2A[ a] R: Pertanto le due inclusioni sono vericate e quindi vale (4). Denizione 15.SianoAun insieme,Runa relazione di equivalenza suA. L'insieme A=R=f[a] R: a2Ag si chiamainsieme quoziente diAperR. Denizione 16.SianoAun insieme,A=fA i: i2Igun sottoinsieme (non vuoto) dell'insiemeP(A) delle parti diA. Si dice cheAe unapartizionese  8i2I ; A i6 =;  8i; j2I ; i6 =j; A j\ A j= ; S i2IA i= A. Osservazione 9.SiaAun insieme,Runa relazione di equivalenza suA. Per la Propo- sizione 2, sicuramente l'insieme quoziente diArispetto ad una relazione di equivalenza Re una partizione. Si puo vericare anche il viceversa: siaA=fA i: i2Iguna partizione sull'insiemeA. Si denisce la relazioneRnel modo che segue: (a; b)2 R () 9i2Itale chea; b2A i: Si prova cheRe di equivalenza e cheA=R=A: