Πόσα στοιχεία υπάρχουν στο σετ τροφοδοσίας;

ο ισχύος ενός σετ ΕΝΑ είναι η συλλογή όλων των υποσυνόλων του A. Όταν εργάζεστε με ένα πεπερασμένο σειρά με n στοιχεία, μια ερώτηση που θα μπορούσαμε να ζητήσουμε είναι: "Πόσα στοιχεία υπάρχουν στη δέσμη εξουσίας ΕΝΑ; " Θα δούμε ότι η απάντηση στο ερώτημα αυτό είναι 2ⁿ και να αποδείξουμε μαθηματικά γιατί αυτό είναι αλήθεια.

Θα αναζητήσουμε ένα μοτίβο παρατηρώντας τον αριθμό των στοιχείων στο σύνολο ισχύος ΕΝΑ, που ΕΝΑ έχει n στοιχεία:

• Αν ΕΝΑ = {} (το κενό σύνολο), τότε ΕΝΑ δεν έχει στοιχεία αλλά Ρ (Α) = {{}}, ένα σύνολο με ένα στοιχείο.
• Αν ΕΝΑ = {a}, τότε ΕΝΑ έχει ένα στοιχείο και Ρ (Α) = {{}, {a}}, ένα σύνολο με δύο στοιχεία.
• Αν ΕΝΑ = {a, b}, τότε ΕΝΑ έχει δύο στοιχεία και Ρ (Α) = {{}, {a}, {b}, {a, b}}, ένα σύνολο με δύο στοιχεία.

Σε όλες αυτές τις περιπτώσεις, είναι εύκολο να το δούμε σκηνικά με ένα μικρό αριθμό στοιχείων που αν υπάρχει ένας πεπερασμένος αριθμός n στοιχεία σε ΕΝΑ, τότε το σύνολο ισχύος Π (ΕΝΑ) έχει 2n στοιχεία. Αλλά συνεχίζει αυτό το μοτίβο; Ακριβώς επειδή ένα πρότυπο ισχύει για

Αλλά αυτό το μοτίβο συνεχίζεται. Για να δείξουμε ότι πράγματι συμβαίνει αυτό, θα χρησιμοποιήσουμε την απόδειξη με επαγωγή.

Η απόδειξη μέσω επαγωγής είναι χρήσιμη για την απόδειξη δηλώσεων που αφορούν όλους τους φυσικούς αριθμούς. Αυτό επιτυγχάνεται σε δύο βήματα. Για το πρώτο βήμα, αγκυρώνουμε την απόδειξη μας δείχνοντας μια αληθινή δήλωση για την πρώτη τιμή του n που θέλουμε να εξετάσουμε. Το δεύτερο βήμα της απόδειξής μας είναι να υποθέσουμε ότι ισχύει η δήλωση n = κ, και η επίδειξη ότι αυτό συνεπάγεται ότι η δήλωση ισχύει για n = κ + 1.

Για να βοηθήσουμε στην απόδειξη μας, θα χρειαστούμε μια άλλη παρατήρηση. Από τα παραπάνω παραδείγματα μπορούμε να δούμε ότι το P ({a}) είναι ένα υποσύνολο του P ({a, b}). Τα υποσύνολα του {a} σχηματίζουν ακριβώς το ήμισυ των υποσυνόλων του {a, b}. Μπορούμε να αποκτήσουμε όλα τα υποσύνολα {a, b} προσθέτοντας το στοιχείο b σε κάθε υποσύνολο {a}. Αυτή η προσθήκη της σειράς επιτυγχάνεται μέσω της καθορισμένης λειτουργίας της ένωσης:

• Αδειάστε το σύνολο U {b} = {b}
• {a} U {b} = {a, b}

Αυτά είναι τα δύο νέα στοιχεία του P ({a, b}) που δεν ήταν στοιχεία του P ({a}).

Βλέπουμε ένα παρόμοιο περιστατικό για το P ({a, b, c}). Αρχίζουμε με τα τέσσερα σύνολα του P ({a, b}), και σε κάθε ένα από αυτά προσθέτουμε το στοιχείο c:

• Αδειάστε το σύνολο U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, γ}
• {a, b} U {c} = {a, b, c}

Έτσι καταλήγουμε με συνολικά οκτώ στοιχεία στο P ({a, b, c}).

Είμαστε πλέον έτοιμοι να αποδείξουμε τη δήλωση, "Αν το σετ ΕΝΑ περιέχει n στοιχεία, τότε το σύνολο ισχύος Ρ (Α) έχει 2ⁿ στοιχεία."

Ξεκινάμε σημειώνοντας ότι η απόδειξη μέσω επαγωγής έχει ήδη αγκυροβοληθεί για τις περιπτώσεις n = 0, 1, 2 και 3. Υποθέτουμε με επαγωγή ότι ισχύει η δήλωση κ. Τώρα αφήστε το σετ ΕΝΑ περιέχω n + 1 στοιχεία. Μπορούμε να γράψουμε ΕΝΑ = σι U {x}, και εξετάστε πώς να διαμορφώσετε υποσύνολα του ΕΝΑ.

Λαμβάνουμε όλα τα στοιχεία του Ρ (Β), και από την επαγωγική υπόθεση, υπάρχουν 2ⁿ από αυτά. Στη συνέχεια, προσθέτουμε το στοιχείο x σε κάθε ένα από αυτά τα υποσύνολα του σι, με αποτέλεσμα άλλα 2ⁿ υποσύνολα του σι. Αυτό εξαντλεί τον κατάλογο των υποσυνόλων του σι, και έτσι το σύνολο είναι 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} στοιχεία του συνόλου ισχύος του ΕΝΑ.