كم عدد العناصر الموجودة في مجموعة الطاقة؟

ال مجموعة الطاقة من مجموعة أ هو جمع كل مجموعات فرعية من A. عند العمل مع محدود جلس مع ن عناصر ، سؤال واحد قد نطرحه هو ، "كم عدد العناصر الموجودة في مجموعة القوة أ ؟ " سنرى أن الإجابة على هذا السؤال هي 2^ن وتثبت حسابيا لماذا هذا صحيح.

سنبحث عن نمط من خلال ملاحظة عدد العناصر في مجموعة الطاقة أ، أين أ لديها ن عناصر:

• إذا أ = {} (المجموعة الفارغة) ، ثم أ ليس لديه عناصر ولكن ف (أ) = {{}} ، مجموعة بعنصر واحد.
• إذا أ = {a} ، إذن أ عنصر واحد و ف (أ) = {{} ، {a}} ، مجموعة ذات عنصرين.
• إذا أ = {a، b} إذن أ عنصرين و ف (أ) = {{} ، {a} ، {b} ، {a ، b}} ، مجموعة ذات عنصرين.

في كل هذه الحالات ، من السهل رؤيته مجموعات مع عدد قليل من العناصر التي إذا كان هناك عدد محدود من ن عناصر في أ، ثم تعيين السلطة ص (أ) لديه 2ن عناصر. ولكن هل يستمر هذا النمط؟ فقط لأن النمط صحيح ن = 0 و 1 و 2 لا يعني بالضرورة أن النمط صحيح لقيم أعلى لـ ن.

لكن هذا النمط يستمر. لإثبات أن هذا هو الحال بالفعل ، سنستخدم الدليل عن طريق الاستقراء.

البرهان عن طريق الحث مفيد لإثبات البيانات المتعلقة بجميع الأعداد الطبيعية. نحقق ذلك في خطوتين. للخطوة الأولى ، نقوم بتثبيت إثباتنا من خلال إظهار بيان حقيقي للقيمة الأولى لـ

للمساعدة في إثباتنا ، سنحتاج إلى ملاحظة أخرى. من الأمثلة أعلاه ، يمكننا أن نرى أن 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، c}
• {a، b} U {c} = {a، b، c}

وهكذا ينتهي بنا المطاف بإجمالي ثمانية عناصر في P ({a، b، c}).

نحن الآن جاهزون لإثبات البيان ، "إذا كانت المجموعة أ يحتوي على ن العناصر ، ثم مجموعة الطاقة ف (أ) لديه 2^ن عناصر."

نبدأ بالإشارة إلى أن الدليل عن طريق الاستقراء قد تم إرساؤه بالفعل للحالات ن = 0 و 1 و 2 و 3. نفترض بالحث الذي يحمله البيان ك. الآن دع المجموعة أ يحتوي ن + 1 عناصر. يمكننا الكتابة أ = ب ش {x} ، والنظر في كيفية تشكيل مجموعات فرعية من أ.

نأخذ جميع عناصر ف (ب)، ومن خلال الفرضية الاستقرائية ، هناك 2^ن من هؤلاء. ثم نضيف العنصر x إلى كل مجموعة فرعية من ب، مما أدى إلى 2 أخرى^ن مجموعات فرعية من ب. هذا يستنفد قائمة مجموعات فرعية من بوبذلك يكون الإجمالي 2^ن + 2^ن = 2(2^ن) = 2^{ن + 1} عناصر مجموعة القوة أ.