116. Se A é um conjunto finito com n elementos, prove que P(A) tem 2ⁿ elementos

Enunciado. Prove por indução finita que, se é um conjunto finito com elementos, então , o conjunto das partes de , tem elementos.

Este é o fecho do capítulo e amarra o que foi visto lá no começo, sobre conjunto das partes. Lembre que reúne todos os subconjuntos de , inclusive o vazio e o próprio .

1ª etapa — a base . Se tem zero elementos, então , e o único subconjunto do vazio é ele mesmo:

Verdadeira. (Se preferir começar em : um conjunto tem os subconjuntos e , dois ao todo, e .)

2ª etapa — hipótese de indução. Supomos que todo conjunto com elementos tenha subconjuntos, e tomamos um conjunto com elementos.

O passo — a ideia de separar um elemento. Escolha um elemento qualquer e escreva , onde tem elementos. Agora divida os subconjuntos de em dois grupos, sem sobreposição:

• os que não contêm — são exatamente os subconjuntos de , e pela hipótese são ;

• os que contêm — cada um deles é um subconjunto de com o acrescentado. Há um para cada subconjunto de , ou seja, também .

Todo subconjunto de cai em um dos dois grupos, e em nenhum dos dois ao mesmo tempo. Somando:

Está provado.

Uma leitura que ajuda a não esquecer: montar um subconjunto é decidir, elemento por elemento, se ele entra ou não. São duas escolhas para cada um dos elementos, independentes entre si — daí .

Conferência: no exercício 22 você construiu para e encontrou 16 subconjuntos. E .