le ensemble de puissance d'un ensemble UNE est la collection de tous les sous-ensembles de A. Lorsque vous travaillez avec un fini ensemble avec n éléments, une question que nous pourrions poser est: «Combien d’éléments y a-t-il dans le UNE? " Nous verrons que la réponse à cette question est 2n et prouver mathématiquement pourquoi cela est vrai.
Observation du motif
Nous chercherons un modèle en observant le nombre d'éléments dans l'ensemble de puissance de UNE, où UNE a n éléments:
- Si UNE = {} (l'ensemble vide), puis UNE n'a pas d'éléments mais P (A) = {{}}, un ensemble avec un élément.
- Si UNE = {a}, puis UNE a un élément et P (A) = {{}, {a}}, un ensemble à deux éléments.
- Si UNE = {a, b}, puis UNE a deux éléments et P (A) = {{}, {a}, {b}, {a, b}}, un ensemble à deux éléments.
Dans toutes ces situations, il est simple de voir ensembles avec un petit nombre d'éléments que s'il y a un nombre fini de n éléments dans UNE, puis le bloc d'alimentation P (UNE) a 2n éléments. Mais ce schéma se poursuit-il? Tout simplement parce qu'un modèle est vrai pour
n = 0, 1 et 2 ne signifie pas nécessairement que le modèle est vrai pour des valeurs plus élevées de n.Mais ce schéma continue. Pour montrer que c'est effectivement le cas, nous utiliserons la preuve par induction.
Preuve par induction
La preuve par induction est utile pour prouver des déclarations concernant tous les nombres naturels. Nous y parvenons en deux étapes. Pour la première étape, nous ancrons notre preuve en montrant un vrai énoncé pour la première valeur de n que nous souhaitons considérer. La deuxième étape de notre preuve est de supposer que la déclaration vaut pour n = k, et le spectacle que cela implique que la déclaration vaut pour n = k + 1.
Une autre observation
Pour nous aider dans notre preuve, nous aurons besoin d'une autre observation. D'après les exemples ci-dessus, nous pouvons voir que P ({a}) est un sous-ensemble de P ({a, b}). Les sous-ensembles de {a} forment exactement la moitié des sous-ensembles de {a, b}. Nous pouvons obtenir tous les sous-ensembles de {a, b} en ajoutant l'élément b à chacun des sous-ensembles de {a}. Cet ajout d'ensemble est accompli au moyen de l'opération d'ensemble d'union:
- Ensemble vide U {b} = {b}
- {a} U {b} = {a, b}
Ce sont les deux nouveaux éléments de P ({a, b}) qui n'étaient pas des éléments de P ({a}).
Nous voyons une occurrence similaire pour P ({a, b, c}). Nous commençons par les quatre ensembles de P ({a, b}), et à chacun d'eux nous ajoutons l'élément c:
- Ensemble vide U {c} = {c}
- {a} U {c} = {a, c}
- {b} U {c} = {b, c}
- {a, b} U {c} = {a, b, c}
Et donc nous nous retrouvons avec un total de huit éléments dans P ({a, b, c}).
La preuve
Nous sommes maintenant prêts à prouver la déclaration: «Si l'ensemble UNE contient n éléments, puis l'ensemble de puissance P (A) a 2n éléments."
On commence par noter que la preuve par induction a déjà été ancrée pour les cas n = 0, 1, 2 et 3. Nous supposons par induction que l'énoncé vaut pour k. Maintenant, laissez l'ensemble UNE contenir n + 1 éléments. Nous pouvons écrire UNE = B U {x}, et voyez comment former des sous-ensembles de UNE.
Nous prenons tous les éléments de P (B), et par l'hypothèse inductive, il y a 2n de ceux-ci. Ensuite, nous ajoutons l'élément x à chacun de ces sous-ensembles de B, résultant en un autre 2n sous-ensembles de B. Cela épuise la liste des sous-ensembles de B, et donc le total est de 2n + 2n = 2(2n) = 2n + 1 éléments de l'ensemble de puissance de UNE.