Exemplo 5.6: [Conjunto Potência] Seja A um conjunto com n elementos. Mostrar que o conjunto potência P(A) tem 2n elementos. Prova: Base: Se n = 0 temos que o conjunto A é vazio portanto P(A) = {∅}, logo o número de elementos de P(A) é igual a 1 = 20. Hipótese de indução: Para um dado conjunto A com k ≥ 0 elementos temos que o conjunto potência P(A) tem 2k elementos. Passo: Mostrar que para um conjunto A com k + 1 elementos o conjunto P(A) tem 2k+1 elementos. Seja A um conjunto com k + 1 elementos. Como k ≥ 0, A tem pelo menos um elemento. Seja a este elemento. Considere o conjunto B = A − {a}. Logo B tem k elementos, o que, pela hipótese de indução, implica que P(B) tem 2k elementos. O P(A) pode ser dividido em dois sub-conjuntos, ou seja P(A) = P(B) ∪ {C ∪ {a} : C ∈ P(B) } . Como P(B)∩{C ∪ {a} : C ∈ P(B) } = ∅ e o número de elementos de |P(B)| = |{C ∪ {a} : C ∈ P(B) }| = 2k. concluı́mos que o número de elementos de P(A) = 2k+1. Fim.