אריתמטיקה של עוצמות

שעור ארבעה-עשר - אריתמטיקה של עוצמות

מספרים טבעיים אפשר לחבר, להכפיל ואפילו להעלות בחזקה (אבל לא תמיד אפשר לחלק או לחסר אותם, אם רוצים שהתוצאה תשאר מספר טבעי). מכיוון שכל מספר טבעי הוא, בסופו של דבר, עוצמה של קבוצות מסויימות, אפשר לנסות להכליל את הפעולות האריתמטיות אל מרחב העוצמות. ההגדרות, גם אם הן מפתיעות במבט ראשון, פשוטות מאד, והן מאפשרות לשחזר את התכונות הסטדנרטיות של הפעולות האריתמטיות גם בהקשר הכללי.

למרות שעד כה הגדרנו רק מתי שתי קבוצות הן שוות-עוצמה, כדי שלא לסרבל את ההגדרות, נדבר מעכשיו על העוצמה $\ |A|$, ונתכוון ל-$\ A$ או כל קבוצה שוות-עוצמה לה. בפרט, נסמן ב-$\ n$ ("העוצמה $\ n$") את העוצמה של קבוצה (כלשהי) בת $\ n$ ("המספר הטבעי $\ n$") אברים.

תרגיל. לכל קבוצה $\ A$, אם בקבוצה $\ S$ יש איבר יחיד, אז $\ |A|=|A\times S|$.

תרגיל. אם $\ A,B$ זרות ו- $\ A',B'$ זרות, ומתקיים $\ |A|=|A'|$ ו- $\ |B|=|B'|$, אז $\ |A\cup B|=|A'\cup B'|$.

התרגיל הזה מאפשר להשתמש באיחוד כדי להגדיר את הסכום של העוצמות, ולא רק של הקבוצות עצמן (משום שהוא מראה שהחלפת קבוצה בקבוצה שוות-עוצמה לה, אינה משנה את עוצמת האיחוד).

הגדרה. אם $\ A,B$ קבוצות זרות, אז סכום העוצמות שלהן הוא עוצמת האיחוד $\ A\cup B$ (היינו, $\ |A|+|B|=|A\cup B|$). באופן כללי (אם לא ידוע ש-$\ A$ ו-$\ B$ זרות), אפשר להעזר בתרגיל האחרון כדי להתחכם ולהחליף אותן במכפלות הקרטזיות $\ A\times \{1\}$ ו-$\ B\times \{2\}$, שהן בוודאי זרות.

תרגיל. לכל עוצמה $\ |A|+|\emptyset |=|A|$ (לכן עוצמת הקבוצה הריקה נקראת אפס); לכל שתי עוצמות, $\ |A|+|B|=|B|+|A|$; לכל שלוש עוצמות מתקיים $\ (|A|+|B|)+|C|=|A|+(|B|+|C|)$.

תרגיל. אם $\ |A|=|A'|$ ו- $\ |B|=|B'|$ אז $\ |A\times B|=|A'\times B'|$. (כעת אפשר להשתמש במכפלה הקרטזית כדי להגדיר פעולה בין עוצמות).

הגדרה. מכפלת עוצמות מוגדרת כעוצמת המכפלה הקרטזית, $\ |A|\cdot |B|=|A\times B|$. (כאן אין צורך להניח שהקבוצות זרות).

תרגיל. אם $\ S$ קבוצה בת איבר אחד, אז לכל עוצמה, $\ |A|\cdot |S|=|A|$; לכל שתי עוצמות מתקיים $\ |A|\cdot |B|=|B|\cdot |A|$ (מה בעצם מוכיחים כאן?); לכל שלוש עוצמות מתקיים $\ (|A|\cdot |B|)\cdot |C|=|A|\cdot (|B|\cdot |C|)$ (וכאן?); לכל שלוש עוצמות מתקיים $\ |A|\cdot (|B|+|C|)=|A|\cdot |B|+|A|\cdot |C|$.

ואל הפעולה השלישית והאחרונה -

הגדרה. לכל שתי קבוצות $\ A,B$, הקבוצה $\ A^{B}$ מסמנת את אוסף כל הפונקציות $\ B\rightarrow A$.

תרגיל. אם $\ |A|=|A'|$ ו- $\ |B|=|B'|$ אז $\ |A^{B}|=|{A'}^{B'}|$.

פתרון. לפי ההנחה יש פונקציות חד-חד-ערכיות ועל $\ f:A\rightarrow A'$ ו- $\ g:B\rightarrow B'$. עלינו לבנות פונקציה חד-חד-ערכית ועל מקבוצת הפונקציות $\ A^{B}$ אל הקבוצה $\ {A'}^{B'}$; בדוק שהפונקציה $\ \Phi (h)=g\circ h\circ f^{-1}$ עונה על הדרישות.

הגדרה. החזקה של עוצמות מוגדרת כעוצמה של קבוצת הפונקציות, היינו $\ |A|^{|B|}=|A^{B}|$.

תרגיל. לכל שלוש עוצמות מתקיים $\ |A|^{|B|+|C|}=|A|^{|B|}\cdot |A|^{|C|}$; לכל שלוש עוצמות מתקיים $\ |A|^{|B|\cdot |C|}=(|A|^{|B|})^{|C|}$; לכל שלוש עוצמות מתקיים $\ (|A|\cdot |B|)^{|C|}=|A|^{|C|}\cdot |B|^{|C|}$.

<< השיעור הקודם - קבוצות סופיות ואינסופיות

דף הקורס - תורת הקבוצות

השיעור הבא - קבוצות בנות מנייה >>