Question

(Combinatória: relações binárias e contagem)

Seja A = {1, 2, ... , n} um conjunto, com n ∈ ℕ.

Uma relação binária R ⊆ A × A é dita reflexiva se para todo a ∈ A, então (a, a) ∈ R.

a) Mostre que se R é reflexiva, então R possui pelo menos n elementos, isto é, #(R) ≥ #(A).

b) Calcule a quantidade de relações reflexivas que existem sobre A.

─────

Gabarito alínea b) $2^{n(n-1)}.$​

Answer 1

a) Já que para todo elemento $a \in A$ há um par $(a, a) \in R$, como A possui n elementos, R deve possuir pelo menos n pares. Escrito diferentemente, a quantidade de elementos de R deve ser no mínimo a quantidade de elementos de A:

$\#(R) \geq \#(A)$ (praticamente autoexplicativo).

b) Basta acrescentar a R quaisquer pares $(a,b)$, com $a\neq b$, para formar uma relação distinta. Então posso escolher $a$ de $n$ modos e $b$ de $(n-1)$ modos, totalizando $n(n-1)$ pares. Para cada par, posso colocá-lo ou não no conjunto R (que vale lembrar que já possui todos os pares $(a,a)$), ou seja, $n(n-1)$ tomadas de decisão de 2 opções cada. Portanto, posso inserir pares em R de $2^{n(n-1)}$ modos, que corresponde diretamente à quantidade de relações reflexivas existentes.