Enumere todas as relações no conjunto X=0,1. Quais delas são relações de equivalência em X ? Quais relações são de ordem?

Passo 1

O enunciado pede para listar todas as relações em X=0,1, depois identificar quais são relações de equivalência e quais são relações de ordem (parciais).
Conteúdo necessário: definição de relação como qualquer subconjunto de Xtimes X, e critérios de
– equivalência: reflexiva, simétrica e transitiva;
– ordem parcial: reflexiva, antissimétrica e transitiva.

Passo 2

O produto cartesiano é
Xtimes X = (0,0),(0,1),(1,0),(1,1)
Como uma relação é qualquer subconjunto de Xtimes X, temos 2^4=16 relações ao todo.

Passo 3

Vamos numerar as 16 relações R1,dots,R16 listando os subconjuntos em ordem crescente de tamanho:
R1 = emptyset
R2 = (0,0)
R3 = (0,1)
R4 = (1,0)
R5 = (1,1)
R6 = (0,0),(0,1)
R7 = (0,0),(1,0)
R8 = (0,0),(1,1)
R9 = (0,1),(1,0)
R10 = (0,1),(1,1)
R11 = (1,0),(1,1)
R12 = (0,0),(0,1),(1,0)
R13 = (0,0),(0,1),(1,1)
R14 = (0,0),(1,0),(1,1)
R15 = (0,1),(1,0),(1,1)
R16 = (0,0),(0,1),(1,0),(1,1).

Passo 4

Para ser relação de equivalência em X precisa ser reflexiva ( (0,0),(1,1)in R), simétrica e transitiva.
Examinando, só duas relações satisfazem todos os três:
(0,0),(1,1) (identidade)
(0,0),(0,1),(1,0),(1,1) (relação universal)

Passo 5

Para ser ordem parcial precisa ser reflexiva, antissimétrica e transitiva.
As que contêm (0,0) e (1,1) e não violam antissimetria são exatamente três:
(0,0),(1,1),
(0,0),(1,1),(0,1),
(0,0),(1,1),(1,0).

Resposta

Todas as 16 relações em X são
&emptyset,;(0,0),;(0,1),;(1,0),;(1,1), &(0,0),(0,1),;(0,0),(1,0),;(0,0),(1,1),;(0,1),(1,0), &(0,1),(1,1),;(1,0),(1,1),;(0,0),(0,1),(1,0), &(0,0),(0,1),(1,1),;(0,0),(1,0),(1,1),;(0,1),(1,0),(1,1), &(0,0),(0,1),(1,0),(1,1)
Relações de equivalência:
(0,0),(1,1) e (0,0),(0,1),(1,0),(1,1).
Relações de ordem parcial:
(0,0),(1,1),
(0,0),(1,1),(0,1),
(0,0),(1,1),(1,0).

Exercícios relacionados