Seja
um conjunto finito com
elementos. Mostre que:
O número de relações em
é
.
O número de relações em
Passo 1
O enunciado diz que
é um conjunto finito com
elementos e que uma relação em
é qualquer subconjunto de
. Nosso objetivo é contar quantas relações — isto é, quantos subconjuntos de
— existem.
Passo 2
Como cada elemento de
pode aparecer como primeira ou segunda coordenada de um par, o produto cartesiano
tem
pares ordenados.
Passo 3
Cada relação em
corresponde a escolher, para cada um dos
pares de
, se ele pertence ou não ao subconjunto. Então o número de subconjuntos de um conjunto com
elementos vale
Passo 4
Se quisermos excluir a relação vazia (o subconjunto que não contém nenhum par), basta retirar uma opção, obtendo
Resposta
O número de relações não vazias em
é
.