Prove por indução que o número de subconjuntos de um conjunto com n elementos é
. Relacione com a regra do produto em combinatória e regra da adição para casos.
Passo 1
O enunciado pede duas coisas: provar por indução que o número de subconjuntos de um conjunto com
elementos é
e relacionar essa afirmação com a regra do produto e a regra da adição em combinatória.
Informações que temos e vamos usar:
- Um conjunto com
elementos significa que há exatamente objetos distintos. - “Subconjunto” significa qualquer coleção de elementos do conjunto original (incluindo o subconjunto vazio e o conjunto todo).
- A prova deve ser por indução (então usarei base e passo indutivo).
- Vou também mostrar a interpretação combinatória usando a regra do produto e comentar a conexão com a regra da adição.
Passo 2
Base da indução:
.
Expliquei o que é um conjunto com elementos: é o conjunto vazio. Quantos subconjuntos tem o conjunto vazio? Só o próprio subconjunto vazio. Portanto o número de subconjuntos é
. Como
Expliquei o que é um conjunto com
a afirmação vale para
. Então a base da indução está comprovada.
Passo 3
Hipótese indutiva: suponha que a afirmação seja verdadeira para algum inteiro
. Ou seja, suponha que todo conjunto com
elementos tem exatamente
subconjuntos. Esta é a hipótese que vamos usar para provar o caso
.
Passo 4
Passo indutivo — ideia principal e divisão em casos:
Considere um conjunto com
elementos. Escolha um elemento particular de
e chame-o de
. Vamos contar todos os subconjuntos de
separando-os em dois casos mutuamente exclusivos:
Considere um conjunto
- Caso A: subconjuntos que não contêm
. - Caso B: subconjuntos que contêm
.
Esses dois casos são disjuntos (um subconjunto não pode simultaneamente conter e não conter
) e sua união é o conjunto de todos os subconjuntos de
. Pela regra da adição (contar a união de casos disjuntos), o total de subconjuntos de
é a soma do número de subconjuntos em A com o número em B.
Passo 5
Contagem dos dois casos usando a hipótese indutiva:
- Caso A (não contém
): qualquer subconjunto que não contenha é exatamente um subconjunto de , que tem elementos. Pelo hipótese indutiva, o número de tais subconjuntos é . - Caso B (contém
): se um subconjunto contém , retire desse subconjunto; o que sobra é um subconjunto de . Essa operação é bijetiva entre subconjuntos de que contêm e subconjuntos de . Logo, também há subconjuntos que contêm .
Agora somamos (regra da adição para casos disjuntos):
Assim o caso
está provado a partir do caso
.
Passo 6
Conclusão da indução: mostramos a base
e que, se a propriedade vale para
, vale para
. Pelo princípio da indução matemática, a afirmação vale para todo inteiro
: um conjunto com
elementos tem
subconjuntos.
Passo 7
Interpretação com a regra do produto (argumento alternativo e intuitivo):
Ao construir um subconjunto de um conjunto com elementos, para cada elemento há duas escolhas independentes: incluí‑lo ou não incluí‑lo. A regra do produto diz que, se há escolhas independentes com
opções, o total de combinações é
. Aqui cada
, então o total é
Ao construir um subconjunto de um conjunto com
Este argumento é direto e funciona porque as escolhas (incluir/não incluir) são independentes para cada elemento. Ele é equivalente à prova por indução: a partição em "contém
" / "não contém
" usa a regra da adição, enquanto a escolha binária por elemento usa a regra do produto.
Passo 8
Exemplinhos para fixar (concreto e divertido):
- Para
: elementos . Subconjuntos: . Total . - Para
: elementos . Subconjuntos: . Total . - Para
: dá subconjuntos; pode listar para checar.
Esses exemplos mostram na prática tanto a visão de casos (adição) quanto a visão de escolhas independentes (produto).