Relação de Equivalência

Relação de Equivalência

1. RELAÇÃO DE ORDEM PACIAL

   • Seja R uma relação binária em A. Dizemos que R é uma relação de ordem parcial se for: a . R é reflexiva b. R é antissimétrica c. R é transitiva
     • Sejam A = R e R = { (x, y) ∈ R × R, : x ≤ y }. R é reflexiva sobre A pois (∀x ∈ R) x ≤ x logo (∀x ∈ R) xRx. R é transitiva pois (∀x, y, z ∈ R) ((x ≤ y ∧ y ≤ z) → x ≤ z)). Portanto (∀x, y, z ∈ R) (xRy ∧ yRz) → xRz . R é anti-simétrica pois (∀x, y ∈ R) (x ≤ y ∧ y ≤ x) → x = y. Portanto (∀x, y ∈ R) (xRy ∧ yRx) → x = y
   • se R é uma relação de ordem parcial em A dizemos que A é Parcialmente ordenado por R.

2. RELAÇÃO DE ORDEM TOTAL

   • Definição: Uma relação R é uma ordem total sobre um conjunto A (ou ordem linear) se, e somente se R é uma relação de ordem sobre A e quaisquer dois elementos de A são comparáveis por R.
     • Portanto uma relação de ordem R é total se, quaisquer que sejam a e b em A, (a, b) ∈ R ou (b, a) ∈ R. Se R é uma relação de ordem total sobre A, o par (A,R) é chamado de conjunto totalmente ordenado
       • Dizemos que uma relação de ordem parcial R sobre o conjuto A é uma relação de ordem total.
         • aRa ou bRa, para todo a,b ∈ A ( lei da dicotomia)

3. seja R uma relação binária em A. Dizemos que R é uma relação de equivalência se ela for ao mesmo tempo reflexiva, simétrica e transitiva.

   • se R é uma relação de equivalência em A definimos a classe de equivalência de um elemento a ∈ A denotada por [a]= { x ∈ A; (a, b) ∈ R}.
     • A coleção das classes de equivalência dos elementos de A denotada por A/R= {[a]; a ∈ A}.
   • Como a relação R é reflexiva, simétrica e transitiva
     • 2= { x ∈ A: (2,x) ∈ R}= {x ∈ A; 3\(x-2)} = {2,5,8}, 3 ={ x ∈ A: (3,x) ∈ R}= {x ∈ A; 3\(x-3)} = {3,6}, 4={ x ∈ A: (4,x) ∈ R}= {x ∈ A; 3\(x-4} = {4,7}, 5={ x ∈ A: (5,x) ∈ R}= {x ∈ A; 3\(x-5} = {2,5,8},6={ x ∈ A: (6,x) ∈ R}= {x ∈ A; 3\(x-6} = {3,6}7={ x ∈ A: (7,x) ∈ R}= {x ∈ A; 3\(x-7} = {4,7}8={ x ∈ A: (8,x) ∈ R}= {x ∈ A; 3\(x-8} = {2,5,8}
     • EQ A e [a]
       • a. Para todo a ∈ A, a ∈ [a] b.[a]=[b] se, e somente se (a ,b) ∈ R c. Se [a] ≠ [b], então [a] e [b] são disjuntas . d. U [a]= A
     • Z= {0,1,...m-1} e Z =0 U1 U...U m-1
       • aRb ⇔xa=Xb