Seja A um conjunto finito com n elementos. Mostre que:
O número de relações em A é 2^n^2-1.

Passo 1

O enunciado diz que A é um conjunto finito com n elementos e que uma relação em A é qualquer subconjunto de Atimes A. Nosso objetivo é contar quantas relações — isto é, quantos subconjuntos de Atimes A — existem.

Passo 2

Como cada elemento de A pode aparecer como primeira ou segunda coordenada de um par, o produto cartesiano Atimes A tem
|Atimes A|=ncdot n=n^2
pares ordenados.

Passo 3

Cada relação em A corresponde a escolher, para cada um dos n^2 pares de Atimes A, se ele pertence ou não ao subconjunto. Então o número de subconjuntos de um conjunto com n^2 elementos vale
2^n^2,

Passo 4

Se quisermos excluir a relação vazia (o subconjunto que não contém nenhum par), basta retirar uma opção, obtendo
2^n^2-1

Resposta

O número de relações não vazias em A é 2^n^2-1.

Exercícios relacionados