הצגת המקור של הדף "קבוצות שקולות"

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

==הגדרה פורמלית==
נאמר שקבוצה <math>A</math> שקולה לקבוצה <math>B</math> ומסמנים <math>A\sim B</math> אם ורק אם קיימת [[פונקציה]] <math>f : A \to B</math> [[פונקציה חד-חד-ערכית ועל|חד־חד־ערכית ועל]].

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

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

==מוטיבציה==
[[תמונה:Bijection.svg|שמאל|ממוזער|200px|דוגמה לפונקציה חד-חד-ערכית ועל מקבוצה <math>X</math> לקבוצה <math>Y</math>. קיומה של הפונקציה מעיד על כך שבשתי הקבוצות אותו מספר של איברים.]]
ההגדרה של קבוצות שקולות נועדה [[הכללה (מתמטיקה)|להכליל]] את ה[[יחס (תורת הקבוצות)|יחס]] "בעלות אותו מספר איברים" כך שיחול גם על [[קבוצה אינסופית|קבוצות אינסופיות]].

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

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

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

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

==אינסופיות לפי דדקינד==
ידידו של קנטור, [[ריכרד דדקינד]], השתמש ביחס השקילות בין קבוצות כדי להגדיר [[קבוצה אינסופית]]. לפי דדקינד, קבוצה אינסופית היא קבוצה השקולה ל[[תת-קבוצה]] ממש של עצמה (תת-קבוצה שאינה שווה לקבוצה עצמה). למשל [[קבוצת המספרים הטבעיים]] היא אינסופית, משום שההתאמה <math>n  \mapsto (n+1)</math> היא התאמה חחע"ע בין קבוצת המספרים הטבעיים עם [[אפס (מספר)|אפס]] לקבוצת המספרים הטבעיים ללא אפס (שהיא תת-קבוצה ממש שלה).

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

==דוגמאות==
===קבוצות בנות־מנייה===
[[קובץ:Rationals.png|שמאל|ממוזער|250px|המחשה לדרך בה בונים סדרה של המספרים רציונליים, ובכך מראים כי הם בני מנייה.]]
[[קבוצה בת־מנייה]] היא קבוצה השקולה לקבוצת ה[[מספר טבעי|מספרים הטבעיים]] המסומנת <math>\mathbb{N}</math> (בערך זה קבוצת הטבעיים כוללת את 0, אולם כל התוצאות נכונות גם בלעדיו). אלו הן הקבוצות האינסופיות הקטנות ביותר. ה[[עוצמה (מתמטיקה)|עוצמה]] ("מספר האיברים") של קבוצות בנות־מנייה נקראת [[אלף אפס|אָלֶף אֶפֶס]], וסימונה <math>\aleph_0</math>.

קבוצת ה[[מספר זוגי|מספרים הזוגיים]] היא דוגמה פשוטה לקבוצת בת־מנייה, שכן <math>n  \mapsto 2n</math> היא התאמה חחע"ע בין הטבעיים כולם לזוגיים. [[פרדוקס גלילאו]] מדגים כי גם קבוצת ה[[מספר ריבועי|מספרים הריבועיים]] היא בת־מנייה.

באופן כללי, קבוצה בת־מנייה היא קבוצה שניתן לסדר את איבריה ב[[סדרה אינסופית]] (ומכאן שמה, שכן ניתן למנות את איבריה אחד אחד). זאת משום שאם <math>A</math> קבוצה  שאיבריה ניתנים לסידור כסדרה <math>a_0, a_1, a_2,\ldots</math>, אז ההתאמה <math>n  \mapsto a_n</math> היא התאמה חחע"ע בין הטבעיים לאיברי הקבוצה. מכאן נובע שכל תת-קבוצה אינסופית של המספרים הטבעיים (או [[קבוצה בת מנייה|קבוצה בת-מנייה]] אחרת) היא בת־מנייה (למשל [[קיומם של אינסוף מספרים ראשוניים|קבוצת הראשוניים]]).

ישנן קבוצות רבות שנדמות "גדולות" מן הטבעיים, אך גם הן בנות־מנייה. למשל [[קבוצת המספרים השלמים]] (הכוללת גם שליליים) היא בת־מנייה, שכן ניתן לסדר את איבריה בסדרה כך: <math>0, 1, -1, 2, -2, 3, -3,\ldots</math>. קבוצת ה[[מספר רציונלי|מספרים הרציונליים]], הכוללת גם את ה[[שבר (מתמטיקה)|שבר]]ים של מספרים שלמים, אף היא בת־מנייה, כפי שמדגימה [[פונקציית הזיווג של קנטור]] (שמתאימה זוגות של מספרים שלמים, ובפרט שברים, למספרים הטבעיים). גם הקבוצה של כל ה[[n-יה סדורה|סדרות הסופיות]] של מספרים טבעיים היא בת־מנייה.

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

===קבוצות מעוצמת הרצף===
כאמור, קנטור הוכיח כי קבוצת ה[[מספר ממשי|מספרים הממשיים]] אינה בת־מנייה. העוצמה של קבוצת המספרים הממשיים והקבוצות השקולות לה נקראת [[עוצמת הרצף]], וסימונה <math>\aleph</math>. בתיאור גאומטרי, קבוצת המספרים הממשיים היא קבוצת הנקודות על [[הישר הממשי]]. לכן כל קבוצת הממשיים שקולה לקבוצת ה[[נקודה (גאומטריה)|נקודות]] על [[ישר]] (ומכאן שמה של עוצמת הרצף).

[[קובץ:קבוצות שקולות.svg|מרכז|ממוזער|450px|הדגמה גאומטרית של השקילות בין קטע (מופיע במאונך) לישר (מופיע במאוזן). לכל נקודה על הישר האינסופי מעבירים ישר המחבר אותה לנקודה P או Q (בהתאם למיקום שלה), ומתאימים לה את נקודת החיתוך עם הקטע. באיור, A מותאם ל-{{משמאל לימין|A'}} ו-B מותאם ל-{{משמאל לימין|B'}}.]]

מסתבר שקבוצת הממשיים שקולה גם לקבוצת הנקודות על כל [[קרן (גאומטריה)|קרן]] ו[[קטע (מתמטיקה)|קטע]] שמוגבלים באחד או בשניים מקצותיהם. כלומר מספר הנקודות בישר אינסופי זהה למספר הנקודות על קטע סופי, קטן ככל שיהיה. למעשה, ב-[[1877]] גילה קנטור כי כל הקבוצות הללו שקולות גם לקבוצת הנקודות ב[[מישור (גאומטריה)|מישור]], ב[[מרחב תלת-ממדי|מרחב התלת-ממדי]] וב[[המרחב האוקלידי|מרחב ה-n-ממדי]]. על כך אמר "אני רואה זאת, אך איני מאמין!". ההוכחה המקורית של קנטור עושה שימוש בהצגת מספרים כ[[שבר משולב]], אך הוכחה פשוטה יותר עושה שימוש בהצגה העשרונית של מספרים ממשיים. למשל כדי להתאים בין [[קטע היחידה]] ל[[ריבוע היחידה]] אפשר להציג כל נקודה בריבוע כ-<math>(0.a_1a_2a_3\ldots,0.b_1b_2b_3\ldots)</math> ולהתאים לה את <math>0.a_1b_1a_2b_2a_3b_3\ldots</math>.

גם [[קבוצת חזקה|קבוצת החזקה]] <math>P(\mathbb{N})</math> שקולה לקבוצת הממשיים.

[[קטגוריה:תורת הקבוצות]]
[[קטגוריה:יחסי שקילות]]

[[de:Mächtigkeit (Mathematik)#Gleichmächtigkeit, Mächtigkeit]]