QUESTÃO Prove por indução que se # A = n, então # P(A) = 2^n.

Passo 1

Vamos começar entendendo o que a questão pede. Precisamos provar, usando o princípio da indução matemática, que se um conjunto A tem n elementos (isto é, ), então o número de subconjuntos de A, representado por P(A), é igual a 2^n. Para isso, vamos precisar entender como a indução funciona e aplicar isso passo a passo.

Passo 2

Caso Base: Vamos verificar se a afirmação é verdadeira para .
Quando , o conjunto A é o conjunto vazio, ou seja, . O conjunto das partes de A, P(A), contém apenas um subconjunto, que é o próprio conjunto vazio. Então:
E como , temos que:
Portanto, o caso base é verdadeiro.

Passo 3

Hipótese de Indução: Suponha que a afirmação seja verdadeira para algum inteiro , ou seja, suponha que para um conjunto B com , vale que:

Passo 4

Passo Indutivo: Precisamos mostrar que a afirmação também é verdadeira para . Ou seja, para um conjunto A com , devemos provar que:
Considere o conjunto A como a união de um conjunto B com k elementos e um novo elemento a, ou seja, . Cada subconjunto de A ou não contém o elemento a, ou contém a.
  • Os subconjuntos que não contêm a são exatamente os subconjuntos de B, e há deles (pela hipótese de indução).
  • Os subconjuntos que contêm a são obtidos adicionando a a cada subconjunto de B, também totalizando .
Portanto, o número total de subconjuntos de A é:

Resposta

Assim, por indução matemática, provamos que se , então .

Exercícios relacionados