תורת הקבוצות - מכפלות קרטזיות כלליות

בתחילת סדרת הפוסטים שלי על תורת הקבוצות הגדרתי את המושג של מכפלה קרטזית. הרעיון היה זה: אם \( A,B \) הן קבוצות, המכפלה הקרטזית שלהן היא הקבוצה \( A\times B\triangleq\left\{ \left(a,b\right)\ |\ a\in A,b\in B\right\} | \) של כל הזוגות הסדורים שבהם האיבר השמאלי נלקח מ-\( A \) והאיבר הימני נלקח מ-\( B \). זה היה מושג חשוב ושימש אותנו בכל מה שעשינו משם והלאה, ובפרט השתמשנו בו כדי להגדיר פונקציות. עכשיו המעגל הולך להיסגר, כשנשתמש בפונקציות כדי להכליל את מושג המכפלה הקרטזית למספר כלשהו של קבוצות, לאו דווקא שתיים.

אני יכול כבר עכשיו לתת את ההגדרה הכללית, אבל לא נבין ממנה כלום בשלב הזה, ובפרט לא למה היא כל כך מסובכת. אז בואו נתחיל בקטן. מכיוון שכבר הגדרנו מכפלה של שתי קבוצות, בואו נגדיר מכפלה של שלוש קבוצות. ברור לגמרי (אני מקווה!) מה האינטואיציה מאחורי הגדרה כזו - אני רוצה אוסף של שלשות סדורות כמו שבמכפלה קרטזית של שתי קבוצות היה לי אוסף של זוגות סדורים. כלומר, אם \( A,B,C \) קבוצות אני רוצה שיתקיים משהו כמו \( A\times B\times C=\left\{ \left(a,b,c\right)\ |\ a\in A,b\in B,c\in C\right\} \) כאשר הרעיון מאחורי שלשה סדורה היא ששתי שלשות סדורות הן שוות אם ורק אם הן שוות “רכיב-רכיב”, כלומר \( \left(a_{1},b_{1},c_{1}\right)=\left(a_{2},b_{2},c_{2}\right) \) אם ורק אם \( a_{1}=a_{2} \) וגם \( b_{1}=b_{2} \) וגם \( c_{1}=c_{2} \).

לכאורה יש לנו דרך פשוטה מאוד לעשות את זה: כבר הגדרנו מכפלה קרטזית של שתי קבוצות, למה לא להפעיל את ההגדרה שוב? תחשבו שניה מה קורה עם חיבור: אנחנו מגדירים חיבור רק עבור זוג מספרים, אבל מכאן קל להכליל לשלושה: \( a+b+c \) זה פשוט \( \left(a+b\right)+c \), כלומר קודם כל מחברים את \( a \) עם \( b \), מקבלים “תוצאת ביניים” ומחברים אותה עם \( c \). גם עבור מכפלה קרטזית זה סוג של עובד, בערך… אבל לא מספיק טוב. כי בואו נראה מה קורה על פי ההגדרה היבשה: מכיוון ש-\( A\times B\triangleq\left\{ \left(a,b\right)\ |\ a\in A,b\in B\right\} | \) אנחנו הולכים לקבל ש-

\( \left(A\times B\right)\times C=\left\{ \left(\left(a,b\right),c\right)\ |\ a\in A,b\in B,c\in C\right\} | \)

כלומר, מבחינה פורמלית, \( \left(A\times B\right)\times C \) הוא לא אוסף של שלשות סדורות אלא עדיין אוסף של זוגות סדורים כך שהאיבר השמאלי בכל זוג הוא בעצמו זוג סדור. זה… לא נשמע בעייתי במיוחד, למה בעצם לא להגדיר שלשה סדורה בדיוק בצורה הזו? הרי גם “זוג סדור” זה לא איזה מושג קדוש שהגיע אלינו מהחלל החיצון אלא מושג ש”מימשנו” בצורה די מכוערת עם קבוצות. ובכן, יש שתי התנגדויות להגדרה הזו: הראשונה, שאז מכפלה קרטזית לא תהיה אסוציאטיבית: \( A\times\left(B\times C\right) \) הוא אוסף של זוגות סדורים שבהם הרכיב הימני הוא בעצמו זוג סדור. אבל בינינו, זו התנגדות די קטנונית, נכון? פורמליזם שמורמליזם, אפשר בלי הרבה מאמץ לטפל בבעיה הזו. מה שמביא אותנו להתנגדות השניה: פשוט לא צריך לטפל בכל הקטנוניות הזו כי ההגדרה הכללית שאביא עוד מעט מטפלת בכל זה “על הדרך” ובנוסף לכך מאפשרת לי להגדיר מכפלה קרטזית של מספר אינסופי של קבוצות.

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

אבל מה זה בעצם אומר, מכפלה של אינסוף קבוצות? כדי לתת אינטואיציה בואו נתחיל עם סימון כללי למכפלה של מספר סופי של קבוצות. נניח שיש לי את הקבוצות \( A_{1},A_{2},\ldots,A_{n} \). האינטואיציה שלי היא שמכפלה של כולן אמורה להיות אוסף של \( n \)-יות סדורות (“\( n \)-יה” הוא סימון מקובל בעברית! נשבע!). כלומר, שזה אמור להיות משהו כזה:

\( A_{1}\times A_{2}\times\ldots\times A_{n}=\left\{ \left(a_{1},a_{2},\ldots,a_{n}\right)\ |\ a_{1}\in A_{1},a_{2}\in A_{2},\ldots,a_{n}\in A_{n}\right\} \)

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

\( A_{1}\times A_{2}\times\ldots=\left\{ \left(a_{1},a_{2},\ldots\right)\ |\ a_{1}\in A_{1},a_{2}\in A_{2},\ldots\right\} \)

כל מה שעשיתי פה היה להסיר את האיבר ה”אחרון” בסדרה. אבל איך אני יכול לפרמל את זה עכשיו?

התשובה קלה - פונקציות. בואו נסתכל שניה על ה-\( n \)-יה הסדורה \( \left(a_{1},a_{2},\ldots,a_{n}\right) \). מה זה הדבר הזה, בעצם? אלו הרבה ערכים שונים כשלכל אחד מהם יש מקום בתוך ה-\( n \)-יה; המקום הזה מסומן על ידי מספר טבעי בין 1 ל-\( n \) - זה האינדקס שמתאר את המקום הזה. \( a_{3} \) הוא האיבר במקום מס’ 3, כלומר האיבר שמאונדקס על ידי המספר 3. אפשר לחשוב על התהליך שבו אני אומר לעצמי “הממממ, מאוד מעניין מה יש במקום מספר 3! אולי אבדוק מה נמצא שם?” בתור תהליך של הפעלת פונקציה: הקלט הוא המספר 3 (האינדקס של המקום שאני רוצה לבדוק) והפלט הוא האיבר שנמצא במקום הזה, שמובטח לי ששייך לקבוצה \( A_{3} \).

אז בואו נפרמל את המושג של \( n \)-יה באמצעות פונקציה: הקלט שפונקציה כזו יכולה לקבל הוא אינדקס, כלומר במקרה של \( n \)-יה זה איבר ששייך לקבוצה \( \left\{ 1,2,\ldots,n\right\} \). הפלט? הוא משהו ששייך לאחת מבין הקבוצות \( A_{1},A_{2},\ldots,A_{n} \); לכן אם אני בא להגדיר את הטווח של הפונקציה, הוא צריך לכלול את האיחוד של הקבוצות הללו ואין צורך בעוד איברים. מכאן שפורמלית, \( n \)-יה סדורה כזו היא פשוט פונקציה \( f:\left\{ 1,\ldots,n\right\} \to\bigcup_{i=1}^{n}A_{i} \)

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

\( A_{1}\times A_{2}\times\ldots\times A_{n}\triangleq\left\{ f:\left\{ 1,\ldots,n\right\} \to\bigcup_{i=1}^{n}A_{i}\ |\ \forall i\in\left\{ 1,\ldots,n\right\} :f\left(i\right)\in A_{i}\right\} \)

שימו לב לתנאי שבצד ימין של הסוגריים המסולסלים: הוא אומר שלכל אינדקס \( i \), האיבר \( f\left(i\right) \) אכן שייך לקבוצה \( A_{i} \) (הרי בתיאוריה הוא לא חייב להיות שייך אליה, הוא רק צריך להיות שייך לאחת מהקבוצות \( A_{1},\ldots,A_{n} \)).

האם הכתיב הזה מסורבל? בוודאי! אז בואו נעבור למקרה האינסופי, שבו הכתיב נהיה פשוט יותר. בשביל לפשט עוד יותר, אני אתחיל את האינדקסים מאפס במקום מ-1 כי אצלי הטבעיים כוללים את 0:

\( A_{0}\times A_{1}\times\ldots\triangleq\left\{ f:\mathbb{N}\to\bigcup_{i=0}^{\infty}A_{i}\ |\ \forall i\in\mathbb{N}:f\left(i\right)\in A_{i}\right\} \)

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

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

אז אני הולך לסבך טיפה את הסימונים בהגדרה על מנת להגיע למקרה הכללי ביותר, זה שבו האינדקסים לא צריכים להיות הקבוצה \( \left\{ 1,\ldots,n\right\} \) או הקבוצה \( \mathbb{N} \) אלא הם פשוט קבוצה כללית כלשהי \( \Lambda \). אני לא מניח כלום על ה-\( \Lambda \) הזו; רק שזו קבוצה של איברים. כמקודם, אני מסמן ב-\( i \) איבר כלשהו בקבוצה הזו. עכשיו ניקח את ההגדרה של מכפלה קרטזית למקרה האינסופי ונדחוף את \( \Lambda \) הזו שם. נקבל:

\( \prod_{i\in\Lambda}A_{i}\triangleq\left\{ f:\Lambda\to\bigcup_{i\in\Lambda}A_{i}\ |\ \forall i\in\Lambda:f\left(i\right)\in A_{i}\right\} \)

ההבדל הכי גדול בין ההגדרה הזו לקודמת הוא בכלל באופן שבו אני מסמן את המכפלה - אני משתמש בסימן \( \prod \) שמיועד לתאר מכפלות עם אינדקס, כמו ש-\( \sum \) משמש לתיאור סכומים עם אינדקס. פרט לכך הסימונים די דומים, ואני מקווה שעכשיו ההגדרה הזו די פשוטה; חשבו מה היה קורה אם הייתי מתחיל איתה את הפוסט - האם גם אז היה ברור מה הולך פה בכלל?

עכשיו, בואו נדבר על מקרה פרטי של מכפלות כאלו - המקרה שבו מכפילים את אותה קבוצה \( A \) בעצמה. מתבקש אינטואיטיבית להשתמש בסימן כמו \( A^{2} \) כדי לתאר את \( A\times A \) או \( A^{3} \) כדי לתאר את \( A\times A\times A \) וכן הלאה, אבל מה לגבי מכפלות אינסופיות? ובכן, תכף נראה שזה נותן לנו אינטואיציה לסימון מועיל באופן כללי.

ראשית, בואו ניקח את ההגדרה של מכפלה קרטזית כללית שכתבתי למעלה ונכתוב אותה מחדש במקרה שבו \( A_{i}=A \) לכל \( i\in\Lambda \). נעבור מההגדרה הזו:

\( \prod_{i\in\Lambda}A_{i}\triangleq\left\{ f:\Lambda\to\bigcup_{i\in\Lambda}A_{i}\ |\ \forall i\in\Lambda:f\left(i\right)\in A_{i}\right\} \)

אל ההגדרה הזו:

\( \prod_{i\in\Lambda}A\triangleq\left\{ f:\Lambda\to A\right\} \)

תראו כמה שהכל נהיה פשוט פתאום: כבר לא צריך שהפונקציה \( f \) תלך אל איחוד כלשהו ולא צריך לדרוש שהתמונות של \( f \) על איברים ספציפיים יהיו שייכים לקבוצות ספציפיות; המכפלה הקרטזית הפכה להיות פשוט קבוצת כל הפונקציות מ-\( \Lambda \) אל \( A \).

עכשיו, מה זה \( A^{2} \)? אפשר לחשוב על זה בתור המכפלה הקרטזית \( A_{0}\times A_{1} \) כאשר \( A_{0}=A_{1}=A \). כלומר, בתור \( \prod_{i\in\left\{ 0,1\right\} }A \), כלומר בתור קבוצת הפונקציות \( f:\left\{ 0,1\right\} \to A \). עכשיו, בואו ניזכר שהגדרתי את 2 בתור הקבוצה \( \left\{ 0,1\right\} \). אז בעצם כשאני כותב \( A^{2} \) אני כותב \( A^{\left\{ 0,1\right\} } \). במילים אחרות, \( A^{\left\{ 0,1\right\} } \) היא קבוצת כל הפונקציות מ-\( \left\{ 0,1\right\} \) אל \( A \).

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

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

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

ובכן, הנה יש לנו טענה: אם \( \Lambda \) היא קבוצת אינדקסים כלשהי ו-\( \left\{ A_{i}\right\} _{i\in\Lambda} \) משפחה של קבוצות כך ש-\( A_{i}\ne\emptyset \) לכל \( i\in\Lambda \) אז \( \prod_{i\in\Lambda}A_{i}\ne\emptyset \). טענה פשוטה, לא? הנה הוכחה במקרה של שתי קבוצות: אם \( A\ne\emptyset \) אז קיים \( a\in A \) ואם \( B\ne\emptyset \) אז קיים \( b\in B \) ולכן \( \left(a,b\right)\in A\times B \) ולכן \( A\times B\ne\emptyset \). פשוט ומובן מאליו, לא?

ובכן, בואו ננסה גם באופן כללי: אם \( A_{i}\ne\emptyset \) לכל \( i\in\Lambda \) אז קיים \( a_{i}\in A_{i} \) לכל \( i\in\Lambda \) ולכן אם נגדיר פונקציה \( f:\Lambda\to\bigcup A_{i} \) על ידי \( f\left(i\right)=a_{i} \) נקבל ש-\( f\in\prod_{i\in\Lambda}A_{i} \) ולכן \( \prod_{i\in\Lambda}A_{i}\ne\emptyset \). פשוט וקל. לא?

לא.

ממש ממש לא.

הו, כמה שזה לא פשוט וקל.

אבל… אבל… למה, בעצם? מה שגוי ב”הוכחה” שלמעלה? צעד אחד, שמבוצע כל כך מהר שקשה לשים אליו לב: הקפיצה מ”נגדיר פונקציה \( f \) על ידי \( f\left(i\right)=a_{i} \)” אל “נקבל ש-\( f\in\prod_{i\in\Lambda}A_{i} \)”. כי צריך לזכור שבתורת הקבוצות, זה שהגדרנו משהו לא אומר שהוא קיים.

זוכרים את הפרדוקס של ראסל? כל הצרות שלנו התחילו מכך שנתנו הגדרה פשוטה עד כדי גיחוך למשהו, והנחנו שזה אומר שהמשהו הזה קיים; ואז חיש קל הקיום שלנו הוביל לסתירה. זה אילץ אותנו לזנוח את כל גישת ה”אם אפשר להגדיר משהו אז אוטומטית נובע שהוא קיים” - היא מובילה ליותר מדי מוקשים. אז זה שהגדרתי את \( f \) עדיין לא מבטיח לי שהיא קיימת; צריך להוכיח את זה מתוך האקסיומות של תורת הקבוצות.

עבור המקרה של מכפלה של מספר סופי קבוצות קל להוכיח את זה. נניח שאני מכפיל את הקבוצות \( A_{1},\ldots,A_{n} \). ראשית צריך להוכיח שהמספרים \( 1,\ldots,n \) קיימים אבל זה קל; זה נובע מהאקסיומה לפיה הקבוצה הריקה \( \emptyset \) קיימת, ואז מאקסיומות הזיווג (אם \( a,b \) קיימים אז גם \( \left\{ a,b\right\} \) קיימת; ובפרט אם \( a \) קיים גם \( \left\{ a\right\} \) קיימת) והאיחוד, שמאפשרות לנו לבנות מתוך \( n \) את \( n+1\triangleq n\cup\left\{ n\right\} \).

עכשיו, נתחיל מזה שהקבוצה \( \emptyset \) קיימת. מכיוון ש-\( A_{1}\ne\emptyset \) אז קיים \( a_{1}\in A_{1} \) ולכן הזוג \( \left(1,a_{1}\right) \) קיים. למה בעצם הזוג הסדור קיים? בואו ניזכר בהגדרה שנתתי לזוג סדור: \( \left(a,b\right)=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \). אקסיומת הזיווג עושה פה את העבודה: מתוך \( a,b \) היא בונה לנו את \( \left\{ a\right\} \) ואת \( \left\{ a,b\right\} \) ואז משני אלו היא בונה את הקבוצה של \( \left(a,b\right) \). אז זה קל.

עכשיו, אקסיומת הזיווג נותנת לנו את הקבוצה \( \left\{ \left(1,a_{1}\right)\right\} \). בעזרת זיווג אפשר לבנות גם את \( \left\{ \left(2,a_{2}\right)\right\} \) ואז בעזרת איחוד לקבל את \( \left\{ \left(1,a_{1}\right),\left(2,a_{2}\right)\right\} \). אפשר להמשיך ככה לכל הקבוצות ואחרי מספר סופי של צעדים נגיע לקבוצה \( \left\{ \left(1,a_{1}\right),\ldots,\left(n,a_{n}\right)\right\} \) שהיא הפונקציה המבוקשת.

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

ובכן, מה האקסיומה הזו? הנה ניסוח מדויק של מה שאנחנו צריכים: אם \( \left\{ A_{i}\right\} _{i\in\Lambda} \) היא משפחה של קבוצות כך ש-\( A_{i}\ne\emptyset \) לכל \( i\in\Lambda \) אז קיימת \( f:\Lambda\to\bigcup_{i\in\Lambda}A_{i} \) כך ש-\( f\left(i\right)\in A_{i} \) לכל \( i\in\Lambda \). לאקסיומה הזו יש שם: אקסיומת הבחירה. ומה שראינו בפוסט הזה הוא שהיא שקולה לטענה שמכפלה קרטזית כללית של קבוצות היא לא ריקה אם כל הקבוצות במכפלה לא ריקות.

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

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