Prove por indução que o número de subconjuntos de um conjunto com n elementos é 2^{n}. 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 n elementos é \,2^{n}\, 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 n elementos significa que há exatamente n 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: n=0.
Expliquei o que é um conjunto com 0 elementos: é o conjunto vazio. Quantos subconjuntos tem o conjunto vazio? Só o próprio subconjunto vazio. Portanto o número de subconjuntos é 1. Como
2^{0}=1,
a afirmação vale para n=0. Então a base da indução está comprovada.

Passo 3

Hipótese indutiva: suponha que a afirmação seja verdadeira para algum inteiro k\ge0. Ou seja, suponha que todo conjunto com k elementos tem exatamente 2^{k} subconjuntos. Esta é a hipótese que vamos usar para provar o caso k+1.

Passo 4

Passo indutivo — ideia principal e divisão em casos:
Considere um conjunto S com k+1 elementos. Escolha um elemento particular de S e chame-o de x. Vamos contar todos os subconjuntos de S separando-os em dois casos mutuamente exclusivos:
  • Caso A: subconjuntos que não contêm x.
  • Caso B: subconjuntos que contêm x.
Esses dois casos são disjuntos (um subconjunto não pode simultaneamente conter e não conter x) e sua união é o conjunto de todos os subconjuntos de S. Pela regra da adição (contar a união de casos disjuntos), o total de subconjuntos de S é 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 x): qualquer subconjunto que não contenha x é exatamente um subconjunto de S\setminus\{x\}, que tem k elementos. Pelo hipótese indutiva, o número de tais subconjuntos é 2^{k}.
  • Caso B (contém x): se um subconjunto contém x, retire x desse subconjunto; o que sobra é um subconjunto de S\setminus\{x\}. Essa operação é bijetiva entre subconjuntos de S que contêm x e subconjuntos de S\setminus\{x\}. Logo, também há 2^{k} subconjuntos que contêm x.
Agora somamos (regra da adição para casos disjuntos):
\text{nº total de subconjuntos de }S = 2^{k}+2^{k}=2\cdot 2^{k}=2^{k+1}.º
Assim o caso k+1 está provado a partir do caso k.

Passo 6

Conclusão da indução: mostramos a base n=0 e que, se a propriedade vale para k, vale para k+1. Pelo princípio da indução matemática, a afirmação vale para todo inteiro n\ge0: um conjunto com n elementos tem 2^{n} subconjuntos.

Passo 7

Interpretação com a regra do produto (argumento alternativo e intuitivo):
Ao construir um subconjunto de um conjunto com n 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 m_{1},m_{2},\dots,m_{n} opções, o total de combinações é \prod_{i=1}^{n}m_{i}. Aqui cada m_{i}=2, então o total é
\prod_{i=1}^{n}2=2^{n}.
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 x" / "não contém x" 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 n=1: elementos \{a\}. Subconjuntos: \varnothing,\{a\}. Total 2=2^{1}.
  • Para n=2: elementos \{a,b\}. Subconjuntos: \varnothing,\{a\},\{b\},\{a,b\}. Total 4=2^{2}.
  • Para n=3: dá 8=2^{3} 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).

Resposta

2^{n}

Exercícios relacionados