2. Seja℘(X) o conjunto cujos elementos sao os subconjuntos de ˜ X. Prove por induc¸ao que ˜ se X e finito ent ´ ao˜ card℘(X) = 2 card X .

Para provar que se X é finito, então o card(℘(X)) = 2^card(X), podemos usar a indução matemática. Base da indução: Se X é um conjunto finito com um único elemento, então o conjunto de partes de X é {∅, {x}}. Portanto, o card(℘(X)) = 2^1 = 2, e 2^card(X) = 2^1 = 2. Assim, a base da indução é verdadeira. Hipótese da indução: Suponha que, para um conjunto finito X com n elementos, o card(℘(X)) = 2^n. Passo da indução: Considere um conjunto finito X com n+1 elementos. Escolha um elemento x em X e defina Y = X - {x}. Observe que Y tem n elementos. Pela hipótese de indução, o card(℘(Y)) = 2^n. Agora, observe que cada subconjunto de X é ou um subconjunto de Y ou um subconjunto de Y com x adicionado. Portanto, o número total de subconjuntos de X é igual ao número de subconjuntos de Y mais o número de subconjuntos de Y com x adicionado. Isso é igual a 2^n + 2^n = 2^(n+1). Portanto, o card(℘(X)) = 2^(n+1), como desejado. Assim, concluímos que, se X é finito, então o card(℘(X)) = 2^card(X).