Relações de Equivalência

Prévia do material em texto

Relac¸o˜es de equivaleˆncia
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Novembro de 2013
Suma´rio
• Reflexividade, simetria, transitividade.
• Relac¸o˜es de equivaleˆncia.
Gottlob Frege
Destacou o papel das
relac¸o˜es de equivaleˆncia
na fundamentac¸a˜o da
matema´tica.
Gottlob Frege (1848 – 1925)
Exemplo
{?, ∗} {?, �}
{∗, �} {�, ◦}
{◦, ?} {∗, ◦}
Exemplo
{?◦, �∗} {�?, ?◦}
{∗◦, ?◦} {?◦, ◦?}
{?◦, �?} {�∗, �?}
Exemplo
1 {?}, {◦}, {�}, {∗}, {∗◦}, . . .
2 {?, ◦}, {�, ∗}, {∗, ◦}, {∗◦, ?◦}, . . .
3 {?, ◦, �}, {�, ∗, ◦}, {∗, ◦, ?}, {∗◦, ?◦, ?�}, . . .
Igualdade
Propriedades da igualdade:
(1) Para todo x ∈ A, temos que x = x .
(2) Para todos x , y ∈ A, se x = y , enta˜o y = x .
(3) Para todos x , y , z ∈ A, se x = y e y = z , enta˜o x = z .
Reflexividade
Definic¸a˜o Seja R uma relac¸a˜o em A. Dizemos que R e´ reflexiva
se, para todo x ∈ A, temos que
(x , x) ∈ R.
Reflexividade
Proposic¸a˜o Seja R uma relac¸a˜o em A.
R e´ reflexiva se, e somente se, IA ⊆ R.
Simetria
Definic¸a˜o Seja R uma relac¸a˜o em A. Dizemos que R e´ sime´trica
se, para todos x , y ∈ A, temos que
(x , y) ∈ R =⇒ (y , x) ∈ R.
Simetria
Proposic¸a˜o Seja R uma relac¸a˜o em A.
R e´ sime´trica se, e somente se, R−1 ⊆ R.
Transitividade
Definic¸a˜o Seja R uma relac¸a˜o em A. Dizemos que R e´ transitiva
se, para todos x , y , z ∈ A, temos que
(x , y) ∈ R and (y , z) ∈ R =⇒ (x , z) ∈ R.
Transitividade
Proposic¸a˜o Seja R uma relac¸a˜o em A.
R e´ transitiva se, e somente se, R ◦ R ⊆ R.
Problemas
Verdadeiro ou falso?
(1) Se R e S sa˜o sime´tricas, enta˜o R ∪ S e´ sime´trica.
(2) Se R e´ reflexiva, enta˜o R ∪ S e´ reflexiva.
(3) Se R e S sa˜o transitivas, enta˜o R ∪ S e´ transitiva.
Relac¸a˜o de equivaleˆncia
Definic¸a˜o Seja R uma relac¸a˜o em A. Dizemos que R e´ uma
relac¸a˜o de equivaleˆncia em A se R e´ reflexiva, sime´trica e transitiva.
Proposic¸a˜o Seja R uma relac¸a˜o em A.
R e´ relac¸a˜o de equivaleˆncia em A se, e somente se,
IA ⊆ R, R−1 ⊆ R, R ◦ R ⊆ R.
Exerc´ıcios
1. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo, 2006).
3. Exerc´ıcios da Lista 11.
	Reflexividade
	Simetria
	Transitividade
	Relação de equivalência