עוצמה (מתמטיקה)

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

• העוצמה של הקבוצה הריקה היא אפס.
• העוצמה של קבוצת ימי השבוע היא שבע.
• העוצמה של קבוצת חברי הכנסת המכהנים כיום היא 120.

דוגמאות לקבוצות עם עוצמה אינסופית:

• כל המספרים השלמים המתחלקים בשלוש.
• כל המספרים (הלא שלמים) בין אפס לאחד.

את העוצמה של קבוצה A מסמנים $|A|$.

שקילות בין קבוצות

ערך מורחב – קבוצות שקולות

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

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

אחת התוצאות המפתיעות הראשונות של ההגדרה הזו היא שקבוצה יכולה לחפוף לתת קבוצה שלה. לדוגמה, קבוצת כל המספרים הטבעיים $\!\,1,2,3,\dots$ חופפת לקבוצת כל המספרים הזוגיים $\!\,2,4,6,\dots$, כאשר ההתאמה או הזיווג הוא של כל מספר טבעי $\!\,n$ עם המספר הזוגי $\!\,2n$. ברור שההתאמה הזו מסדרת את המספרים משתי הקבוצות בזוגות, ושהזוגות ממצים את כל המספרים משתי הקבוצות. כלומר, לקבוצת המספרים הטבעיים ולקבוצת המספרים הזוגיים יש אותה עוצמה.

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

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

ניתן לראות זאת בנקל על ידי יצירת שתי פונקציות חד חד ערכיות, האחת מהרציונליים אל הטבעיים, והשנייה מהטבעיים אל הרציונלים. נקרא להן $f$ ו-$g$:

$\!\,f(m/n)=2^{m}\cdot 3^{n}$ כאשר המספר הרציונלי מוצג בצורה המצומצמת ביותר שלו.

$\!\,g(n)=n$

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

ריבוי עוצמות

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

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

את העוצמה של המספרים הטבעיים סימן קנטור באות העברית $\!\,\aleph _{0}$ (קרי: אלף אפס), ואת עוצמת הממשיים (עוצמת הרצף) סימן באות $\!\,\aleph$ (כיום משתמשים גם בסימון $\!\,c$ לעוצמה זו). למעשה עוצמת המספרים הממשיים שווה לעוצמת קבוצת החזקה של המספרים הטבעיים, כלומר $\!\,\aleph =2^{\aleph _{0}}$.

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

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

חיבור. הסכום $\ |A|+|B|$ מוגדר כעוצמת האיחוד $\ A\cup B$, בתנאי שהקבוצות A ו- B זרות. זוהי פעולה קומוטטיבית ואסוציאטיבית, אך קיומן של עוצמות אינסופיות אינו מאפשר להגדיר את פעולת החיסור: $\ \aleph _{0}+n=\aleph _{0}$ לכל n טבעי, ואפילו $\ \aleph _{0}+\aleph _{0}=\aleph _{0}$. הסכום של קבוצה כלשהי של עוצמות מוגדרת באותה צורה כעוצמה של האיחוד של קבוצות מעוצמות מתאימות, שזרות זו לזו בזוגות. ראו עקרון החיבור.

כפל. המכפלה $\ |A|\cdot |B|$ מוגדרת כעוצמתה של המכפלה הקרטזית $\ A\times B$. גם פעולה זו היא קומוטטיבית ואסוציאטיבית, ואף דיסטריבוטיבית ביחס לחיבור. המכפלה של קבוצה כלשהי של עוצמות מוגדרת באותה צורה כעוצמת המכפלה הקרטזית של קבוצות מעוצמות מתאימות. ראו עקרון הכפל.

חזקה. החזקה $\ |A|^{|B|}$ מוגדרת כעוצמתה של קבוצת הפונקציות $\ B\rightarrow A$. הפעולה מקיימת את האקסיומות הרגילות של החזקה, כדוגמת $\ |A|^{|B|+|C|}=|A|^{|B|}\cdot |A|^{|C|}$ ו- $\ |A|^{|B|\cdot |C|}=(|A|^{|B|})^{|C|}$. מכיוון שיש בדיוק פונקציה אחת מן הקבוצה הריקה לכל קבוצה (הלא היא הפונקציה הריקה), מתקיים $\ |A|^{0}=1$ לכל עוצמה; בפרט $\ 0^{0}=1$. ממשפט קנטור ומההתאמה בין קבוצת החזקה לקבוצת הפונקציות מקבוצה A לקבוצה $\ \{0,1\}$ מקבלים $\ |A|<|P(A)|=2^{|A|}$. בהשוואה לזה, עקבי להניח ש-$2^{\aleph _{1}}=2^{\aleph _{0}}$.

אם מניחים את אקסיומת הבחירה, ולפחות אחת מהעוצמות $\kappa ,\mu$ היא אינסופית, אז מתקיים $\kappa +\mu =\kappa \cdot \mu =\max\{\kappa ,\mu \}$. לכן עיקר העניין הוא במכפלות ובסכומים אינסופיים של עוצמות.

מספרים מונים

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

בהנחת אקסיומת הבחירה ניתן לפתור את הבעיה באופן פשוט יותר, באמצעות הגדרת המונה של פון-נוימן: מונה הוא סודר $\mu$ כך שלכל סודר $\alpha <\mu$ אין העתקה חח"ע מ-$\mu$ ל-$\alpha$. אקסיומת הבחירה שקולה לכך שכל עוצמה מיוצגת על ידי מספר מונה - כלומר שלכל קבוצה X יש מונה שעוצמתו היא |X|.

כיוון שהמונים הם סודרים - הם סדורים היטב, ולכל מונה יש מונה מינימלי שגדול ממנו שנקרא המונה העוקב. למשל המונה הראשון שגדול מ-$\aleph _{0}$ מסומן ב-$\aleph _{1}$. ניתן להמשיך ולהגדיר באינדוקציה טרנספיניטית את סדרת ה"אלף" - סדרת העוצמות של המונים האינסופיים:

$\aleph _{0},\aleph _{1},\aleph _{2},\dots \aleph _{\omega },\aleph _{\omega +1},\dots$

מקובל לסמן ב-$\omega _{\alpha }$ את המספר המונה שמתאים לעוצמה $\aleph _{\alpha }$. במידה ואקסיומת הבחירה לא מתקיימת, הסדרה הזו לא ממצה את כל העוצמות ויש עוצמות שלא שוות לאף $\aleph _{\alpha }$ - אלו העוצמות של הקבוצות אותן לא ניתן לסדר היטב. למרות זאת, אין אף עוצמה שגדולה מכל סדרת האלף, כלומר לכל קבוצה X אפשר למצוא מספר אלף $\mu =\aleph _{\beta }$ כך שאין פונקציה חד חד ערכית $f:\mu \rightarrow X$ (זהו מספר הרטוג של X).

סדרת האלף היא סדרה נורמלית (כלומר היא עולה ממש ולכל סודר גבולי $\alpha$ מתקיים $\textstyle \aleph _{\alpha }=\sup _{\beta <\alpha }\aleph _{\beta }$) ולכן יש לה נקודות שבת, כלומר יש מונים שמקיימים $\mu =\aleph _{\mu }$. למשל, הגבול של הסדרה $\omega ,\omega _{\omega },\omega _{\omega _{\omega }}\dots$ הוא נקודת שבת של סדרת האלף.

ראו גם

• מונחים בתורת הקבוצות
• השערת הרצף
• מונה גדול