קבוצות שקולות

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

הגדרה פורמלית

נאמר שקבוצה $A$ שקולה לקבוצה $B$ ומסמנים $A\sim B$ אם ורק אם קיימת פונקציה $f:A\to B$ שהיא חד-חד-ערכית ועל (להלן חחע"ע).

שקילות בין קבוצות מקיימת את תכונות יחס שקילות. נראה זאת:

• רפלקסיביות: $A\sim A$, שכן פונקציית הזהות $f(a)=a$ היא חחע"ע.
• סימטריות: אם $f:A\to B$ היא פונקציה חחע"ע, אז הפונקציה ההפוכה $f^{-1}:B\to A$ היא פונקציה חחע"ע.
• טרנזיטיביות: אם $f:A\to B$ היא חחע"ע ו-$g:B\to C$ היא חחע"ע, הרי שגם ההרכבה $g\circ f:A\to C$ היא חחע"ע.

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

מוטיבציה

דוגמה לפונקציה חד-חד-ערכית ועל מקבוצה $X$ לקבוצה $Y$. קיומה של הפונקציה מעיד על כך שבשתי הקבוצות אותו מספר של איברים.

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

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

אם ישנה התאמה חחע"ע בין שתי קבוצות סופיות, הרי שיש להן אותו מספר איברים. ולהפך, אם לשתי קבוצות סופיות יש אותו מספר של איברים, הרי שיש ביניהן התאמה חחע"ע.

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

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

אינסופיות לפי דדקינד

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

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

דוגמאות

קבוצות בנות מנייה

המחשה לדרך בה בונים סדרה של המספרים רציונליים, ובכך מראים כי הם בני מנייה.

קבוצה בת מנייה היא קבוצה השקולה לקבוצת המספרים הטבעיים המסומנת $\mathbb {N}$ (בערך זה קבוצת הטבעיים כוללת את 0, אולם כל התוצאות נכונות גם בלעדיו). אלו הן הקבוצות האינסופיות הקטנות ביותר. העוצמה ("מספר האיברים") של קבוצות בנות מנייה נקראת אָלֶף אֶפֶס, וסימונה $\aleph _{0}$.

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

באופן כללי, קבוצה בת מנייה היא קבוצה שניתן לסדר את איבריה בסדרה אינסופית (ומכאן שמה, שכן ניתן למנות את איבריה אחד אחד). זאת משום שאם $A$ קבוצה שאיבריה ניתנים לסידור כסדרה $a_{0},a_{1},a_{2},\ldots$, אז ההתאמה $n\mapsto a_{n}$ היא התאמה חחע"ע בין הטבעיים לאיברי הקבוצה. מכאן נובע שכל תת-קבוצה אינסופית של המספרים הטבעיים (או קבוצה בת-מנייה אחרת) היא בת מנייה (למשל קבוצת הראשוניים).

ישנן קבוצות רבות שנדמות "גדולות" מן הטבעיים, אך גם הן בנות מנייה. למשל קבוצת המספרים השלמים (הכוללת גם שליליים) היא בת מנייה, שכן ניתן לסדר את איבריה בסדרה כך: $0,1,-1,2,-2,3,-3,\ldots$. קבוצת המספרים הרציונליים, הכוללת גם את השברים של מספרים שלמים, אף היא בת מנייה, כפי שמדגימה פונקציית הזיווג של קנטור (שמתאימה זוגות של מספרים שלמים, ובפרט שברים, למספרים הטבעיים). גם הקבוצה של כל הסדרות הסופיות של מספרים טבעיים היא בת מנייה.

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

קבוצות מעוצמת הרצף

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

הדגמה גאומטרית של השקילות בין קטע (מופיע במאונך) לישר (מופיע במאוזן). לכל נקודה על הישר האינסופי מעבירים ישר המחבר אותה לנקודה P או Q (בהתאם למיקום שלה), ומתאימים לה את נקודת החיתוך עם הקטע. באיור, A מותאם ל-A' ו-B מותאם ל-B'.

מסתבר שקבוצת הממשיים שקולה גם לקבוצת הנקודות על כל קרן וקטע שמוגבלים באחד או בשניים מקצותיהם. כלומר מספר הנקודות בישר אינסופי זהה למספר הנקודות על קטע סופי, קטן ככל שיהיה. למעשה, ב-1877 גילה קנטור כי כל הקבוצות הללו שקולות גם לקבוצת הנקודות במישור, במרחב התלת-ממדי ובמרחב ה-n-ממדי. על כך אמר "אני רואה זאת, אך איני מאמין!". ההוכחה המקורית של קנטור עושה שימוש בהצגת מספרים כשבר משולב, אך הוכחה פשוטה יותר עושה שימוש בהצגה העשרונית של מספרים ממשיים. למשל כדי להתאים בין קטע היחידה לריבוע היחידה אפשר להציג כל נקודה בריבוע כ-$(0.a_{1}a_{2}a_{3}\ldots ,0.b_{1}b_{2}b_{3}\ldots )$ ולהתאים לה את $0.a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}\ldots$.

גם קבוצת החזקה $P(\mathbb {N} )$ שקולה לקבוצת הממשיים.