Vou provar que, se um conjunto tiver \(n\) elements, então esse conjunto tem exatamente \(2^n\) subconjuntos.

|S| = n implies that |P(S)| = 2^n

Prova num tweet

Tome-se um conjunto de tamanho \(n\). Para qualquer um dos seus subconjuntos podemos atribuir um número \(0\)/\(1\) a um elemento, consoante esse elemento esteja ou não no subconjunto, e a cada subconjunto corresponde uma sequência de atribuições. Há \(2^n\) atribuições destas, logo há \(2^n\) subconjuntos.

Artigo anterior Próximo artigo

Blog Comments powered by Disqus.