relacoes de equivalencia

Prévia do material em texto

UFGD
SISTEMAS DE INFORMAC¸A˜O
Disciplina: Matema´tica Discreta
Professor : Lino Sanabria
Relac¸o˜es de Equivaleˆncia
1 Preliminares
Definic¸a˜o .1 : Dado um conjunto A, definimos o conjunto das partes de A, como sendo
℘(A) := {B
∣∣∣B ⊂ A},
o conjunto dos subconjuntos de A.
Exerc´ıcio .2 Determtine ℘(A) nos seguintes casos:
1. A = ∅
2. A = {a}
3. A = {a, b}
4. A = {a, b, c}
5. A = {{a, b}, c}
6. A = {{a, c}, c}
Definic¸a˜o .3 Dados conjuntos A e B definimos o produto cartesiano de A por B, pondo:
A×B := {(x, y)
∣∣∣x ∈ A e y ∈ B},
1
Exerc´ıcio .4 Sejam A = {1, 2} e B = {a, b}. Determine:
1. A×B
2. ℘(A×B)
3. ℘(A) e ℘(B)
4. ℘(A)× ℘(B)
Notac¸a˜o .5 Denotaremos por #A o nu´mero de elementos do conjunto A, sempre que A for
um conjunto finito.
Proposic¸a˜o .6 Seja A um conjunto finito. Enta˜o:
• #℘(A) = 2#A
• #A× A = (#A)2
Exerc´ıcio .7 Seja A um conjunto finito. Quantos sa˜o os subconjuntos de A× A ?
2 Relac¸o˜es
Definic¸a˜o .8 Uma relac¸a˜o em um conjunto A na˜o vazio, e´ qualquer subconjunto de A× A.
Exemplo .9 Se A = {a}, enta˜o A×A = {(a, a)}. Segue da´ı que existem apenas duas relac¸o˜es
em A, a saber:
R0 = ∅ e R1 = {(a, a)}.
Exemplo .10 Sendo A = {0, 1}, temos A × A = {(0, 0), (0, 1), (1, 0), (1, 1)}, e da´ı os seus
subconjuntos sa˜o:
R0 = ∅ R1 = {(0, 0)} R2 = {(0, 1)} R3 = {(1, 0)}
R4 = {(1, 1)} R5 = {(0, 0), (0, 1)} R6 = {(0, 0), (1, 0)} R7 = {(0, 0), (1, 1)}
R8 = {(0, 1), (1, 0)} R9 = {(0, 1), (1, 1)} R10 = {(1, 0), (1, 1)} R11 = {(0, 0), (0, 1), (1, 0)}
R12 = {(0, 0), (0, 1), (1, 1)} R13 = {(0, 0), (1, 0), (1, 1)}
R14 = {(0, 1), (1, 0), (1, 1)} R15 = {(0, 0), (0, 1), (1, 0), (1, 1)}
2
Notac¸a˜o .11 Quando (x, y) ∈ R dizemos que x esta´ relacionado com y e escrevemos xRy.
Caso contra´rio, escrevemos x
∣∣∣Ry.
Exemplo .12 Continuac¸a˜o do exemplo 1.10.
1. (1, 1) ∈ R4, logo podemos escrever 1 R41.
2. (1, 1) /∈ R8, logo podemos escrever 1
∣∣∣R
8
1.
Observac¸a˜o .13 (Sobre especif´ıcac¸a˜o de conjuntos) Lembrando que A = {0, 1}, podemos es-
pecif´ıcar o conjunto R8 de va´rios modos, a saber:
R8 = {(0, 1), (1, 0)} = {(x, y) ∈ A × A
∣∣∣x + y = 1} = {(x, y) ∈ A × A∣∣∣x + y e´ ı´mpar} =
= {(x, y) ∈ A× A
∣∣∣x 6= y}
Observe ainda que poderiamos ter, solicitado o conjunto R8, atrave´s da relac¸a˜o, isto e´,
dizendo xR8y ⇐⇒ x+ y = 1.
Exerc´ıcio .14 Seja A um conjunto finito. Quantas sa˜o as relac¸o˜es em A ?
Exerc´ıcio .15 Sejam A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} e R = {(x, y)
∣∣∣x|y}. Responda se e´ falso
ou verdadeiro. Justifique sua resposta.
1. 2R3
2. 3R6
3. 4R10
4. 8R8
5. 1Rx, [∀x, x ∈ A]
6. 2Rx, [∀x, x ∈ {2, 4, 6, 8}]
Exerc´ıcio .16 Sejam A = Z e R = {(x, y)
∣∣∣x ≤ y}. Responda se e´ falso ou verdadeiro.
Justifique sua resposta.
1. {(x, x)
∣∣∣x ∈ Z} ⊆ R
3
2. {(x, x+ 1)
∣∣∣x ∈ Z} ⊆ R
3. xRx, [∀x, x ∈ Z]
4. Existe (x, y) ∈ R tal que (y, x) ∈ R.
Definic¸a˜o .17 Uma relac¸a˜o R, em um conjunto A, e´ reflexiva se:
(x, x) ∈ R, para todo x ∈ A
Definic¸a˜o .18 Uma relac¸a˜o R, em um conjunto A, e´ sime´trica se:
(y, x) ∈ R, sempre que (x, y) ∈ R
Definic¸a˜o .19 Uma relac¸a˜o R, em um conjunto A, e´ transitiva se:
(x, z) ∈ R, sempre que (x, y) ∈ R e (y, z) ∈ R
Definic¸a˜o .20 Uma relac¸a˜o R, em um conjunto A, e´ dita relac¸a˜o de equivaleˆncia se for
reflexiva, sime´trica e transitiva.
Exerc´ıcio .21 Para as relac¸o˜es no conjunto A = {0, 1}, dadas anteriormente, determine
quais sa˜o:
• Reflexivas.
• Sime´tricas.
• Transitivas.
• Reflexivas e Sime´tricas.
• Reflexivas e Transitivas.
• Sime´tricas e Transitivas.
• Relac¸o˜es de equivaleˆncia.
4
Exerc´ıcio .22 A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Seja R = {(a, b) ∈ A × A
∣∣∣a e´ divis´ıvel por b}.
Pergunta-se :
• R e´ reflexiva?
• R e´ sime´trica?
• R e´ transitiva?
• Relac¸a˜o de equivaleˆncia?
Definic¸a˜o .23 Seja R uma relac¸a˜o de equivaleˆncia em um conjunto A, definimos a classe
de um elemento a ∈ A, e denotamos por a, como sendo o conjunto dos elementos de A que se
relacionam com a, isto e´:
a := {b ∈ A
∣∣∣bRa}
Exemplo .24 A = Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . . }. Defina uma relac¸a˜o em A, da seguinte
forma: aRb ⇐⇒ 7|b− a
1. Verifique que R e´ uma relac¸a˜o de equivaleˆncia.
(a) R e´ reflexiva. xRx, para todo x ∈ Z, pois 7|x− x.
(b) R e´ sime´trica. Se xRy, enta˜o 7|x− y, logo, 7|y − x e portanto yRx
(c) R e´ transitiva. Se xRy e yRz, enta˜o 7|x − y e 7|y − z, logo, 7|x − y + y − z, ou
seja 7|x− z e portanto xRz
2. a := {b ∈ A|bRa} = {b ∈ A|b− a e´ mu´ltiplo de 7}. Mostre que a := {a+ 7n|n ∈ A}.
x ∈ a ⇐⇒ xRa ⇐⇒ x− a = 7n, para algum n ⇐⇒ x = a+ 7n, para algum n ⇐⇒
x ∈ {a+ 7n|n ∈ A}.
3. Segue do item anterior que A/∼ = {a|a ∈ A} = {0, 1, 2, 3, 4, 5, 6}, que denotamos por Z7.
4. Defina a+ b := a+ b e a · b := a · b
5. Resolva a equac¸a˜o 5x+ 3 = 6 em Z7.
5
Congrueˆncias
No´s ja´ sabemos que a soma de dois nu´meros pares, ou dois nu´meros ı´mpares, e´ par, e a
soma de um nu´mero par com um nu´mero ı´mpar e´ ı´mpar, podemos representar isto atrave´s de
uma tabela, da seguinte forma:
+ p i
p p i
i i p
De modo analogo, temos, para o produto:
· p i
p p p
i p i
Estas observac¸o˜es elementares sa˜o suficientes para responder a questo˜es na˜o triviais, por
exemplo:
Questa˜o: Existe soluc¸a˜o inteira para a equac¸a˜o x5 + 11111x+ 111 = 0 ?
Dado um nu´mero inteiro a, este sera´ par ou ı´mpar. Se a for par, enta˜o a5 + 11111a+ 111
sera´ ı´mpar. Se a for ı´mpar, tambe´m a5 + 11111a+ 111 sera´ ı´mpar. Portanto a equac¸a˜o acima
na˜o possui soluc¸a˜o inteira.
Este tipo de argumento pode ser generalizado, com a introduc¸a˜o do conceito de congrueˆncia.
Seja N um inteiro maior do que 1.
Definic¸a˜o: a ≡ b(mod N) ⇐⇒ N | a− b.
a ≡ b mod N leˆ-se “a e´ congruente a b mo´dulo N”.
Exemplos:
3 ≡ 1 (mod 2) pois 2 | 3− 1
8 6≡ 3 (mod 2) pois 2|6 8− 3
27 ≡ 3 (mod 8) pois 8 | 27− 3
6
Observe que a e´ congruente a b mo´dulo N se a− b for mu´ltiplo de N.
Afirmo: Se a ≡ b (mod N) enta˜o o resto da divisa˜o de a por N e´ igual ao resto da divisa˜o
de b por N.
Prova Pelo algoritmo da divisa˜o, temos:
a = q1N + r1 e b = q2N + r2, onde 0 ≤ r1 ≤ N e 0 ≤ r2 ≤ N . Podemos supor que r1 ≥ r2,
da´ı a− b = (q1− q2)N + (r1− r2), como 0 ≤ r1− r2 ≤ N , segue da unicidade, no algoritmo da
divisa˜o, que r1 − r2 e´ o resto da divisa˜o de a − b por N . Por outro lado, sabemos que a − b e´
divis´ıvel por N, portanto r1 = r2.
Observac¸a˜o 1: Todo nu´mero inteiro a e´ congruente a si mesmo mo´dulo N, pois N | a− a.
Observac¸a˜o 2: Se a e´ congruente a b mo´dulo N, enta˜o b e´ congruente a a mo´dulo N, pois
se a− b e´ divis´ıvel por N, b− a tambe´m o e´.
Observac¸a˜o 3: A congrueˆncia e´ transitiva, isto e´, se a ≡ b (mod N) e b ≡ c (mod N), enta˜o
a ≡ c (mod N). De fato, segue da definic¸a˜o que N | a− b e N | b− c, logo N | (a− b) + (b− c),
isto e´, N | a− c.
Resumindo:
1. a ≡ a (mod N), para todo inteiro a
2. Se a ≡ b (mod N) enta˜o b ≡ a (mod N)
3. Se a ≡ b (mod N) e b ≡ c (mod N), enta˜o a ≡ c (mod N)
Agora a discussa˜o inicial sobre operac¸o˜es com nu´meros pares e ı´mpares pode ser reformulada
em termos de congrueˆncia (mod 2). Dado um nu´mero inteiro a, se a e´ par, enta˜o a = 2n, logo
2 | 2n − 0, portanto a ≡ 0 (mod 2), e se a e´ ı´mpar, enta˜o a = 2n + 1, logo 2 | (2n + 1) − 1,
portanto a ≡ 1 (mod 2).
Tome a = 38731431 e b = 25538, como a e´ par e b e´ ı´mpar, temos:
a ≡ 1 (mod 2) e
b ≡ 0 (mod 2)
Apenas lembrando da tabela do in´ıcio e que a e´ par e b e´ ı´mpar, podemos concluir que:
a+ b ≡ 1 + 0 (mod 2) e
a · b ≡ 1 · 0 (mod 2).
7
Este exemplo sugere que podemos operar elementos congruentes de modo analogo ao que
fazemos com igualdades, de fato, temos o seguinte:
Teorema Se a ≡ x (mod N) e b ≡ y (mod N), enta˜o:
1. a+ b ≡ x+ y (mod N)
2. a · b ≡ x · y (mod N)
Demonstrac¸a˜o:
1. Porhipo´tese N | a−x e N | b−y, portanto N | (a−x)+(b−y), isto e´, N | (a+b)−(x+y),
ou seja, a+ b ≡ x+ y (mod N).
2. N divide qualquer combinac¸a˜o linear de (a−x) e (b−y), em particular, divide a·b−x·y =
b · (a− x) + x · (b− y)
Aplicac¸a˜o: ( Em pequenos passos )
1. E´ claro que 10 ≡ 1 (mod 9).
2. Enta˜o, pelo teorema, 10 · 10 ≡ 1 · 1 (mod 9), isto e´, 102 ≡ 1 (mod 9).
3. Por induc¸a˜o podemos concluir que 10n ≡ 1 (mod 9), ∀n ∈ IN .
4. Se um nu´mero a e´ da forma an · 10n enta˜o a ≡ an · 1 (mod 9), isto e´ a ≡ an (mod 9).
5. Exemplo:
a = 8000000 = 8 · 106, logo, a ≡ 8 (mod 9).
b = 6000 = 6 · 103, logo, b ≡ 6 (mod 9).
8006000 = a+ b ≡ 8 + 6 (mod 9), isto e´, 8006000 ≡ 8 + 6 (mod 9)
6. Generalizando:
Seja a = an · 10n + an−1 · 10n−1 + · · · + a1 · 101 + a0, enta˜o, segue do teorema e das
observac¸a˜oes acima que:
an · 10n + an−1 · 10n−1 + · · ·+ a1 · 101 + a0 ≡ an + an−1 + · · ·+ a1 + a0 (mod 9).
7. Conclusa˜o: um nu´mero inteiro e´ congruente mo´dulo 9 a soma dos seus d´ıgitos (na
base 10).
8
8. Exemplo: 355431 = 3 · 105 + 5 · 104 + 5 · 104 + 4 · 103 + 3 · 10 + 1
Logo 355431 ≡ 3 + 5 + 5 + 4 + 3 + 1 (mod 9). Isto e´ 355431 ≡ 21 (mod 9).
9. Continuando. Pelo mesmo motivo...
21 ≡ 2 + 1 (mod 9), istoe´ 355431 ≡ 3 (mod 9).
9