Notas de aula Unidade 5

Prévia do material em texto

Unidade 5 - Relações
Definição 2.1. Se A e B são conjuntos, uma relação R de A em B é um subconjunto do
produto cartesiano A × B. Se (a, b) ∈ R, escrevemos aR b e dizemos que a está relacionado
com b. Se (a, b) /∈ R, escrevemos a /R b
No caso particular em que A = B, ou seja R ⊆ A×A, em vez de dizer que R é uma relação
de A em A, podemos dizer simplesmente que R é uma relação em A. Mais precisamente,
dizemos que R é uma endorrelação de A.
Exemplo 2.2. Vejamos alguns exemplo de relações.
1) Se A = {a, b, c} e B = {0, 1}, a relação R = {(a, 0), (b, 0), (c, 1)} pode ser representada
pelo diagrama
c r
b r
a r
���
��:
���
��:
XXXXXz
r 1
r 0
e também pela tabela
R 0 1
a ×
b ×
c ×
2) Se A = B = {1, 2, 3, 4}, temos |A×B| = 16. Um exemplo de relação de A em B é
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}.
Note que vale a proposição (∀m ∈ A)(∀n ∈ A)(mRn ←→ m ≤ n). Por isso, nesta situação
podemos dizer que R é a relação de ≤ em A.
3) Se A é um conjunto qualquer e se B = ℘(A) é o conjunto das partes de A, definimos uma
relação RA de A em ℘(A) dizendo que um par (x, S) ∈ RA ←→ x ∈ S, isto é,
xRA S ←→ x ∈ S.
Por exemplo, se A = {u, v}, temos ℘(A) = {∅, {u}, {v}, {u, v}}, de forma que
RA =
{
(u, {u}), (u, {u, v}), (v, {v}), (v, {u, v})
}
.
4) Seja A = {2, 3, 4, 5, 6} e consideremos em A a relação R definida por
xR y ⇐⇒ x | y.
Duas maneiras de representar R são
r6 6
r5 5
r4 4
r3 3
r2 2
rr
rr
r-
Z
Z
Z
Z
Z
Z
Z~
HH
HHH
HHj
@
@
@
@
@
@
@R
-
-
-
-
R 2 3 4 5 6
2 × × ×
3 × ×
4 ×
5 ×
6 ×
1
Observação. O diagrama da esquerda na linha acima lembra uma função, mas não é uma
função porque do elemento 2 partem três flechas e do elemento 3 partem duas flechas. Isso dá
a ideia de que toda função é uma relação, embora nem toda relação seja uma função. Vamos
tornar essa ideia mais precisa. Vimos que se f : A→ B é uma função, o gráfico de f
G(f) = {(x, f(x)) | x ∈ A}
é um subconjunto do produto cartesiano A×B, logo é uma relação de A em B. Identificando
f com G(f), podemos dizer que toda função f : A→ B é um caso particular de relação R de
A em B em que
(∀x ∈ A)(∃!y ∈ B)(xR y).
A nomenclatura conhecida das propriedades das funções pode ser estendida às relações,
como segue.
Definição 2.3. Sejam A e B conjuntos e R ⊆ A×B uma relação. Dizemos que o subconjunto
Dom(R) := {a ∈ A | ∃ b ∈ B, (a, b) ∈ R} de A é o domı́nio de R e que o subconjunto
Im(R) := {b ∈ B | ∃ a ∈ A, (a, b) ∈ R} de B é a imagem de R. Dizemos que R é uma relação
• total se (∀ a ∈ A)(∃ b ∈ B) [(a, b) ∈ R], ou seja, se Dom(R) = A.
• sobrejetora se (∀ b ∈ B)(∃ a ∈ A) [(a, b) ∈ R], ou seja, se Im(R) = B.
• injetora se (∀ b ∈ B)(∀ a1 ∈ A)(∀ a2 ∈ A) [(a1, b) ∈ R ∧ (a2, b) ∈ R −→ a1 = a2].
• funcional se (∀ a ∈ A)(∀ b1 ∈ B)(∀ b2 ∈ B) [(a, b1) ∈ R ∧ (a, b2) ∈ R −→ b1 = b2].
Observe que uma relação funcional total é o gráfico de uma função.
No Exemplo 1 acima, Dom(R) = {a, b, c} = A, logo R é total, Im(R) = {0, 1} = B, logo R
é sobrejetora mas, como (a, 0) ∈ R, (b, 0) ∈ R e a 6= b, temos que R não é injetora. E como a,
b e c só estão relacionados com um único elemento de B, temos que R é funcional.
Já no Exemplo 2 acima temos: Dom(R) = {1, 2, 3, 4} = A = B = Im(R); logo R é total e
sobrejetora. Entretanto, como (1, 2) ∈ R e (1, 3) ∈ R e 2 6= 3 temos que R não é funcional e,
como (2, 4) ∈ R e (3, 4) ∈ R e 2 6= 3, temos que R não é injetora.
Verifique também que a relação do Exemplo 3 é total, mas não satisfaz as outras propri-
edades, enquanto que a relação do Exemplo 4 é total e sobrejetora, mas não é funcional nem
injetora.
Definição 2.4. Sejam A e B conjuntos e R ⊆ A × B uma relação. A relação inversa de R,
ou dual, denotada por R−1, é dada por
R−1 = {(b, a) ∈ B × A | (a, b) ∈ R}.
Note que R−1 ⊆ B × A e que qualquer relação, funcional ou não, tem relação inversa.
No Exemplo 2 acima, temos
R−1 = {(1, 1), (2, 1), (3, 1), (4, 1), (2, 2), (3, 2), (4, 2), (3, 3), (4, 3), (4, 4)}
2
e podemos dizer que R−1 é a relação de ≥ em A. No Exemplo 3 acima, temos
R−1 =
{
({u}, u), ({u, v}, u), ({v}, v), ({u, v}, v)
}
.
Como você descreveria essa relação?
O seguinte teorema pode ser demonstrado a partir da definição da relação inversa.
Teorema 2.5. Sejam R ⊂ A×B uma relação e R−1 a sua inversa. Vale que:
(a) (R−1)−1 = R.
(b) R é injetora se, e somente se, R−1 é funcional.
(c) R é sobrejetora se, e somente se, R−1 é total.
Operações com Relações
Uma relação de A em B é um subconjunto R ⊆ A × B e, portanto, as relações estão sujeitas
a todas as operações com conjuntos. Se R1 e R2 forem relações de A em B, então R1 ∪ R2,
R1 ∩R2, R1 −R2, R2 −R1 e R1 ⊕R2 também são relações de A em B.
Exemplo. Sejam R1 e R2 as relações em R definidas por
xR1 y ←→ x y.
Então
R1 ∪R2 = {(x, y) ∈ R2 | x 6= y}
R1 ∩R2 = ∅, R1 −R2 = R1, R2 −R1 = R2
R1 ⊕R2 = (R1 ∪R2)− (R1 ∩R2) = R1 ∪R2.
Definição 2.6. Se R for uma relação de A em B e S uma relação de B em C, definimos a
composta S ◦R como sendo o conjunto
S ◦R = {(a, c) ∈ A× C | ∃b ∈ B tal que (a, b) ∈ R e (b, c) ∈ S}.
Exemplo 2.7. Sejam A = {1, 2, 3}, B = {1, 2, 3, 4} e C = {a, b, c}
rr
r
���
��:
���
��:
XXXXXz
HHH
HHj r
rr
rXXXXXz
��
���:
XXXXXz
- r
r
ra
b
c
3
2
1
4
3
2
1
A B C
R = {(1, 1), (1, 2), (2, 4), (3, 3)} relação de A em B
S = {(1, a), (2, a), (2, b), (4, c)} relação de B em C
1 −→ 1 −→ a =⇒ 1 −→ a
1 −→ 2 −→ a =⇒ 1 −→ a
1 −→ 2 −→ b =⇒ 1 −→ b
2 −→ 4 −→ c =⇒ 2 −→ c
3 −→ 3
Logo S ◦R = {(1, a), (1, b), (2, c)}.
Propriedades de Endorrelações
As endorrelações, relações em que A = B, possuem várias propriedades e resultados impor-
tantes e interessantes, que serão apresentados a seguir.
3
Definição 2.8. Uma relação R em um conjunto A é dita reflexiva se (∀x ∈ A)(xRx).
Isso significa que uma relação R não é reflexiva se existe x ∈ A tal que (a, a) /∈ R.
Exemplo 2.9. No Exemplo 2.2, temos duas endorrelações, a saber, (2) e (4). Note que ambas
são reflexivas. Vejamos os seguintes exemplos adicionais:
1) A relação R em N definida por nRm←→ n ≤ m é reflexiva.
De fato, (∀n ∈ N)(n ≤ n).
2) A relação R em Z definida por nRm←→ n|S| = |T |.
Obviamente isso implica que |T | = |S|. Logo T RS.
3) Em A = {1, 2, 3, . . . , 10} a relação nRm ←→ n | m não é simétrica. Para justificar que é
falsa a proposição (∀n ∈ A)(∀m ∈ A)(nRm → mRn), temos que justificar que sua negação
é verdadeira. Mas essa negação é (∃n ∈ A)(∃m ∈ A)(nRm ∧m/Rn). Ou seja, precisamos dar
um contraexemplo. Sejam n = 1 e m = 2. Temos 1 | 2 e 2 - 1, isto é, 1R 2 e 2 /R 1. Logo a
relação não é simétrica.
Definição 2.13. Uma relação R em A é antissimétrica se (∀x, y ∈ A)(xR y∧yRx −→ x = y).
Isso significa que uma relação R não é antissimétrica se existem elementos x, y tais que
xR y, yRx e x 6= y.
4
Exemplo 2.14. As relações a seguir são antissimétricas.
1) A relação definida por xR y ←→ x ≤ y em Z é antissimétrica. De fato, se x ≤ y e y ≤ x,
então x = y.
2) A relação aR b←→ a | b em N é antissimétrica. De fato, se a | b e b | a, então a = b. Essa
relação não seria antissimétrica em Z, pois 1 6= −1, mas 1 | (−1) e (−1) | 1.
3) Se A é um conjunto qualquer, a relação S RT ←→ S ⊆ T em ℘(A) é antissimétrica. De
fato, se S ⊆ T e T ⊆ S, então S = T .
Definição 2.15. Uma relação R em A é transitiva se a proposição (∀x, y, z ∈ A)(xR y ∧
y R z −→ xR z) é válida.
Isso significa que uma relação R ⊆ A × A não é transitiva se existem x, y, z ∈ A tais que
xR y, yR z, mas x /R z.
Exemplo 2.16. As relações a seguir são transitivas.
1) A relação xR y ←→ x ≤ y em Z é transitiva.
De fato, se a ≤ b e b ≤ c, então a ≤ c.
2) Se A é um conjunto qualquer, a relação S RT ←→ S ⊆ T em ℘(A) é transitiva. De fato,
se S ⊆ T e T ⊆ V , então S ⊆ V .
3) Definimos uma relação no conjunto N2 = N × N por (a, b)R (c, d) ←→ a + d = b + c. R é
transitiva. De fato, suponhamos que (a, b)R (c, d) e (c, d)R (e, f). Então
a + d = b + c e c + f = d + e.
Somando essas duas igualdades, obtemos a + d + c + f = b + c + d + e. Cancelando c + d dos
dois lados, segue que a + f = b + e e, portanto, (a, b)R (e, f). Logo a relação R é transitiva.
Propriedades de Endorrelações
A seguir listamos alguns resultados envolvendo as propriedades das endorrelações e suas
inversas.
1. Uma relação R em um conjunto A é simétrica ⇐⇒ R−1 = R.
Mostraremos as duas implicações.
=⇒ Suponhamos que a seja simétrica. Mostraremos que R−1 ⊆ R e que R ⊆ R−1. Para
a primeira afirmação, seja (x, y) ∈ R. Como R é simétrica, (y, x) ∈ R. A definição de
inversa implica que (x, y) ∈ R−1, como queŕıamos demonstrar. Para a segunda afirmação,
seja (x, y) ∈ R−1, de forma que (y, x) ∈ R. Como R é simétrica, temos (x, y) ∈ R, como
queŕıamos demonstrar.
⇐= Suponhamos que R = R−1. Para mostrar que R é simétrica, sejam x, y ∈ A tais
que xR y, ou seja, (x, y) ∈ R. Por definição de inversa, (y, x) ∈ R−1. A hipótese R = R−1
implica que (y, x) ∈ R, como queŕıamos demonstrar.
2. Uma relação R em A é antissimétrica se e somente se R ∩ R−1 ⊆ ∆, onde ∆ = {(a, a) |
a ∈ A}.
Precisamos mostrar duas implicações.
5
=⇒ Suponhamos R antissimétrica. Vamos mostrar que R ∩R−1 ⊆ ∆.
Seja (a, b) ∈ R ∩ R−1. Por definição, (a, b) ∈ R−1 ⇐⇒ (b, a) ∈ R. Então (a, b) ∈ R e
(b, a) ∈ R. Mas R é antissimétrica. Segue que a = b. Então (a, b) = (a, a) ∈ ∆. Logo
R ∩R−1 ⊆ ∆.
⇐= Suponhamos que R ∩R−1 ⊆ ∆. Vamos mostrar que R é antissimétrica.
Se (a, b) ∈ R e (b, a) ∈ R, então (a, b) ∈ R e (a, b) ∈ R−1. Segue que (a, b) ∈ R ∩ R−1.
Então (a, b) ∈ ∆. Então a = b. Logo R é antissimétrica.
3. Uma relação R em A é transitiva se e somente se R2 = R ◦ R ⊆ R. Precisamos mostrar
duas implicações.
=⇒ Suponhamos R transitiva. Vamos mostrar que R◦R ⊆ R. Seja (a, c) ∈ R◦R. Pela
definição de composta de duas relações, ∃b ∈ A tal que (a, b) ∈ R e (b, c) ∈ R. Então,
pela transitividade, (a, c) ∈ R. Logo R ◦R ⊆ R.
⇐= Suponhamos que R ◦R ⊆ R. Vamos mostrar que R é transitiva. Suponhamos que
a, b, c ∈ A com aR b e bR c. Então (a, b) ∈ R e (b, c) ∈ R. Pela definição de composição,
(a, c) ∈ R ◦ R. Por hipótese, R ◦ R ⊆ R. Portanto (a, c) ∈ R, ou seja, aR c. Logo R é
transitiva.
Representações de uma Relação
Vimos acima que uma relação entre conjuntos finitos pode ser representada através de
um diagram de flechas. Outras representações amplamente utilizadas são representações por
matrizes e por digrafos, como discutiremos a seguir.
Definição 2.17. Seja R uma relação de A = {a1, a2, . . . , am} em B = {b1, b2, . . . , bn}. Os
elementos de A e de B foram listados de uma maneira fixada arbitrariamente. Seja MR = (mij)
a matriz dada por
mij =
{
1, se (ai, bj) ∈ R
0, se (ai, bj) /∈ R
Dizemos que a matriz MR representa a relação R.
Exemplo 2.18. Considere as seguintes relações.
1) Sejam A = {1, 2, 3}, B = {1, 2} e R a relação de A em B definida por xR y ←→ x > y.
Temos a1 = 1, a2 = 2, a3 = 3, b1 = 1 e b2 = 2. R = {(2, 1), (3, 1), (3, 2)} =⇒ m11 = 0,
m12 = 0, m21 = 1, m22 = 0, m31 = 1, m32 = 1. Logo
MR =
 0 0
1 0
1 1

É claro que, trocando a ordem dos elementos de A e B, mudamos a matriz.
2) Sejam
M =
 1 0 1 1 1
0 1 1 0 0
1 0 0 1 0

A = {a1, a2, a3} e B = {b1, b2, b3, b4, b5}. Determine a relação de A em B representada pela
matriz M .
Solução: R = {(a1, b1), (a3, b1), (a2, b2), (a1, b3), (a2, b3), (a1, b4), (a3, b4), (a1, b5)}.
6
Observação. 1) A matriz MR de uma relação em um conjunto A é uma matriz quadrada
n× n, onde n = |A|.
2) Examinando a matriz MR podemos descobrir propriedades da relação R. O próximos teo-
remas são exemplos disso.
Teorema 2.19. Seja R uma relação em um conjunto finito A = {a1, . . . , an}.
(a) R é reflexiva se, e somente se, a diagonal da matriz MR é formada toda por 1s.
(b) R é simétrica se, e somente se, MR é uma matriz simétrica1.
Demonstração: Para demonstrar o item (a), utilizaremos que R é reflexiva ⇐⇒ (∀a ∈
A)[(a, a) ∈ R] ⇐⇒ (∀(a, a) ∈ ∆)[(a, a) ∈ R] ⇐⇒ ∆ ⊆ R, onde ∆ = {(x, x) | x ∈ A}. Mas
∆ ⊆ R ⇐⇒ mii = 1 para todo i. Logo R é reflexiva ⇐⇒ a diagonal da matriz MR é formada
toda por 1s.
Para demonstrar o item (b), dado A = {a1, a2, . . . , an}, defina MR = (mij). A matriz MR
é simétrica ⇐⇒ (∀i)(∀j)(mij = mji). A relação R é simétrica ⇐⇒ (∀i)(∀j)(
[
(ai, aj) ∈
R ←→ (aj, ai) ∈ R
]
). Mas (ai, aj) ∈ R ←→ mij = 1. Logo a relação R é simétrica ⇐⇒
(∀i)(∀j)(mij = 1←→ mji = 1). Como um elemento da matriz só pode ser igual a 0 ou 1, então
R é simétrica ⇐⇒ (∀i)(∀j)(mij = mji) ⇐⇒ MR é uma matriz simétrica.
Exemplo 2.20. Sejam A = {a1, a2, a3, a4}, e M =

1 1 0 1
1 0 0 1
0 0 1 0
1 1 0 1
.
M representa uma relação R em A. R não é reflexiva, pois m22 = 0 =⇒ (a2, a2) /∈ R. R é
simétrica pois a matriz M é simétrica.
Nesse exemplo, a relação R satisfaz
R = {(a1, a1), (a1, a2), (a1, a4), (a2, a1), (a2, a4), (a3, a3), (a4, a1), (a4, a2), (a4, a4)}.
Observação. Uma relação R no conjunto A = {a1, a2, . . . , an} é antissimétrica quando
(aiRaj) ∧ (ajRai) =⇒ ai = aj, isto é, quando mij = 1 ∧ mji = 1 =⇒ i = j, ou seja,
mij = 1∧ i 6= j =⇒ mji = 0. Portanto R é antissimétrica se e somente se a matriz MR tem a
seguinte propriedade:
Um elemento mij fora da diagonal principal e seu simétrico aji em relação à diagonal prin-
cipal não podem ser ambos iguais a 1
Por exemplo, se
MR =

0 1 1 0
0 1 0 1
1 0 1 0
0 0 1 1

então R não é antissimétrica pois os elementos m13 e m31, simétricos em relação à diagonal
principal, são ambos iguais a 1.
1Lembre que uma matriz quadrada (aij) é simétrica ⇐⇒ (∀i)(∀j)(aij = aji), ou seja, ⇐⇒ a matriz tem
simetria em relação à diagonal principal.
7
Digrafos. Um digrafo (grafo direcionado) é um
grafo em que as arestas têm um sentido de percurso
associado. Como arestas admitem-se também os
laços (ou loops), que são segmentos saindo e che-
gando em um mesmo vértice. Formalmente, pode-
mos dizer que uma aresta que liga o vértice a com
b é o par ordenado (a, b), a é o vértice inicial e b o
vértice final. Um loop é umaaresta do tipo (a, a).
Na figura ao lado está representado um digrafo.
c
b a
Observação importante. Uma relação R em um conjunto A é um subconjunto do produto
cartesiano A× A, portanto R é um conjunto de pares ordenados de elementos de A. Como as
arestas de um digrafo são pares ordenados de vértices, podemos então pensar a relação R no
conjunto A como um digrafo em que o conjunto de vértices é V = A e o conjunto de arestas é
A = R.
Por exemplo, o digrafo do exemplo acima representa a relação
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (c, a), (c, b)}
no conjunto A = {a, b, c}.
Algumas propriedades de uma relação R podem ser obtidas a partir do digrafo que repre-
senta a relação:
1. R é reflexiva ⇐⇒ existe um loop em cada vértice.
2. R é simétrica ⇐⇒ toda vez que existir uma aresta ligando dois vértices distintos, existe
também a aresta com a orientação oposta.
3. R é antissimétrica ⇐⇒ nunca existem duas arestas com orientações opostas ligando um
mesmo par de vértices distintos.
4. R é transitiva ⇐⇒ toda vez que existem uma aresta ligando x com y e uma aresta
ligando y com z, existe também uma aresta ligando x com z.
Por exemplo, a relação R considerada no exemplo acima não é transitiva pois existem uma
aresta ligando b com a e uma aresta ligando a com c, mas não existe uma aresta ligando b com
c.
Se uma relação R for simétrica, podemos representá-la por um grafo (não direcionado). Neste
caso, cada aresta ab vai representar dois pares ordenados (a, b) ∈ R e (b, a) ∈ R.
Relação de Equivalência
Um dos tipos de relação que exercem um papel fundamental na Matemática são as relações
de equivalência, que estendem a noção de igualdade a situações em que a igualdade não é literal,
mas dependente de algum critério ou convenção.
Definição 2.21. Uma relação de equivalência R em um conjunto A é uma relação que é
reflexiva, simétrica e transitiva.
8
Exemplo 2.22. Os exemplos a seguir são relações de equivalência.
1. Sejam A = N× N e (a, b)R (x, y)←→ a + b = x + y.
Reflexiva: ∀(a, b) ∈ A, (a, b)R (a, b) pois a + b = a + b.
Simétrica: Se (a, b)R (x, y), então a + b = x + y, logo x + y = a + b, logo (x, y)R (a, b).
Transitiva: Se (a, b)R (x, y) e (x, y)R (u, v). Então a + b = x + y e x + y = u + v, logo
a + b = u + v. Segue que (a, b)R (u, v).
Logo R é uma relação de equivalência.
2. Sejam A = Z, a ∼ b←→ |a| = |b|.
Reflexiva: ∀a ∈ Z, a ∼ a, pois |a| = |a|.
Simétrica: Se a ∼ b, então |a| = |b|, logo |b| = |a|, logo b ∼ a.
Transitiva: Se a ∼ b e b ∼ c, então |a| = |b| e |b| = |c|. Segue que |a| = |c|. Logo a ∼ c.
Logo ∼ é uma relação de equivalência.
3. Sejam A = Z, aR b←→ a | b←→ (∃c ∈ Z)(ac = b).
R não é uma relação de equivalência. Não vale a propriedade simétrica. Por exemplo, 1 | 2
mas 2 - 1.
4. Sejam A = R e x ∼ y ←→ y − x ∈ Z.
Reflexiva: ∀x ∈ R, x ∼ x, pois x− x = 0 ∈ Z.
Simétrica: Se x ∼ y, então y − x ∈ Z, logo −(y − x) = x− y ∈ Z, logo y ∼ x.
Transitiva: Se x ∼ y e y ∼ z, então y − x ∈ Z e z − y ∈ Z. Mas a soma de inteiros é um
inteiro. Logo (y − x) + (z − y) ∈ Z. Então z − x ∈ Z. Logo x ∼ z.
Logo ∼ é uma relação de equivalência.
Três exemplos importantes de relações de equivaléncia são a representação de números
racionais, a cardinalidade e a congruência módulo m.
Representação dos números racionais. Vimos nas unidades anteriores que os números
racionais são frações p
q
onde p e q são números inteiros e q 6= 0. O uso das fracções para
representar os números racionais é uma notação, podeŕımos escrevê-los na form (p, q) ∈ Z×Z∗.
Considere a relação R em Z× Z∗ tal que
(a, b)R (p, q)⇐⇒ aq = bp.
Vejamos que R é uma relação de equivalência.
Reflexividade: (∀a ∈ Z)(∀b ∈ Z∗)[(a, b)R (a, b)], pois ab = ab.
Simetria: Sejam a, p ∈ Z e b, q ∈ Z∗ tais que (a, b)R (p, q). Isso significa que aq = bp, que é
equivalente a pb = qa. Por definição, temos que (p, q)R (a, b), estabelecendo que
(a, b)R (p, q)⇒ (p, q)R (a, b),
como queŕıamos demonstrar.
9
Transitividade: Sejam a, p, r ∈ Z e b, q, s ∈ Z∗ tais que (a, b)R (p, q) e (p, q)R (r, s). Isso significa
que aq = bp e ps = qr. Conclúımos que
(as)q = (aq)s = (bp)s = b(ps) = b(qr) = (br)q.
Como q 6= 0, segue que as = br e, portanto, (a, b)R (r, s). Isso estabelece que
((a, b)R (p, q)) ∧ ((p, q)R (r, s))⇒ (a, b)R (r, s),
como queŕıamos demonstrar.
Cardinalidade. Seja C uma famı́lia de conjuntos. Podemos definir uma relação em C tal que
S ∼ T se existe uma função bijetora f : S → T . Vejamos que ∼ é uma relação de equivalência.
Reflexividade: Dado S ∈ C a função identidade IS : S → S definida por
IS(x) = x, para todo x ∈ S
é uma função bijetora. Logo S ∼ S.
Simetria: Sejam S, T ∈ C tais que S ∼ T . Isso significa que existe f : S → T bijetora. Na
Unidade 4, vimos que f possui uma inversa f−1 : T → S que é bijetora. Logo T ∼ S.
Transitividade: Sejam S, T, U ∈ C tais que S ∼ T e T ∼ U . Isso significa que existem funções
bijetoras f : S → T e g : T → U . Na Unidade 4, vimos que a função composta g ◦ f : S → U é
bijetora. Logo S ∼ U , como queŕıamos demonstrar.
Congruência módulo m. Fixado m ∈ Z com m > 1, definimos uma relação em Z por
a ≡ b (mod m)⇐⇒ m | (b− a).
A expressão a ≡ b (mod m) lê-se “a é congruente a b módulo m”.
Observamos que a demonstração do teorema abaixo mostra que
m | (b− a)⇐⇒ m | (a− b).
Exemplo. 11 ≡ 2 (mod 3), pois 3 | (2− 11). De fato, (∃c = −3 ∈ Z)(3 · (−3) = −9).
13 ≡ −2 (mod 5), pois −2− 13 = −15 = (−3) · 5 =⇒ 5 | −15.
−2 ≡ 12 (mod 7), pois 7 | (12− (−2)).
Teorema 2.23. Se m ≥ 1 é inteiro, então a congruência módulo m é uma relação de equi-
valência em Z.
Demonstração. Dado m ≥ 1, provaremos que a relação de congruência módulo m é reflexiva,
simétrica e transitiva.
Reflexiva: (∀a ∈ Z) a ≡ a (mod m), pois m | (a− a), isto é, m | 0.
Simétrica: Se a ≡ b (mod m), então m | (b − a). Segue que ∃c ∈ Z tal que b − a = cm.
Portanto a − b = (−c) ·m. Então, ∃ d = −c ∈ Z tal que a − b = dm. Logo m | (a − b). Logo
b ≡ a (mod m).
Transitiva: Se a ≡ b (mod m) e b ≡ c (mod m), então m | (b − a) e m | (c − b) =⇒
(∃u ∈ Z)(∃v ∈ Z) tais que b− a = um e c− b = vm =⇒ (b− a) + (c− b) = um + vm =⇒
10
c − a = (u + v)m =⇒ ∃z = u + v ∈ Z tal que c − a = zm =⇒ m | (c − a) =⇒ a ≡ c
(mod m).
Logo a congruência módulo m é uma relação de equivalência em Z.
Observação. Dado a ∈ Z, sejam q e r o quociente e o resto da divisão de a por m. Temos
a = qm + r e 0 ≤ r 1 inteiro. A congruência módulo m tem as seguintes propriedades:
1. m | a←→ a ≡ 0 (mod m).
2. a ≡ b (mod m) e c ≡ d (mod m) −→ a + c ≡ b + d (mod m) e ac ≡ bd (mod m) (ou
seja, podemos somar e multiplicar membro a membro congruências com o mesmo módulo
m, assim como fazemos com igualdades).
3. a ≡ b (mod m) e c ∈ Z −→ ac ≡ bc (mod m).
Demonstração: 1) Por definição, a ≡ b (mod m)←→ m | (b− a). Além disto, a congruência
tem a propriedade simétrica. Então a ≡ 0 (mod m) ⇐⇒ 0 ≡ a (mod m) ⇐⇒ m | (a− 0).
2) Suponhamos que a ≡ b (mod m) e c ≡ d (mod m). Então m | (b−a) e m | (d− c). Então
∃s ∈ Z e ∃t ∈ Z tais que b− a = sm e d− c = tm.
Então, somando as duas últimas igualdades, obtemos (b− a) + (d− c) = sm + tm. Segue que
(b + d)− (a + c) = (s + t)m. Portanto ∃u = s + t ∈ Z tal que (b + d)− (a + c) = um. Segue
que m | [(b + d)− (a + c)]. Logo a + c ≡ b + d (mod m).
Para a multiplicação notamos que
bd−ac = bd−ad+ad−ac = (b−a)d+a(d−c) = smd+atm = (sd+at)m =⇒ ∃v = sd+at ∈ Z
tal que bd− ac = vm. Logo m | (bd− ac). Logo ac ≡ bd (mod m).
3) Tomando d = c no item 2), como a ≡ b (mod m) e c ≡ c (mod m), segue que
ac ≡ bc(mod m).
Observação importante. A propriedade 1 acima estabelece uma ligação entre divisibili-
dade e congruência. Por isso, as congruências são uma ferramenta importante no estudo da
divisibilidade.
Definição 2.25. Seja R uma relação de equivalência no conjunto A e seja a ∈ A um elemento
de A. Definimos a classe de equivalência de a como sendo o conjunto [a] dado por
[a] = {x ∈ A | aRx}.
Também se usa a notação de a para a classe de equivalência de a.
11
Exemplo 2.26. Vejamos alguns exemplos de classe de equivalência.
1) Se A = N×N e (a, b)R (x, y)←→ a+b = x+y, vimos que R é uma relação de equivalência.
[(2, 3)] =
{
(1, 4), (2, 3), (3, 2), (4, 1)
}
.
2) Se A = Z e aR b←→ a ≡ b (mod 3), temos
[0] = {a ∈ Z | a ≡ 0 (mod 3)} = {a ∈ Z | 3 divide a} =
= {0,±3,±6, . . .} = [3] = [−6] = · · ·
[1] = {a ∈ Z | a ≡ 1 (mod 3)} = {a ∈ Z | a deixa resto 1 na divisão por 3} =
= {. . . ,−5,−2, 1, 4, 7, 10, . . .} = [4] = [−2] = · · ·
[2] = {a ∈ Z | a ≡ 2 (mod 3)} = {a ∈ Z | a deixa resto 2 na divisão por 3} =
= {. . . ,−4,−1, 2, 5, 8, 11, . . .} = [5] = [−1] = · · ·
A classe de equivalência de qualquer outro inteiro é igual a uma dessas três acima. Existem ao
todo três classes de equivalência.
3) No exemplo relacionado aos racionais, isto é, em que temos elementos em Z × Z∗ com
(a, b)R (p, q) sempre que aq = bp, a classe de equivalência do elemento (1, 2) é dada por
[(1, 2)] = {(1, 2), (−1,−2), (2, 4), (−2,−4), (3, 6), . . .}.
Definição 2.27. Uma partição de um conjunto A é uma coleção (sinônimo de conjunto) {Si}
de subconjuntos de A satisfazendo
– (∀i)Si 6= ∅;
– i 6= j =⇒ Si ∩ Sj = ∅ (são dois a dois disjuntos);
–
⋃
i
Si = A.
@
@
@
@
S1
�
�
�
�
�
S2
�
�
�
�
�
A
A
A
A
A
S3
�
�
�
��
S4
S5
@
@
@
@@
S6
Exemplo. 1) Z = {n ∈ Z | n é par} ∪ {n ∈ Z | n é ı́mpar} é uma partição de Z.
2) Conforme o exemplo 2 acima, para a relação de congruência módulo 3, aR b ←→ a ≡ b
(mod 3), no conjunto Z,
Z = [0] ∪ [1] ∪ [2]
= {. . . ,−6,−3, 0, 3, 6, . . .} ∪ {. . . ,−5,−2, 1, 4, 7, . . .} ∪ {. . . ,−4,−1, 2, 5, , . . .}
é uma outra partição de Z.
Teorema 2.28. Seja R uma relação de equivalência em um conjunto A. Então as classes de
equivalência de R constituem uma partição de A.
Demonstração: Dividimos a demonstração em três partes:
1) As classes de equivalência são não vazias, (∀a ∈ A)([a] 6= ∅) pois, pela propriedade reflexiva,
aR a =⇒ a ∈ [a] =⇒ [a] 6= ∅.
12
2) As classes de equivalência são duas a duas disjuntas. Basta mostrar que ∀a ∈ A, ∀b ∈ A,
[a] ∩ [b] = ∅ ou [a] = [b].
Sejam a e b em A. Se [a] ∩ [b] = ∅, então já vale. Suponhamos que [a] ∩ [b] 6= ∅. Então
∃c ∈ [a]∩ [b]. Pela definição de classe de equivalência, e utilizando a simetria e a transitividade
da relação R, temos
aR c ∧ bR c =⇒ aR c ∧ cR b =⇒ aR b.
Vamos mostrar que [a] = [b]. Seja x ∈ [a]. Então xR a. Mas aR b. Pela propriedade transitiva,
segue que xR b. Então x ∈ [b]. Logo [a] ⊆ [b]. Analogamente se mostra que [b] ⊆ [a]. Logo
[a] = [b].
3) A união de todas as classes de equivalência é igual a A. Para isto, basta junstificar que
qualquer a ∈ A pertence a alguma classe de equivalência. De fato, ∀a ∈ A, a ∈ [a].
Dois fatos importantes sobre classes de equivalência, que foram estabelecidos na demons-
tração do teorema acima, são os seguintes.
Teorema 2.29. Seja R uma relação de equivalência em um conjunto A.
a) Para quaisquer a, b ∈ A, vale que [a] = [b] ou [a] ∩ [b] = ∅.
b) Para quaisquer a, b ∈ A, temos [a] = [b] se, e somente, b ∈ [a].
Exemplo 2.30. 1) Em Z consideremos a relação de congruência módulo 4, aR b ←→ a ≡ b
(mod 4). Dado um inteiro a ∈ Z qualquer, por divisão por 4, existe um quociente q ∈ Z e
existe um resto r ∈ {0, 1, 2, 3} tais que a = 4q + r e 0 ≤ r 1 qualquer, a relação de congruência módulo m,
aR b←→ a ≡ b (mod m)
tem m classes de equivalência e
Z = [0] ∪ [1] ∪ [2] ∪ · · · ∪ [m− 1] é uma partição de Z.
Dado a ∈ Z, por divisão por m, ∃q ∈ Z, ∃r ∈ Z tais que a = mq + r e 0 ≤ r