Quantos elementos estão no conjunto de potência?

o conjunto de força de um conjunto UMA é a coleção de todos os subconjuntos de A. Ao trabalhar com um finito conjunto com n elementos, uma pergunta que poderíamos fazer é: “Quantos elementos existem no conjunto de UMA? Veremos que a resposta a esta pergunta é 2ⁿ e provar matematicamente por que isso é verdade.

Procuraremos um padrão observando o número de elementos no conjunto de potências de UMA, Onde UMA tem n elementos:

• E se UMA = {} (o conjunto vazio), então UMA não tem elementos mas P (A) = {{}}, um conjunto com um elemento.
• E se UMA = {a}, então UMA tem um elemento e P (A) = {{}, {a}}, um conjunto com dois elementos.
• E se UMA = {a, b}, então UMA tem dois elementos e P (A) = {{}, {a}, {b}, {a, b}}, um conjunto com dois elementos.

Em todas essas situações, é fácil ver por conjuntos com um pequeno número de elementos que, se houver um número finito de n elementos em UMA, então o conjunto de potência P (UMA) tem 2n elementos. Mas esse padrão continua? Só porque um padrão é verdadeiro para

Mas esse padrão continua. Para mostrar que esse é realmente o caso, usaremos a prova por indução.

A prova por indução é útil para provar declarações relativas a todos os números naturais. Conseguimos isso em duas etapas. Para o primeiro passo, ancoramos nossa prova mostrando uma afirmação verdadeira para o primeiro valor de n que desejamos considerar. O segundo passo de nossa prova é assumir que a declaração vale para n = ke a demonstração de que isso implica que a declaração se aplica a n = k + 1.

Para ajudar em nossa prova, precisaremos de outra observação. A partir dos exemplos acima, podemos ver que P ({a}) é um subconjunto de P ({a, b}). Os subconjuntos de {a} formam exatamente metade dos subconjuntos de {a, b}. Podemos obter todos os subconjuntos de {a, b} adicionando o elemento b a cada um dos subconjuntos de {a}. Essa adição de conjunto é realizada por meio da operação de conjunto de união:

• Conjunto vazio U {b} = {b}
• {a} U {b} = {a, b}

Estes são os dois novos elementos em P ({a, b}) que não eram elementos de P ({a}).

Vemos uma ocorrência semelhante para P ({a, b, c}). Começamos com os quatro conjuntos de P ({a, b}) e, para cada um deles, adicionamos o elemento c:

• Conjunto vazio U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

E assim terminamos com um total de oito elementos em P ({a, b, c}).

Agora estamos prontos para provar a afirmação: “Se o conjunto UMA contém n elementos, então o conjunto de potência P (A) tem 2ⁿ elementos ".

Começamos observando que a prova por indução já foi ancorada para os casos n = 0, 1, 2 e 3. Supomos por indução que a afirmação vale para k. Agora deixe o conjunto UMA conter n + 1 elementos. Nós podemos escrever UMA = B U {x} e considere como formar subconjuntos de UMA.

Tomamos todos os elementos de P (B), e pela hipótese indutiva, existem 2ⁿ destes. Em seguida, adicionamos o elemento x a cada um desses subconjuntos de B, resultando em mais 2ⁿ subconjuntos de B. Isso esgota a lista de subconjuntos de Be, portanto, o total é 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} elementos do conjunto de potência de UMA.