Seja
o conjunto das partes de
. Prove, indutivamente, que se
é finito, então
.
Passo 1
O enunciado pede para provar, por indução sobre o número de elementos de um conjunto finito
, que o número de subconjuntos de
(isto é, o cardinal do conjunto das partes
) é dado por
O conteúdo principal aqui é indução finita e contagem de subconjuntos.
Passo 2
Caso base (
):
Quando temos
, logo
Quando
Portanto a propriedade vale para
.
Passo 3
Hipótese de indução:
Suponha que para todo conjunto finito com
valha
Suponha que para todo conjunto finito
Passo 4
Passo indutivo (
):
Seja um conjunto finito com
. Escolha um elemento
e defina
Seja
que tem
pela remoção de exatamente um elemento.
Passo 5
Particionamos
em dois subcoleções disjuntas:
Há bijeção natural entre
e
(cada subconjunto de
é também subconjunto de
sem
) e outra bijeção entre
e
dada por
. Pela hipótese de indução,
Passo 6
Como
e
, temos
Isto completa o passo indutivo e a prova por indução está concluída.