אמת, יש אינסוף איברים בשתי הקבוצות, אבל יש אינסופים גדולים יותר ואינסופים קטנים יותר, זה כבר קשור לתורת הקבוצות. ובכן, הרצאה קלה בתורת הקבוצות.
למעשה, לפי הגדרה, שתי קבוצות מוגדרות להיות שקולות עוצמה אם קיימת פונקציה חד-חד-ערכית ועל מהאחת לשנייה. ההגיון מאחורי זה הוא שאם קיימת פונקציה כזו, הרי שהקבוצה האחת אינה אלא שמות שונים עבור איברי הקבוצה השנייה (כי ניתן לראות בפונקציה חח"ע ועל מתן שמות שונים לאיברי קבוצה).
קבוצה בת מנייה הינה קבוצה שקולת עוצמה למספרים הטבעיים - במלים אחרות, ניתן "למנות" את איבריה.
עכשיו נתחיל בדוגמאות אנטי-אינטואיטיביות:
1) המספרים הזוגיים הם בני מנייה. זאת אומרת, יש אותו מספר של מספרים זוגיים כמו שיש של מספרים טבעיים בכלל. הרי פונקציה חח"ע ועל מהטבעיים לזוגיים: f
= 2n
2) השלמים הם בני מנייה. פונקציה מהשלמים לטבעיים תשלח כל מספר חיובי למספר זוגי כמו ב-1, וכל מספר שלילי למספר אי-זוגי. צריך לבדוק שה-0 יכלל או לא יכלל (תלוי אם אתה מגדיר את הטבעיים עם ה-0 או בלי), אבל הרעיון ברור.
3) עכשיו הטריק היותר רציני: הרציונליים הם בני מנייה. למעשה, יש סיכוי שהוכיחו את זה בחדו"א. לנו הוכיחו את זה באינפי, כדי להוכיח שאם נבנה סדרה של הרציונליים, אז כל הגבולות החלקיים שלה הם הממשיים. לצערי, הפונקציות היותר יפות קשות לכתיבה בפורום, אז נלך על משהו קצת פחות יפה. אני אראה פונקציה חח"ע מהטבעיים לרציונליים ופונקציה חח"ע מהרציונליים לטבעיים. לטובת הדיון, אני אוותר על להוכיח שמכאן נובע שיש פונקציה חח"ע ועל מהאחת לשנייה (זה משפט קנטור-ברנשטיין, ויש לו הוכחה קצת מגעילה, ולחלוטין לא ניתנת להבנה בלי הרבה ציורים אבסטרקטיים). ובכן, פונקציה חח"ע מהטבעיים לרציונליים: f
= n, כמובן. פונקציה חח"ע מהרציונליים לטבעיים:
f(p/q) = 2^p*3^q. כיוון ש-2 ו-3 ראשוניים, לא יכולים להיות שני מספרים שונים שאת שניהם ניתן לבטא כך (הפירוק לראשוניים יחיד), ולכן זו פונקציה חח"ע. (כמובן שמדובר כאן רק ברציונליים החיוביים, אבל זה העקרון.)
לסיכום, הרציונליים בני מנייה.
הממשיים, לעומת זאת, אינם בני מנייה. יש לזה הוכחה מאוד חמודה שנקראת הוכחת האלכסון. היא לא ממש ארוכה או קשה להבנה, אבל אין לי כח לכתוב אותה עכשיו. אולי אחר כך.
עוד דבר עקרוני לדיון הוא שאיחוד של שתי קבוצות בנות מניה הוא קבוצה בת מנייה גם כן, שזה די ברור. (אתה יכול לראות דוגמא שהזוגיים U האי-זוגיים = הטבעיים).
אבל, הממשיים = הרציונליים U האי-רציונליים. ידוע שהרציונליים הם קבוצה בת מנייה. אם גם האי-רציונליים היו קבוצה בת מנייה, היינו מקבלים שהממשיים הם קבוצה בת מנייה, מה שלא נכון. על כן, האי-רציונליים הם קבוצה שאינה בת מנייה, ולמעשה, עוצמת האי-רציונליים היא כמו עוצמת הממשיים.
אגב, עוצמת הטבעיים מסומנת ב-א0 (כן, כן, האות העברית א, כי קנטור היה יהודי), ועוצמת הממשיים - הנקראת גם עוצמת הרצף - מסומנת או באות א או באות c (אני לא סגור אם זה על שם Cantor או על שם continuum, היינו רצף).
נ.ב. כן, כן, צריך לכתוב אי-הרציונליים ולא האי-רציונליים. יופי.