תורת הקבוצות/קבוצת החזקה: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
MeRabbit (שיחה | תרומות)
MeRabbit (שיחה | תרומות)
הרחבה - קבוצת החזקה
שורה 66:
 
===הוכחה באמצעות עוצמות===
{{שקול לדלג|ההוכחה הנ"ל משתמשת במושג של פונקציות ועוצמות שעדיין לא למדנו. מומלץ לחזור לקרוא את ההוכחה הנ"ל מיד לאחר שסיימת לקרוא את הפרק על עוצמות, שכן היא מדגימה בצורה טובה את השימוש בעוצמות לשם הוכחות קומבינטוריות.}}
{{תורת הקבוצות|מוגבל}}
 
בהינתן קבוצה A סופית בעלת n איברים, נרצה למצוא קבוצה שהעצמה שלה היא <math>2^n</math>, ולהראות שהקבוצה הנ"ל שקולה לקבוצת החזקה.
 
נסתכל על הקבוצה <math>\{ 0,1\}^n</math>. קל להראות שזו אכן הקבוצה המבוקשת. נגדיר את הפונקציה:
<center>
<math>\ f:\{ 0,1\}^n\rightarrow 2^A</math>
</center>
על ידי
<center>
<math>\ f(x_1,\ldots ,x_n)=\{ a_i\in A\vert x_i\neq 0\}</math>
</center>
קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן אינטואטיבי, f מקבלת מעין "מתכון" שאומר איזה מהאברים להכניס לתת-קבוצה ואיזה לא לפי הסדר של ה0 ו1 שהיא מקבלת. אם היא מקבלת 1 במקום הi, האיבר הi בקבוצה A נכנס לתת-קבוצה שf מחזירה.
 
הוכחת החד-חד הערכיות והעל של f מושארת כתרגיל לקורא.
 
{{תורת הקבוצות|מוגבל}}
[[קטגוריה:תורת הקבוצות|*]]