Classe de equivalencia e partição de um conjunto

Prévia do material em texto

CLASSE DE EQUIVALEˆNCIA E
PARTIC¸A˜O DE UM CONJUNTO
Diego Lu´ıs
9 de setembro de 2015
Suma´rio
1 Relac¸a˜o de Equivaleˆncia 3
2 Classe de Equivaleˆncia 4
3 Partic¸a˜o de um conjunto 5
4 Refereˆncia 7
2
1 Relac¸a˜o de Equivaleˆncia
Definic¸a˜o 1 Uma relac¸a˜o R sobre um conjunto E na˜o vazio e´ chamado de
relac¸a˜o de equivaleˆncia sobre E se, e somente se, R e´ reflexiva, sime´trica e
transitiva. Ou seja, R deve cumprir, respectivamente, as seguintes proprie-
dades:
(i): se x ∈ E, enta˜o xRx;
(ii): se x, y ∈ E e xRy enta˜o yRx;
(iii): se x, y, z ∈ E, xRy e yRz enta˜o xRz.
Exemplo 1 A relac¸a˜o de igualdade sobre R e´ uma relac¸a˜o de equivaleˆncia,
pois:
(i): ∀x ∈ R⇒ x = x;
(ii): ∀x, y ∈ R, x = y ⇒ y = x;
(iii): ∀x, y, z ∈ R, x = y e y = z ⇒ x = z.
Exemplo 2 A relac¸a˜o de paralelismo definida para as retas de um espac¸o
E euclidiano e´ uma relac¸a˜o de equivaleˆncia, pois sendo x,y e z retas de E,
tem-se :
(i): x//x;
(ii): x//y ⇒ y//x;
(iii): x//y e y//z ⇒ x//z.
Exemplo 3 A relac¸a˜o de congrueˆncia mo´dulo m, em que m ∈ Z e m > 1,
sobre Z e´ uma relac¸a˜o de equivaleˆncia, pois:
(i): ∀x ∈ Z⇒ x ≡ x(mod m);
(ii): ∀x, y ∈ Z, x ≡ y(mod m)⇒ y ≡ x(mod m)
(ii): ∀x, y, z ∈ Z, x ≡ y(mod m) e y ≡ z(mod m) ⇒ x ≡ z(mod m)
3
2 Classe de Equivaleˆncia
Definic¸a˜o 2 Seja R uma relac¸a˜o de equivaleˆncia sobre E. Dado a, com
a ∈ E, chama-se classe de equivaleˆncia determinada por a, mo´dulo R(ou
segundo R), o subconjunto a¯ ⊂ E constituido pelos elementos x tais que xRa:
a¯ = {x ∈ E | xRa}
Ou seja, a¯ e´ um subconjunto de E onde nele esta´ contido todos os elementos
x que tem uma relac¸a˜o de equivaleˆncia R com o elemento a.
Propriedade 1 Em cada subconjunto a¯ ⊂ E, todos os seus elementos sa˜o
equevalentes entre s´ı.
Propriedade 2 Se xRy ⇒ x¯ = y¯;
Propriedade 3 Dado a¯ e b¯ classes de equivaleˆncia, Se a¯ 6= b¯⇒ a¯⋂ b¯ = ∅;
Propriedade 4 A unia˜o de todas as classes de equivaeˆncia de um conjunto
e´ igual ao pro´prio conjunto: X =
⋃
∀x∈X x¯
Exemplo 4 Tome X um subconjunto de Z em que todos os seus elementos
sa˜o congruentes mo´dulo 5. Definamos a classe de equivaleˆncia a¯ de tal forma
que a¯ = {x ∈ Z |x ≡ a mod 5}. Enta˜o:
0¯ = {x ∈ Z |x ≡ 0 mod 5} = {0,±5,±10,±15, ...};
1¯ = {x ∈ Z |x ≡ 1 mod 5} = {...,−9,−4, 1, 6, 11, ....};
2¯ = {x ∈ Z |x ≡ 2 mod 5} = {...,−8,−3, 2, 7, 12, ...};
3¯ = {x ∈ Z |x ≡ 3 mod 5} = {...,−7,−2, 3, 8, 13, ...};
4¯ = {x ∈ Z |x ≡ 4 mod 5} = {...,−6,−1, 4, 9, 14, ...};
Note que cada umas das classes acima e´ diferente uma das outras e que
a unia˜o dessas classes resulta no conjunto Z, ou seja, 0¯∪ 1¯∪ 2¯∪ 3¯∪ 4¯∪ = Z.
4
3 Partic¸a˜o de um conjunto
Definic¸a˜o 3 Seja E um conjunto na˜o vazio diz-se que uma classe X de sub-
conjuntos na˜o vazios de E e´ uma partic¸a˜o de E se, e somente se:
• Dois membros quaisquer de X ou sa˜o iguais ou sa˜o disjuntos;
• A unia˜o dos membros de X e´ igual a E.
Definic¸a˜o 4 Uma partic¸a˜o de um conjunto X e´ uma colec¸a˜o X1, X2, ..., Xk
de subconjuntos na˜o vazios de X tal que cada elemento de X pertence a um
e apenas um Xi. Cada Xj e´ um elemento ou bloco da partic¸a˜o. (n ao ´e
correto dizer que ”Xj e´ uma partic¸a˜o”e que ”Xj e´ uma das partic¸o˜es”.) Se
k = 2, diz-se que a partic¸a˜o e´ uma bipartic¸a˜o. (IME-USP)
Exemplo 5 X={{1},{2,3},{4}} e´ uma partic¸a˜o do conjunto E={1,2,3,4}
Exemplo 6 Sejam:
P = {x ∈ Z|x e´ par}
I = {x ∈ Z|x e´ impar}
Enta˜o X={P,I} e´ uma partic¸a˜o de Z.
Proposic¸a˜o 1 Se R e´ uma relac¸a˜o de equivaleˆncia sobre o conjunto E, enta˜o
E/R e´ uma partic¸a˜o do conjunto E.
prova: A notac¸a˜o E/R pode ser entendida como uma partic¸a˜o do conjunto
E estabelecida por uma relac¸a˜o R. Ou seja, a relac¸a˜o R e´ a caracter´ıstica que
particiona o conjunto E.
Partindo da definic¸a˜o 3 devemos mostrar que dados a¯, b¯ ∈ E/R eles sa˜o
na˜o vazios e sa˜o iguais ou disjuntos:
Seja a ∈ E/R enta˜o aRa e a ∈ a¯ logo a¯ 6= ∅, analogamente temos b¯ 6= ∅.
Suponha que y = a¯ ∩ b¯, enta˜o y ∈ a¯ e y ∈ b¯ da´ı yRa e yRb, como R e´ uma
relac¸a˜o sime´trica enta˜o aRy e yRb, portanto pela definic¸a˜o 1 item (iii) tem-
pos que aRb, da´ı concluimos pela propriedade 2 que a¯ = b¯. Caso ∅ = a¯ ∩ b¯,
de forma trivial podemos concluir que a¯ e b¯ sa˜o disjuntos.
Agora provemos que a unia˜o dos membros de E/R e´ igual a E:
A definic¸a˜o de classe de equivaleˆncia nos garente que para cada a ∈ E temos
a¯ ⊂ E, enta˜o ∪a∈E a¯ ⊂ E.
5
para todo elemento x qualquer em E, sabe-se que xRx e x ∈ x¯, da´ı temos
que x¯ ⊂ ∪a∈E a¯ o que nos leva a concluir que x ∈ ∪a∈E a¯, portanto E ⊂ ∪a∈E a¯.
de ∪a∈E a¯ ⊂ E e E ⊂ ∪a∈E a¯ so´ podemos concluir que ∪a∈E a¯ = E.
Proposic¸a˜o 2 Se X e´ uma partic¸a˜o do conjunto E, enta˜o existe uma relac¸a˜o
R de equivaleˆncia sobre E tal que E/R=X.
prova: Para fins desta demonstrac¸a˜o, podemos definir uma relac¸a˜o R sobre
E da seguinte maneira: aRb⇐⇒ ∃A ⊂ X|{a, b} ⊂ A.
Para mostrar que R e´ uma relac¸a˜o de Equivaleˆncia basta mostras os treˆs
itens da definic¸a˜o 1, vejamos:
(i): para todo a ∈ A temos a ∈ E pois A ⊂ X ⊂ E, e ainda a ∈ X o
que conclui que aRa.
(ii): tome dois elementos a, b ∈ E tais que aRb, enta˜o a, b ∈ A ⊂ X. Sabe-
mos que a, b ∈ A e´ equivalente a dizer que b, a ∈ A portanto, logicamente bRa.
(iii): Sejam a,b,c elementos quais quer de E, tais que aRb e bRc, tome os
conjuntos A e B pertencentes a X de modo que a, b ∈ A e b, c ∈ B ou seja
y ∈ A ∩ B. Conclu´ımos pela definic¸a˜o 3 que A=B, sendo assim a e c sa˜o
elementos de um mesmo subconjunto contido em X, portanto aRc.
Enta˜o, com esses intens verificados, mostramos que R e´ uma relac¸a˜o de
equivaleˆncia.
6
4 Refereˆncia
DOMINGUES, H. H; IEZZI, G. Algebra Moderna. Sa˜o Paulo: Atual,
2003.
Classe de Equivaleˆncia
Dispon´ıvel em<https://pt.wikipedia.org/wiki/Classe de equivaleˆncia>
Acesso em 06 de setembro de 2015.
Partic¸a˜o de um conjunto
Dispon´ıvel em <http://www.ime.usp.br/ pf/algoritmos para grafos/aulas
/footnotes/partition.html>. Acesso em 06 de setembro de 2015.
7