תורת הקבוצות - מה זו בעצם קבוצה אינסופית?

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

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

האתגר שלנו הוא לפרמל מושג אינטואיטיבי, של גודל של קבוצה. בואו נסתכל למשל על הקבוצה \( \left\{ \pi,e,\sqrt{2}\right\} \) - מה הגודל שלה? האינטואיציה שלנו אומרת שהגודל שלה הוא 3 כי יש בה שלושה איברים. האינטואיציה אומרת שלקבוצה הריקה \( \emptyset \) יש 0 איברים ושלקבוצה \( \mathbb{N}=\left\{ 0,1,2,\ldots\right\} \) יש \( \infty \) (“אינסוף”) איברים. אבל אנחנו רוצים לפרמל את האינטואיציה הזו כי זה מה שעושים במתמטיקה.

אם נותנים לנו קבוצה, איך בעצם אנחנו יודעים כמה איברים יש בה? אנחנו סופרים אותם. אני לוקח את האיבר \( \pi \) ואומר “1”, ואז אני לוקח את \( e \) ואומר “2” ואז אני לוקח את \( \sqrt{2} \) ואומר “3” ובכך זה נגמר כי לא נשארו איברים בקבוצה. את מה שעשיתי כאן אפשר לתאר פורמלית בעזרת פונקציה: אני הגדרתי פונקציה \( f:\left\{ \pi,e,\sqrt{2}\right\} \to\left\{ 1,2,3\right\} \) כך ש-

\( f\left(\pi\right)=1 \)

\( f\left(e\right)=2 \)

\( f\left(\sqrt{2}\right)=3 \)

הייתי יכול, כמובן, גם לספור את האיברים בסדר שונה, ואז הייתי מקבל פונקציה אחרת, נאמר \( g:\left\{ \pi,e,\sqrt{2}\right\} \to\left\{ 1,2,3\right\} \) שמוגדרת על ידי

\( g\left(\sqrt{2}\right)=1 \)

\( g\left(\pi\right)=2 \)

\( g\left(e\right)=3 \)

אבל זה לא משנה כלום - הפונקציה \( g \) היא אינדיקציה לכך שהקבוצה היא מגודל 3 בדיוק כפי שהפונקציה \( f \) היא אינדיקציה שכזו.

אם כן, אולי יש לנו הגדרה כללית? נאמר, הקבוצה \( A \) היא מגודל 3 אם קיימת פונקציה \( f:A\to\left\{ 1,2,3\right\} \)? די קל לראות שההגדרה הזו לא עובדת כמות שהיא. למשל, בואו ניקח את הקבוצה \( A=\left\{ e,\pi\right\} \) שיש בה רק שני איברים, אז נביט בפונקציה \( f:\left\{ e,\pi\right\} \to\left\{ 1,2,3\right\} \) שמוגדרת כך:

\( f\left(\pi\right)=1 \)

\( f\left(e\right)=2 \)

זו בעצם אותה פונקציה בדיוק כמו קודם, אז מה השתבש עכשיו? שהאיבר \( 3 \) הוא “מיותר”; בכלל לא השתמשנו בו. באותה מידה יכלנו להגדיר \( f:\left\{ e,\pi\right\} \to\left\{ 1,2\right\} \) וגם זה היה עובד. נראה די ברור איך אפשר לתקן את הבעיה הזו - צריך לדרוש שכל האיברים של \( \left\{ 1,2,3\right\} \) “יהיו בשימוש”, או בניסוח מתמטי - הפונקציה \( f:A\to\left\{ 1,2,3\right\} \) צריכה להיות על.

לרוע המזל, זה עדיין לא מספיק. הנה עוד דוגמא ששוברת את האינטואיציה שלנו, שתתבסס על קבוצה בת ארבעה איברים, \( \left\{ \pi,e,\sqrt{2},42\right\} \): נגדיר \( f:\left\{ \pi,e,\sqrt{2},42\right\} \to\left\{ 1,2,3\right\} \) על ידי

\( f\left(\pi\right)=1 \)

\( f\left(e\right)=2 \)

\( f\left(\sqrt{2}\right)=3 \)

\( f\left(42\right)=3 \)

ושוב - זו אותה פונקציה כמו קודם, רק עם התוספת החדשה \( f\left(42\right)=3 \). מה השתבש הפעם? כמובן, הפעם השתמשתי ב-3 יותר מדי פעמים: גם \( \sqrt{2} \) וגם 42 הלכו אליו. אם הייתי מבצע ספירה בקול רם, מה שהיינו שומעים הוא “אחד, שתיים, שלוש, שלוש…”. זו רמאות ברורה וגם הפתרון ברור - לאסור על \( f \) להחזיר את אותו פלט לשני קלטים שונים. או בניסוח מתמטי: הפונקציה \( f:A\to\left\{ 1,2,3\right\} \) צריכה להיות חד-חד-ערכית.

אפשר לעשות את זה טיפה יותר אלגנטי. כזכור, הגדרה אפשרית למספרים הטבעיים הלכה ככה: \( 0 \) מוגדר להיות הקבוצה הריקה \( \emptyset \), \( 1 \) מוגדר להיות הקבוצה \( \left\{ 0\right\} \) וכן הלאה. באופן כללי, \( n \) מוגדר להיות \( \left\{ 0,1,2,\ldots,n-1\right\} \). אז אם אני מתחיל את המספור שלי מ-0 במקום מ-1, אני יכול לומר ש-\( A \) היא קבוצה מגודל 3 אם קיימת פונקציה חח”ע ועל \( f:A\to3 \) (כלומר, \( f:A\to\left\{ 0,1,2\right\} \)). מכאן אפשר להגדיר קבוצות סופיות: קבוצה \( A \) היא סופית אם קיים מספר טבעי \( n \) כך שקיימת פונקציה חח”ע ועל \( f:A\to n \), ובמקרה זה מסמנים את הגודל של \( A \) בתור \( \left|A\right|=n \).

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

לא ראינו את זה בא, מה?

חלק שני, שבו אנחנו משווים עוצמות

בהגדרה שלי של קבוצה סופית הכלי שבו השתמשתי היה פונקציה חח"ע ועל מהקבוצה \( A \) אל קבוצה ספציפית אחרת של מספרים טבעיים. אבל למה לעצור כאן? האינטואיציה היא שאם קיימת \( f:A\to B \) חח”ע ועל עבור שתי קבוצות \( A,B \) כלשהן, אז הגודל שלהן הוא שווה. הרי מה \( f \) עושה בסך הכל? משנה את השמות של אברי \( A \) כך שמתקבלים כל אברי \( B \) (כולם, כי \( f \) על), ושינוי השמות הזה לא “מאבד” איברים כי \( f \) חח”ע ולכן שני איברים שונים לא “יתמזגו לאחד” אחרי שינוי השמות שלהם.

עבור קבוצות סופיות, ההגדרה הזו עובדת מצוין. בואו ניקח שתי קבוצות סופיות כלשהן, \( A,B \), כך ש-\( \left|A\right|=n \) ו-\( \left|B\right|=m \). נניח עכשיו שקיימת פונקציה חח”ע ועל \( f:A\to B \). מכך ש-\( \left|A\right|=n \) אפשר להסיק שקיימת \( g:n\to A \) חח”ע ועל (ההגדרה אומרת שקיימת פונקציה מ-\( A \) אל \( n \), אבל אפשר לקחת את ההופכי שלה) ומכך ש-\( \left|B\right|=m \) אפשר להסיק שקיימת \( h:B\to m \) חח”ע ועל. ההרכבה \( hfg:n\to m \) נותנת לנו פונקציה חח”ע ועל בין \( n \) ו-\( m \). אז אנחנו נשארים רק עם הצורך להוכיח שאם יש פונקציה חח”ע ועל \( f:n\to m \) אז \( n=m \). בואו נניח בלי הגבלת הכלליות ש-\( n\le m \) ונוכיח באינדוקציה על הגודל של \( n \).

אם \( n=0 \), כלומר \( n=\emptyset \), אז הפונקציה \( f:n\to m \) היחידה שקיימת היא הפונקציה הריקה (כלומר, פונקציה שפורמלית היא יחס שהוא הקבוצה הריקה). אם \( m\ne\emptyset \) הפונקציה הזו לא תהיה על, ולכן \( m=\emptyset=n \).

נניח אם כן שעבור \( n \) הטענה נכונה ונוכיח אותה עבור \( n+1 \). כלומר, נניח שקיימת פונקציה \( f:n+1\to m \) כך ש-\( n+1\le m \) ונוכיח ש-\( n+1=m \). כזכור, \( n+1 \) זו פשוט הקבוצה \( \left\{ 0,1,\ldots,n\right\} \) ואילו \( m \) היא הקבוצה \( \left\{ 0,1,\ldots,m-1\right\} \).

מכיוון ש-\( f \) היא על \( m \), קיים \( k\in\left\{ 0,1,\ldots,n\right\} \) כך ש-\( f\left(k\right)=m-1 \). בואו נבנה מ-\( f \) הזו פונקציה \( g:n\to m-1 \) על ידי כך שניקח את \( f \), נתעלם מהפעולה שלה על \( n \), ואם צריך לתקן את מי ש-\( k \) עבור אליו, נתקן כך:

\( g\left(x\right)=\begin{cases} f\left(n\right) & x=k\\ f\left(x\right) & x\ne k \end{cases} \)

קיבלנו ש-\( g \) הזו היא פונקציה חח”ע ועל מ-\( n \) אל \( m-1 \) ומהנחת האינדוקציה נובע ש-\( n=m-1 \), כלומר \( n+1=m \) וזה מסיים את ההוכחה.

בואו נתפקס עכשיו על מה שהייתה המטרה שלנו פה - הוכחנו שאם קיימת \( f:A\to B \) חח”ע ועל כאשר \( A,B \) הן קבוצות סופיות, אז הגודל שלהן שווה. הנכונות הזו נותנת לנו אומץ לקפוץ אל השלב הבא ולתת הגדרה שהיא תמימה למראה וכמעט ריקה מאינפורמציה, אבל היא מה שינחה אותנו מכאן ואילך: אנחנו אומרים שאם קיימת \( f:A\to B \) חח”ע ועל אז \( A,B \) הן שוות עוצמה ומסמנים זאת \( \left|A\right|=\left|B\right| \) או לפעמים סתם \( A\sim B \). שימו לב שכאן אני לא מניח ש-\( A,B \) סופיות; במילים אחרות, נתתי הגדרה פורמלית לאופן שבו בודקים אם שתי קבוצות אינסופיות הן “מאותו גודל אינסופי”.

נשמע הגיוני ומתבקש? זה לא צריך להיות הגיוני ומתבקש כי דברים מוזרים קורים פה. למעשה, דברים שהיו מוזרים מספיק כדי למשוך את תשומת לבו של גלילאו גלילאי. בספרו האחרון, “שני מדעים חדשים”, הוא מביא (בצורה של דיאלוג, שאוותר עליה) את האבחנה הבאה, שנקראת לרוב “הפרדוקס של גלילאו” כי גלילאו עצמו התייחס אל זה בתור סיבה להפסיק לדבר על קבוצות אינסופיות: הקבוצות \( A=\left\{ 0,1,2,3,4,\ldots\right\} \) של הטבעים ו-\( B=\left\{ 0,1,4,9,16,\ldots\right\} \) של ריבועים של מספרים טבעיים הן שוות עוצמה - הפונקציה \( f:A\to B \) המוגדרת בתור \( f\left(n\right)=n^{2} \) היא בבירור חח”ע ועל. אבל מצד שני, \( B\subsetneq A \) - קיימים ב-\( A \) איברים שלא מופיעים ב-\( B \), כך שאינטואיטיבית, \( B \) קטנה יותר מאשר \( A \). אז מה הולך כאן?

אני אוהב להתמודד עם הפרדוקס הזה באופן הבא: תשכחו לרגע מריבועים. נניח שאני מגדיר פונקציה \( f \) שתחומה \( A \) ופועלת כך: \( f\left(n\right)=n^{\prime} \). מה זה \( n^{\prime} \)? זה פשוט המספר \( n \) כשהוספתי איזה לכלוך (“תג”) מעליו. זה לא מספר שונה, זו מחרוזת שונה. שיטת סימון שונה לאותו מספר. כך למשל \( f\left(15\right)=15^{\prime} \). מה הטווח של \( f \)? בואו נכתוב את שתי הקבוצות זו מעל זו:

\( A=\left\{ 0,1,2,3,\ldots\right\} \)

\( B=\left\{ 0^{\prime},1^{\prime},2^{\prime},3^{\prime},\ldots\right\} \)

הקבוצה \( B \) הזו היא בסך הכל “\( A \) עם לכלוכים קטנים בקצה”. האם יש הבדל מהותי? לא. סתם שיטת סימון משונה, אבל “ברור” שהגודל לא משתנה כתוצאה ממנה.

אה-הא! כעת, הבה ונחליף את הלכלוך הזה של תג בלכלוך שנראה טיפה שונה אבל גם הוא לכלוך: הספרה 2. נקבל:

\( B=\left\{ 0^{2},1^{2},2^{2},3^{2},\ldots\right\} \)

ובעצם קיבלנו פה שוב את \( B \) המקורית, רק עם שיטת כתיב טיפה שונה לאיברים. אז איפה הבעיה מתחילה? אולי הבעיה מתחילה כשמפסיקים להתייחס ל-\( 2 \) בתור “לכלוך” ומתחילים להתייחס אליו בתור “הוראות הפעלה” של איך לחשב את הערכים של אברי \( B \)? אבל למה שתהיה פה בעיה? הרי הערכים השונים שמתקבלים עקב כך לא מתנגשים.

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

עדיין, הביטוי “\( A,B \) הן שוות עוצמה” מאפשר לנו להתייחס לעניין בספקנות ההכרחית. מה זו “עוצמה” (Cardinality באנגלית)? זו מילה חדשה שהכנסנו לדיון בדיוק כדי שנוכל לדבר על “גדלים” של קבוצות אינסופיות. אין לנו מחוייבות לאינטואיציה שהמילה “גודל” נושאת איתה. מצד שני, עכשיו גם קצת פחות ברור על מה אנחנו מדברים - בזמן ש”גודל” הוא מספר טבעי, מה זו “עוצמה”? בינתיים הגדרתי רק מה זה אומר ששתי קבוצות הן בעלות אותה עוצמה, אבל לא מה זו ה”עוצמה” הזו מלכתחילה!

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

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

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

נשתמש בתכונות הללו בחופשיות מכאן ואילך.

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

בואו נחזור לרגע אל הפרדוקס של גלילאו. מה שהיה מוזר בו הוא שגילינו ש-\( A\sim B \) עבור סיטואציה שבה \( B \) היא תת-קבוצה ממש של \( A \) - שכל איבר של \( B \) שייך ל-\( A \), אבל חלק מהאיברים של \( A \) חסרים. תופעה כזו לא יכולה להתרחש בקבוצות סופיות - כבר ראינו שאם ל-\( B \) יש פחות איברים מ-\( A \) כששתיהן סופיות, אז לא קיימת \( f:A\to B \) שהיא חח”ע ועל. אם כן, נראה שיש פה דרך חדשה להגדיר קבוצה אינסופית: קבוצה \( A \) היא אינסופית אם ורק אם קיימת לה תת-קבוצה ממש \( B\subsetneq A \) כך ש-\( A\sim B \). ההגדרה הזו נקראת “אינסופיות דדקינד” על שם המתמטיקאי ריכארד דדקינד שהמציא אותה, והיא יפה כי היא בכלל לא מסתמכת על המספרים הטבעיים כדי להגדיר “גודל” של קבוצות.

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

בשביל לראות למה צריך את ההנחה הזו ומה זה בכלל אומר שצריכים אותה, בואו ננסה להוכיח שאינסופיות “רגילה” גוררת את אינסופיות דדקינד, וההפך. אם קבוצה \( A \) היא אינסופית דדקינד, אז קיימת \( B\subsetneq A \) כך ש-\( A\sim B \). עכשיו, אם \( A \) סופית במובן הרגיל, כלומר \( A\sim n \) עבור \( n \) טבעי כלשהו, אז מה שקורה הוא ש-\( B\sim A\sim n \). מצד שני, אם ניקח את הפונקציה שמראה ש-\( A\sim n \) ונצמצם את התחום שלה ל-\( B \) נקבל התאמה חח”ע ועל בין \( B \) ובין תת-קבוצה ממש של \( n \) (זו תת-קבוצה ממש כי יש \( a\in A\backslash B \) שאת התמונה שלו אף איבר ב-\( B \) לא מקבל, אחרת ההתאמה שמראה ש-\( A\sim n \) לא הייתה חח”ע). במילים אחרות, עברנו מלדבר על \( A,B \) כלליות לדבר על כך שלא ייתכן ש-\( n \) שוות עוצמה לתת-קבוצה ממש של עצמה. את זה אפשר להוכיח באינדוקציה על \( n \) בצורה דומה למה שעשינו קודם.

אם כן, ראינו שאם קבוצה היא אינסופית-דדקינד אז היא גם אינסופית במובן הרגיל. אבל האם ההפך נכון? אני אוכיח את זה בדרך עקיפה, בעזרת טענה אחרת שהיא שימושית באופן כללי, ואותה אוכיח בנפנוף ידיים שמסתמך ברמה כלשהי על אקסיומת הבחירה: אם \( A \) היא קבוצה אינסופית (במובן הרגיל) אז, אינטואיטיבית, היא מכילה “משהו שנראה כמו הטבעיים” ופורמלית: קיימת פונקציה \( f:\mathbb{N}\to A \) שהיא חד-חד-ערכית (לא בהכרח על). לפונקציה כזו קוראים שיכון.

למה הטענה הזו מספיקה כדי להראות שאם \( A \) אינסופית, אז היא אינסופית-דדקינד? כי אם \( A \) אינסופית ו-\( f \) כזו קיימת, אפשר לתאר את התמונה שלה בתור \( \left\{ a_{0},a_{1},a_{2},\ldots\right\} \), ואז אפשר לעשות את התעלול הבא: להגדיר פונקציה \( g:A\to A \) על ידי

\( g\left(x\right)=\begin{cases} a_{k+1} & x=a_{k}\\ x & \text{else} \end{cases} \)

כלומר, מה ש-\( g \) עושה על אברי \( A \) הוא זה: על רובם היא לא עושה כלום ומשאירה אותם ללא שינוי; אבל אם היא מקבלת איבר מתוך \( \left\{ a_{0},a_{1},a_{2},\ldots\right\} \), היא מחזירה את האיבר הבא בתור. קל לראות ש-\( g\left(A\right)=A\backslash\left\{ a_{0}\right\} \) וש-\( g \) היא חח”ע, ולכן קיבלנו תת-קבוצה ממש של \( A \) (כל \( A \) למעט \( a_{0} \)) ששקולה ל-\( A \) - אינסופיות-דדקינד בפעולה.

אוקיי, אז איך מוכיחים שאם \( A \) אינסופית אפשר לשכן את \( \mathbb{N} \) בתוכה? הנה הוכחה בנפנוף ידיים: מכיוון ש-\( A \) לא ריקה, יש בה איבר, נקרא לו \( a_{0} \). אז נגדיר \( f\left(0\right)=a_{0} \). עכשיו, גם \( A\backslash\left\{ a_{0}\right\} \) לא ריקה (כי \( A \) אינסופית, לא ייתכן ש-\( a_{0} \) היה האיבר היחיד בה) אז קיים איבר \( a_{1}\in A\backslash\left\{ a_{0}\right\} \) ואפשר להגדיר \( f\left(1\right)=a_{1} \). ככה אפשר להמשיך: נניח שכבר הגדרתי את \( f \) עד לערך \( n \), אז נתבונן ב-\( A\backslash\left\{ a_{0},\ldots,a_{n}\right\} \). זו קבוצה לא ריקה כי אם הייתה ריקה, \( A \) הייתה שווה לקבוצה הסופית \( \left\{ a_{0},\ldots,a_{n}\right\} \), ולכן קיים בקבוצה הזו איבר \( a_{n+1} \) ואפשר להגדיר \( f\left(n+1\right)=a_{n+1} \), וכך זה נמשך עד אינסוף.

נשמע סביר? בהחלט. אז למה זו הוכחה בנפנוף ידיים? כי כזכור, בתורת הקבוצות צריך לבנות דברים באופן מסודר, מתוך אקסיומות, ולא סתם לומר “אני יכול לתאר את זה ולכן זה קיים”, מה שמביא עלינו זוועות כמו הפרדוקס של ראסל. כאן אני בונה פונקציה \( f \), שהיא בעצם קבוצה של זוגות סדורים מהצורה \( \left(n,a_{n}\right) \). אנחנו יודעים לבנות זוגות סדורים, ועבור כל זוג סדור אנחנו גם יודעים לבנות את הקבוצה שהוא האיבר היחיד שלה, ואנחנו יודעים לאחד מספר סופי של קבוצות - אבל ב-\( f \) צריך להיות מספר אינסופי של זוגות סדורים, ואת זה אנחנו כבר לא יודעים לעשות מהאקסיומות הבסיסיות.

בניה מחוכמת יותר, בעזרת אקסיומות מחוכמות יותר, כבר דורשת שנתבסס על משהו קיים. אני לא יכול סתם כך להגיד “\( A \) לא ריקה אז יש בה איזה איבר ונקרא לו \( a_{0} \)”; בשביל לבנות פורמלית את \( f \) אני צריך משהו קיים שנותן לי במפורש את \( a_{0} \) ואני יכול להסתמך עליו. המשהו הזה הוא, ובכן, פונקציה: פונקציה \( g \) שיודעת לקבל תת-קבוצות של \( A \) ולהחזיר איברים שנמצאים בהן. זה בדיוק מה שאקסיומת הבחירה מדברת עליו. אקסיומת הבחירה אומרת במפורש את הדבר הזה: אם \( \left\{ A_{i}\right\} _{i\in\Lambda} \) היא משפחה של קבוצות כך ש-\( A_{i}\ne\emptyset \) לכל \( i\in\Lambda \) אז קיימת \( g:\Lambda\to\bigcup_{i\in\Lambda}A_{i} \) כך ש-\( g\left(i\right)\in A_{i} \) לכל \( i\in\Lambda \). במקרה שלנו, משפחת הקבוצות היא פשוט \( \mathcal{P}\left(A\right)\backslash\left\{ \emptyset\right\} \) - כל תתי-הקבוצות של \( A \) למעט הקבוצה הריקה.

עכשיו, במקום לומר “\( A\backslash\left\{ a_{0},\ldots,a_{n}\right\} \) לא ריקה אז קיים בה \( a_{n+1} \) ולכן נגדיר \( f\left(n+1\right)=a_{n+1} \)” אני יכול להגיד משהו פשוט יותר: “נגדיר \( f\left(a_{n+1}\right)=g\left(A\backslash\left\{ a_{0},\ldots,a_{n}\right\} \right) \)”. זו כבר הגדרה מאוד קונקרטית שניתן לבצע - אבל בשביל זה צריך שהפונקציה \( g \) תתקיים מלכתחילה.

אפשר היה לעשות את זה פשוט יותר. לא חייבים את אקסיומת הבחירה המלאה בכל עוצמתה - אפשר להחליף אותה במשהו שנקרא “אקסיומת הבחירה התלויה” (Axiom of dependent choice). לא אכנס לזה הפעם. אבל בלי סוג כלשהו של אקסיומת הבחירה, זה פשוט לא עובד. זה לא שאם אין לנו את אקסיומת הבחירה ו-\( A \) אינסופית אז אין בה עותק של המספרים הטבעיים; זה שאם אין לנו את אקסיומת הבחירה אנחנו פשוט לא מסוגלים לבנות פורמלית את הפונקציה שמראה לנו את השיכון הזה. גם בהגדרה של אינסופיות-דדקינד, מה ש”נשבר” ללא אקסיומת הבחירה הוא לא שלא קיימת תת-קבוצה \( B \) שהיא “מאותו הגודל” של \( A \), אלא שאין לנו דרך לבנות פורמלית את הפונקציה שמראה לנו ש-\( A\sim B \) (ובלי פונקציה כזו פשוט אין משמעות לאמירה ששתי הקבוצות הן “מאותו הגודל”; הרי מהגדרת “אותו הגודל” בהתבסס על קיום פונקציה שכזו התחלנו).

זה מקום טוב לעצור בו, אבל לפני כן, בואו נחדד עוד קצת את המשמעות של מה שהוכחנו. ראינו שאם \( A \) היא קבוצה אינסופית כלשהי, אז היא מכילה עותק של \( \mathbb{N} \), כלומר אינטואיטיבית, \( A \) גדולה “לפחות כמו” \( \mathbb{N} \). כלומר, אינטואטיבית, \( \mathbb{N} \) היא הקבוצה האינסופית “הקטנה ביותר”. איך מפרמלים את הרעיון הזה עד הסוף? את זה כבר כדאי לדחות לפעם הבאה.