Uma relação R sobre um conjunto A é chamada uma relação de equivalência relação de equivalência se
ela for uma relação se ela for uma relação reflexiva, simétrica e transitiva
Reflexiva
A é relacionado a
A
Simétrica
A é relacionado com B, então B é relacionado com A
Transitiva
A é relacionado com B e B é relacionado com C então A é relacionado com C
Partições
Definição: Uma partição ou conjunto quociente de um conjunto não vazio A é uma coleção P de
subconjuntos não vazios de A tal que: 1. Cada elemento de A pertence a algum dos conjuntos em P 2.
Se A1 e A2 são elementos distintos em P, então A1∩A2=∅.
Conjunto P
Uma partição P pode ser usada para construir uma relação de
equivalência sobre A.
Teorema: Seja R uma relação de equivalência sobre A e seja P a coleção de todos os conjuntos relativos
R(a), para todo a∈A. Então P é uma partição de A, e R é a relação de equivalência determinada por P.
Se R é uma relação de equivalência sobre A, então
os conjuntos R(a) são chamados de classes de
equivalência de R.
A partição P construída no teorema acima consiste
portanto de todas as classes de equivalência de R e esta
partição é denotada por A/R.
Partições de um conjunto A também são chamadas
de “conjuntos quocientes” de A, e a notação A/R
lembra que P é o conjunto quociente de A que é
construído e determinado por R.
Relações de ordem
Ordem total
antissimétrica
Se a ≤ b e b ≤ a então a=b
reflexiva
a ≤ a
transitiva
a ≤ b, b ≤ c implica em a ≤ c
ordem parcial
Toda ordem total é também parcial
Elementos mínimos e máximos
Seja R uma relação de ordem sobre um conjunto X, e A um
subconjunto de X. Um elemento mínimo de A sob R é um
elemento m ∈ A se (m, a) ∈ R para todo a ∈ A.
Um elemento m de A é máximo sob uma
relação R se (a, m) ∈ R para todo a ∈ A.
Elementos minimais e maximais
Seja R uma relação de ordem sobre um conjunto X, e
A um subconjunto de X. Um elemento minimal de A
sob R é um elemento m ∈ A tal que não existe
nenhum a ∈ A, diferente de m, com (a, m) ∈ R.
Um elemento maximal de A sob R é um elemento m de A
tal que não existe nenhum a em A, diferente de m, tal que
(m, a) ∈ R