תורת הקבוצות - מחלקות, אקסיומת ההחלפה ואינדוקציה ורקורסיה על-סופיות

מה זו מחלקה ולמה זו לא רמאות

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

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

עכשיו, בואו נסתכל על אוסף כל הסודרים, שאני מכנה \( \text{Ord} \). האם הוא קבוצה? ובכן, ראינו בפוסט מוקדם יותר שאם יש לנו קבוצה \( A \) של סודרים, גם \( \bigcup A \) היא סודר. כלומר, גם \( \bigcup\text{Ord} \) צריך להיות סודר. אבל אם הוא סודר, יש לו עוקב, \( \bigcup\text{Ord}+1 \). מכיוון שגם העוקב הזה הוא סודר, הוא שייך לקבוצת כל הסודרים, \( \text{Ord} \), ולכן נקבל \( \bigcup\text{Ord}+1\in\text{Ord}\subseteq\bigcup\text{Ord} \), כלומר \( \bigcup\text{Ord}+1<\bigcup\text{Ord} \) ומצד שני \( \bigcup\text{Ord}<\bigcup\text{Ord}+1 \) וזה כמובן בלתי אפשרי. קיבלנו סתירה בסגנון הפרדוקס של ראסל שמראה לנו ש-\( \text{Ord} \) לא יכול להיות קבוצה. אז מה הוא כן?

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

יש לי פוסטים על לוגיקה מסדר ראשון, ולכן כאן אני אסתפק בתיאור קצר יחסית. האובייקט הבסיסי בלוגיקה מסדר ראשון הוא נוסחה, שהיא סדרה סופית של תווים. יש לנו תווים שמתארים משתנים, למשל \( x,y,z,A,B,C \) וכדומה (אפשר להניח שיש לנו אינסוף כאלו). בין כל שני משתנים אפשר לכתוב אחד משני סימני יחס: או לכתוב \( x=y \) או לכתוב \( x\in y \). שני הביטויים הללו הם נוסחאות הבסיס שלנו - כלומר, כל נוסחת בסיס \( \varphi \) מורכבת משני משתנים עם אחד משני סימני היחס ביניהם. הרעיון בנוסחאות בסיס הוא שבהינתן השמה למשתנים כל נוסחת בסיס מקבלת ערך שהוא או “אמת”, T או “שקר”, F; אם שמנו במשתנה \( x \) את הקבוצה \( a \) ושמנו במשתנה \( y \) את הקבוצה \( b \), אז הנוסחה \( x=y \) מקבלת ערך “אמת” רק אם \( a,b \) הן אותה קבוצה בדיוק, ו-\( x\in y \) מקבלת ערך “אמת” רק אם הקבוצה \( a \) היא איבר של הקבוצה \( b \).

מנוסחאות בסיס אפשר לבנות נוסחאות מורכבות יותר בעזרת קשרים לוגיים: \( \neg\varphi,\varphi\wedge\psi,\varphi\vee\psi,\varphi\to\psi,\varphi\leftrightarrow\psi \). הקשרים הללו הם פונקציות על ערכי אמת: \( \neg \) (“שלילה”) הופך T ל-F ו-F ל-T; \( \wedge \) (“וגם”) מחזיר T רק אם שני הקלטים היו T; \( \vee \) (“או”) מחזיר F רק אם שני הקלטים היו F, \( \to \) (“גרירה”) מחזיר F רק אם הקלט השמאלי היה T והימני היה F; ו-\( \leftrightarrow \) (“שקילות”) מחזיר T רק אם שני הקלטים שווים.

המרכיב האחרון בבניית נוסחת הוא כמתים. אם \( \varphi \) היא נוסחה, אז גם \( \forall x\varphi \) (“לכל \( x \) מתקיים \( \varphi \)”) ו-\( \exists x\varphi \) (“קיים \( x \) שעבורו מתקיים \( \varphi \)”) הן נוסחאות. \( \forall x\varphi \) מקבלת ערך T רק אם לכל קבוצה שמציבים במקום \( x \) בנוסחה \( \varphi \) מקבלים ערך T, ו-\( \exists x\varphi \) מקבלת ערך T רק אם קיימת קבוצה שאם מציבים אותה במקום \( x \) בנוסחה \( \varphi \) מקבלים ערך T.

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

כרגע, אבל, אני לא מניח עוד הנחות על היקום המתמטי שלנו חוץ מזה שכל איבריו הם קבוצות. אני מסמן אותו ב-\( V \) וחסל. כזכור, \( V \) הזה לא יכול להיות קבוצה (“קבוצת כל הקבוצות” לא קיימת), אבל קל לתת נוסחה ש”מתארת” אותו: \( x=x \). הנוסחה הזו נכונה לכל איבר של \( V \), ולכן אפשר לתאר את \( V \) בתור “אוסף כל האיברים שמקיימים \( x=x \)”, או אפילו להתחצף ולכתוב \( V=\left\{ x\ |\ x=x\right\} \). הכתיב הזה הוא חצוף משתי סיבות: ראשית, כי אני מערבב בין \( x \) שהוא סימן של משתנה (מה שמופיע בנוסחה \( x=x \)) ובין \( x \) שהוא סימון של איבר קונקרטי של \( V \) (מה שמופיע בצד שמאל) אבל זה לא נורא. מה שבאמת נורא הוא שאני משתמש בכתיב הסוגריים המסולסלים שמשמש אותנו להגדיר קבוצות, למרות ש-\( V \) היא לא קבוצה. ומה שהכי נורא זה שאני אשתמש בסימון כמו \( x\in V \) כדי לתאר שייכות למחלקה. כל זה נראה לגמרי כאילו אני מתייחס למחלקות בתור קבוצות. אז למה זה בסדר? ובכן, כי כל מה שאני עושה עם מחלקות זה בסך הכל כתיב מקוצר. אני יכול להעלים את הכתיב המקוצר הזה ולהישאר במקומו עם נוסחאות לוגיות והכל יעבוד באותה מידה בדיוק.

בואו נראה דוגמא יותר קונקרטית - הסודרים. כשאני כותב \( \alpha\in\text{Ord} \), כלומר “\( \alpha \) הוא סודר”, למה אני מתכוון? אם נחזור להגדרה, סודר הוא קבוצה שהיא 1) טרנזיטיבית ו-2) סדורה בסדר מלא על ידי \( \in \). את שני אלו אפשר לנסח באמצעות נוסחה לוגית:

\( \forall\beta\forall\gamma\left(\left(\gamma\in\beta\wedge\beta\in\alpha\right)\to\gamma\in\alpha\right)\wedge\forall\beta\forall\gamma\left(\left(\beta\in\alpha\wedge\gamma\in\alpha\right)\to\left(\beta\in\gamma\vee\gamma\in\beta\right)\right) \)

במקום לכתוב את כל הנוסחה הזו, אפשר לכתוב פשוט \( \alpha\in\text{Ord} \); זה סימון מקוצר מוסכם. זה לא אומר ש-\( \text{Ord} \) היא קבוצה; כלומר, זה לא אומר שיש איבר ביקום שהאיברים שלו הם בדיוק האיברים של \( \text{Ord} \). הטענה שיש כזה איבר מנוסחת כך:

\( \exists A\left(\alpha\in A\leftrightarrow\alpha\in\text{Ord}\right) \)

כאשר כאמור, ה-\( \alpha\in\text{Ord} \) הוא פשוט העתק-הדבק של הנוסחה הגדולה מקודם. עכשיו, מה שראינו הוא שהנוסחה הזו של ה-\( \exists A \) היא שקר, כלומר לא קיימת \( A \) כזו. זו הסיבה שאנחנו אומרים ש-\( \text{Ord} \) היא “מחלקה ממש”.

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

אקסיומת ההחלפה

מבין כל האקסיומות של צרמלו-פרנקל שתיארתי בסדרת הפוסטים הזו, אקסיומת ההחלפה היא זו שהכי חיפפתי וטרם הצגתי בצורה פורמלית, למרות השימושיות הרבה שלה. סוף סוף הגיע הזמן להציג אותה פורמלית, אז כמובן שכדאי להתחיל מהצגה לא פורמלית: בהצגה הזו, אקסיומת ההחלפה אומרת שאם מחלקה \( F \) היא פונקציה ו-\( A \) היא קבוצה, אז \( F\left(A\right) \) היא קבוצה.

אבל רגע, מה זאת אומרת “מחלקה \( F \) היא פונקציה”? הרי “פונקציה” הוגדרה בתור סוג של יחס, שהוא קבוצה. איך משהו שאיננו קבוצה יכול להיות פונקציה? אנחנו שוב מותחים את השימוש בשפה שלנו. מה שקורה בפועל הוא ש-\( F \) כזו היא סימון מקוצר לנוסחה \( \varphi\left(x,y,a_{1},\ldots,a_{n}\right) \). הכתיב הזה עם הסוגריים אומר “יש בנוסחה \( \varphi \) את המשתנים החופשיים \( x,y,a_{1},\ldots,a_{n} \)” כש”משתנה חופשי” הוא משתנה שלא נופל תחת הטווח של כמת עם השם שלו. למשל בנוסחה \( \forall x\left(x=y\right) \) המשתנה \( y \) חופשי והמשתנה \( x \) לא (אם ההגדרות הללו לא ברורות באמת שכדאי לקרוא קודם על לוגיקה מסדר ראשון, זה לא כזה קשה!)

בנוסחה \( \varphi\left(x,y,a_{1},\ldots,a_{n}\right) \) הזו אני חושב על \( x,y \) בתור האיברים של הזוג ש-\( \varphi \) מגדירה, ועל \( a_{1},\ldots,a_{n} \) בתור “פרמטרים” שמאפיינים את \( \varphi \). למשל, הנוסחה שהמשתנים שלה הם רק \( x,y \) (בלי פרמטרים)

\( x\in y\wedge\forall z\in x\left(z\in y\right)\wedge\forall z\in y\left(z=x\vee z\in x\right) \)

מה היא אומרת? ש-\( y=x\cup\left\{ x\right\} \) (מה שעבור סודרים סימנתי ב-\( y=x+1 \) אבל כאן אנחנו עוסקים בקבוצות כלליות, לאו דווקא סודרים). כלומר, \( \varphi\left(x,y\right) \) מקבלת ערך T אם ורק אם \( y=x\cup\left\{ x\right\} \). אפשר גם לסמן את זה \( \left(x,y\right)\in F \), כפי שכבר עשיתי קודם עם מחלקות.

עכשיו, קל להוכיח שאם \( \varphi\left(x,y_{1}\right) \) מקבלת ערך T וגם \( \varphi\left(x,y_{2}\right) \) מקבלת ערך T (עבור הצבות קונקרטיות של קבוצות \( x,y_{1},y_{2} \) למשתנים) אז \( y_{1}=y_{2} \); זו בדיוק התכונה שאנחנו דורשים מפונקציות. אז אפשר להשתמש בסימון \( F\left(x\right) \) כדי לציין את \( y \), ואפשר לכתוב \( F\left(x\right)=x\cup\left\{ x\right\} \) ויהיה ברור אל מה הכוונה אפילו אם \( F \) איננה קבוצה. ואם \( A \) היא כן קבוצה, אני יכול לחשוב על הקבוצה \( F\left(A\right)=\left\{ F\left(a\right)\ |\ a\in A\right\} \), אבל “לחשוב על הקבוצה” לא מוכיח שהיא קיימת; בשביל זה אני צריך את אקסיומת ההחלפה.

פורמלית, אקסיומת ההחלפה היא לא אקסיומה בודדת, כלומר פסוק אחד ויחיד; יש לנו אקסיומת החלפה לכל נוסחה \( \varphi\left(x,y,a_{1},\ldots,a_{n}\right) \) אפשרית (לכן לפעמים מדברים על סכמת אקסיומת ההחלפה - מין תבנית כזו שיוצקים לתוכה את ה-\( \varphi \) ומקבלים אקסיומה), ועבור \( \varphi \) הזה אקסיומת ההחלפה היא

\( \forall x\forall y\forall z\left(\varphi\left(x,y,a_{1},\ldots,a_{n}\right)\wedge\varphi\left(x,z,a_{1},\ldots,a_{n}\right)\to y=z\right)\to \)

\( \to\forall A\exists B\forall y\left(y\in B\leftrightarrow\left(\exists x\in A\right)\varphi\left(x,y,a_{1},\ldots,a_{n}\right)\right) \)

החצי הראשון של האקסיומה אומר “אם \( \varphi \) מתארת פונקציה” והחצי השני אומר “אז לכל קבוצה \( A \) שעליה מפעילים את הפונקציה, קיימת קבוצה \( B \) שהיא התמונה של \( A \)”.

עכשיו אפשר סוף סוף לעשות עם זה משהו: אינדוקציה ורקורסיה על-סופיות. אבל מה זה אומר בכלל?

אינדוקציה על-סופית

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

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

בואו ניזכר איך אינדוקציה רגילה עובדת: יש לנו טענה \( P \) שיכולה להיות נכונה או שגויה עבור מספרים טבעיים שונים ומשונים. אנחנו כותבים \( P\left(n\right) \) כדי לומר “הטענה \( P \) מתקיימת עבור המספר הטבעי \( n \)”. הוכחה באינדוקציה פירושה להוכיח ש-\( P \) מתקיימת לכל הטבעיים, וזאת על ידי הוכחה של שתי טענות:

1. \( P\left(0\right) \) (הטענה מתקיימת עבור המספר הטבעי 0)
2. \( P\left(n\right)\to P\left(n+1\right) \) (אם הטענה מתקיימת עבור המספר הטבעי \( n \) אז היא מתקיימת עבור המספר הטבעי \( n+1 \)).

שני אלו ביחד, כאמור, מוכיחים שהטענה מתקיימת לכל הטבעיים, כלומר \( \forall nP\left(n\right) \) כשהכמת \( \forall \) (“לכל”) רץ על כל הטבעיים.

לפעמים אוהבים קצת לחסוך בכתיבה ולנסח אינדוקציה מתמטית בצורה הבאה:

\( \forall n\left(\forall k<n\left(P\left(k\right)\right)\to P\left(n\right)\right)\to\forall nP\left(n\right) \)

הזוועה הזו אומרת “אם לכל \( n \) טבעי זה נכון שאם לכל \( k<n \) מתקיים \( P\left(k\right) \) נובע מכך ש-\( P\left(n\right) \), אז \( P \) נכון לכל הטבעיים”. הניסוח הזה נקרא אינדוקציה שלמה והוא שקול לאינדוקציה “רגילה” אבל לפעמים יותר נוח, כי כדי להוכיח ש-\( P\left(n\right) \) מתקיים אפשר להשתמש ישירות בכך ש-\( P\left(k\right) \) מתקיים לכל \( k<n \) ולא רק למספר שבא מייד לפני \( n \). לפעמים הניסוח הזה לא חוסך הרבה; עדיין צריך להוכיח בנפרד את המקרה עבור 0, וכשמוכיחים לאיבר כללי מספיק להסתמך על זה שהטענה מתקיימת לזה שלפניו.

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

\( \forall\alpha\left(\forall\beta<\alpha\left(P\left(\beta\right)\right)\to P\left(\alpha\right)\right)\to\forall\alpha P\left(\alpha\right) \)

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

איך מוכיחים שאינדוקציה כזו באמת עובדת? ובכן, נניח ש-\( P \) מקיימת את התכונה שתיארתי: לכל \( \alpha \), אם \( P\left(\beta\right) \) לכל \( \beta<\alpha \) נובע מכך ש-\( P\left(\alpha\right) \), ועכשיו בואו נניח ש-\( P \) לא מתקיימת לכל הסודרים, אז קיים סודר מינימלי \( \alpha \) שעבורו היא לא מתקיימת, אבל המינימליות שלו פירושה שלכל \( \beta<\alpha \) כן מתקיים \( P\left(\beta\right) \), ומכאן שגם \( P\left(\alpha\right) \) עצמו מתקיים.

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

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

אז אני מגדיר סודר גבולי בתור סודר שהוא לא עוקב מיידי של אף סודר אחר, כלומר הוא לא מהצורה \( \alpha+1 \) עבור אף סודר (כזכור, \( \alpha+1\triangleq\alpha\cup\left\{ \alpha\right\} \)). הסודר הגבולי הראשון הוא 0, והשני הוא \( \omega \) וכן הלאה.

עכשיו אפשר לנסח אינדוקציה על-סופית בצורה יותר “קלאסית”. נניח שיש לנו טענה \( P \) על סודרים שמקיימת

1. \( P\left(0\right) \)
2. אם \( P\left(\alpha\right) \) אז \( P\left(\alpha+1\right) \)
3. אם \( \alpha\ne0 \) הוא סודר גבולי ולכל \( \beta<\alpha \) מתקיים \( P\left(\beta\right) \), אז \( P\left(\alpha\right) \)

אז אפשר להסיק ש-\( P \) מתקיימת לכל \( \alpha \).

עכשיו אפשר לעבור לדבר על רקורסיה, סוף סוף.

רקורסיה על-סופית

כמו עם אינדוקציה, גם כאן כדאי להתחיל עם דוגמא מעולם המספרים הטבעיים. איזו דוגמא מפורסמת יש למשהו שמוגדר ברקורסיה? זה קל: סדרת פיבונאצ'י היא ללא ספק הסדרה הרקורסיבית המפורסמת בעולם. בואו נזכיר מהי: זו סדרה \( F_{0},F_{1},F_{2},\ldots \) שמוגדרת על ידי הכללים:

• \( F_{0}=0 \)
• \( F_{1}=1 \)
• \( F_{n}=F_{n-1}+F_{n-2} \) לכל \( n>1 \)

הכללים הללו בעצם נחלקים לשני סוגים: יש לנו תנאי התחלה, שהם ערכים מפורשים של \( F \) עבור איברים ספציפיים, במקרה שלנו \( F_{0},F_{1} \), ויש לנו כלל רקורסיבי שמאפשר לקבל את \( F_{n} \) מתוך ערכים קודמים בסדרה. אנחנו רוצים להכליל את הרעיון הזה גם לסודרים, אבל בסודרים הסיטואציה קצת יותר מסובכת בגלל שיש לנו סודרים גבוליים שלא נוכל לכתוב \( \alpha-1 \) וכדומה עבורם. אז בואו נשתמש בניסוח קצת שונה, וקצת יותר מסורבל למראה במבט ראשון, גם עבור מספרים טבעיים.

הרעיון הוא כזה. מה זו בעצם “סדרה”? אנחנו חושבים עליה בתור פונקציה \( F:\mathbb{N}\to A \) עבור קבוצה \( A \) כלשהי; כלומר, דרך כלשהי להתאים לכל מספר טבעי איבר של \( A \). בסדרה רקורסיבית, כל איבר נבנה בצורה כלשהי מהאיברים הקודמים; פורמלית, יש פונקציה \( G \) שמקבלת סדרה \( G\left(a_{0},a_{1},\ldots,a_{n-1}\right) \) ומוציאה כפלט את \( a_{n} \), שהוא האיבר הבא שאמור להופיע בסדרה בתנאי שהאיברים הקודמים היו \( a_{0},\ldots,a_{n} \). עכשיו, כשאנחנו בונים את הסדרה \( F \), אנחנו עושים את זה על ידי הפעלות של \( G \) שמקבלת בכל פעם את האיברים של \( F \) שכבר נבנו; אפשר לסמן את זה \( F|_{n} \) - הצמצום של התחום של \( F \) מהקבוצה \( \mathbb{N} \) לקבוצה \( n=\left\{ 0,1,2,\ldots,n-1\right\} \), ואז מה שקורה הוא

\( F\left(n\right)=G\left(F|_{n}\right) \)

כלומר, הסדרה האינסופית \( F \) נבנית איכשהו מתוך פונקציה \( G \) שהקלטים שלה הן סדרות סופיות.

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

אם כן, הרעיון הוא שאם נתונה לי פונקציה \( G \) (וגם זו “פונקציה” במובן של מחלקה) שמוגדרת על מחלקת כל הקבוצות \( V \), אני יכול להשתמש בה כדי ליצור סדרה על-סופית אחת ויחידה \( F \), שמקיימת

\( F\left(\alpha\right)=G\left(F|_{\alpha}\right) \)

לכל הסודרים, כאשר \( F|_{\alpha} \) הוא הצמצום של \( F \) לאיברי הסודר \( \alpha \), דהיינו הסדרה \( \left\{ F_{\beta}\right\} _{\beta<\alpha} \) (הסדרה הזו היא כן קבוצה בזכות אקסיומת ההחלפה, שמחליפה את אברי הסודר \( \alpha \) בזוגות \( \left(\beta,F_{\beta}\right) \), ולכן קלט לגיטימי של \( G \)).

את הטענה שבאמת קיימת סדרה אחת ויחידה \( F \) כזו צריך להוכיח; אז בונים את \( F \) בתור נוסחה לוגית \( \varphi \) עם שני משתנים, \( \alpha,x \), כך ש-\( \varphi\left(\alpha,x\right) \) בודקת שקיימת סדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \) כך שהדברים הללו מתקיימים

1. לכל \( \beta<\alpha \) מתקיים \( a_{\beta}=G\left(\left\{ a_{\gamma}\right\} _{\gamma<\beta}\right) \)
2. \( x=G\left(\left\{ a_{\beta}\right\} _{\beta<\alpha}\right) \)

כדי להראות שזה עובד, משתמשים באינדוקציה על-סופית. ראשית, אנחנו רוצים להראות ש-\( F \) היא באמת פונקציה, כלומר שלכל \( \alpha \), אם קיימים \( x_{1},x_{2} \) כך ש-\( \varphi\left(\alpha,x_{1}\right) \) וגם \( \varphi\left(\alpha,x_{2}\right) \) שניהם T אז \( x_{1}=x_{2} \). מה אנחנו יודעים על \( x_{1},x_{2} \)? אנחנו יודעים שעבור \( x_{1} \) קיימת סדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \) שמקיימת את תנאי 1, ובנוסף \( x_{1}=G\left(\left\{ a_{\beta}\right\} _{\beta<\alpha}\right) \); ואנחנו יודעים שעבור \( x_{2} \) קיימת סדרה \( \left\{ b_{\beta}\right\} _{\beta<\alpha} \) שמקיימת את תנאי 1 ובנוסף \( x_{2}=G\left(\left\{ a_{\beta}\right\} _{\beta<\alpha}\right) \). אז מכיוון שאנחנו יודעים ש-\( G \) פונקציה, אם נראה ש-\( \left\{ a_{\beta}\right\} _{\beta<\alpha}=\left\{ b_{\beta}\right\} _{\beta<\alpha} \), ינבע מכך \( x_{1}=x_{2} \). ואיך נראה ששתי הסדרות הללו שוות? בעזרת תנאי 1, ובעזרת אינדוקציה.

אנחנו משתמשים באינדוקציה על \( \beta \) ומראים ש-\( a_{\beta}=b_{\beta} \) לכל \( \beta<\alpha \): הבסיס הוא \( \beta=0 \) ועבורו \( a_{0}=G\left(\emptyset\right)=b_{0} \) (כי במקרה זה לא קיים \( \gamma<\beta \) ולכן הסדרה של תנאי 1 ריקה). לכל סודר אחר, גבולי או עוקב, אנחנו מניחים שלכל \( \gamma<\beta \) כבר מתקיים \( a_{\gamma}=b_{\gamma} \), ומכאן שהסדרות \( \left\{ a_{\gamma}\right\} _{\gamma<\beta},\left\{ b_{\gamma}\right\} _{\gamma<\beta} \) שוות, ולכן

\( a_{\beta}=G\left(\left\{ a_{\gamma}\right\} _{\gamma<\beta}\right)=G\left(\left\{ b_{\gamma}\right\} _{\gamma<\beta}\right)=b_{\beta} \)

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

יפה, אז מה שהשגנו עד כה הוא להראות ש-\( F \) היא באמת פונקציה. אבל עדיין צריך להראות ש-\( F \) מוגדרת לכל סודר \( \alpha \), כלומר שתמיד קיים \( x \) כך ש-\( \varphi\left(\alpha,x\right) \) היא בעלת ערך T; זה לא מתחייב ממה שראינו עד כה. גם את זה נוכיח, כמה מפתיע, באינדוקציה על \( \alpha \).

עבור \( \alpha=0 \), בוודאי ש-\( x=G\left(\emptyset\right) \) ישיג את המטרה ש-\( \varphi\left(0,x\right) \) תקבל T; הסדרה של ה”קיימת סדרה” במקרה הזה היא בהכרח ריקה (כי האינדקסים שלה הם \( \beta<0 \) ואין כאלו) ולכן תנאי 1 מתקיים באופן ריק ותנאי 2 הוא בדיוק \( x=G\left(\emptyset\right) \). אז זה הבסיס.

עבור \( \alpha+1 \), אנו מניחים שהטענה נכונה עבור \( \alpha \), כלומר קיים איבר שאסמן \( a_{\alpha} \) וקיימת סדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \) שמקיימת את תנאי 1 ובנוסף \( a_{\alpha}=G\left(\left\{ a_{\beta}\right\} _{\beta<\alpha}\right) \). נרחיב את הסדרה הזו לסדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha+1} \) על ידי הוספת \( a_{\alpha} \) בתור האיבר האחרון שלה. נסמן \( x=G\left(\left\{ a_{\beta}\right\} _{\beta<\alpha+1}\right) \) (קיים \( x \) כזה כי \( G \) היא פונקציה) ועכשיו ברור ש-\( \varphi\left(\alpha+1,x\right) \) הוא T.

אם \( \alpha \) הוא סודר גבולי, אנחנו מניחים שהטענה נכונה לכל \( \beta<\alpha \). עכשיו מגיע החלק הטריקי והטכני ביותר בהוכחה: אני רוצה לבנות את הסדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \). אם אני אבנה אותה, אני אוכל להגדיר \( x=G\left(\left\{ a_{\beta}\right\} _{\beta<\alpha}\right) \) ואז \( \varphi\left(\alpha,x\right) \) יתקיים וכולנו נשמח. אבל בשביל זה צריך להראות שהסדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \) קיימת. לא קיימת במובן הנפנוף-ידיימי של מחלקות; קיימת בתור אובייקט מתמטי קונקרטי - קבוצה - ביקום שלנו.

אז ראשית כל, אינטואיציה. אם יש לנו \( \beta_{1}<\beta_{2}<\alpha \), אנחנו יודעים שהסדרה עד \( \beta_{1} \) היא תת-סדרה של הסדרה עד \( \beta_{2} \). פורמלית, מכיוון ש-\( \beta_{1} \) מקיימת את הנחת האינדוקציה קיימת עבורה סדרה, \( \left\{ a_{\gamma}\right\} _{\gamma\le\beta_{1}} \) שמקיימת את תכונות 1-2. בדומה עבור \( \beta_{2} \) קיימת סדרה \( \left\{ b_{\gamma}\right\} _{\gamma\le\beta_{2}} \) שכזו. אפשר להוכיח באינדוקציה, כמו שעשינו קודם, שעבור \( \gamma\le\beta_{1} \) מתקיים \( a_{\gamma}=b_{\gamma} \) - שתי הסדרות זהות עד שהסדרה הקצרה ביותר נגמרת. זה נכון לכל זוג \( \beta_{1}<\beta_{2}<\alpha \), ולכן אם נחשוב לרגע על שתי הסדרות הללו בתור קבוצות של זוגות סדורים:

\( \left\{ \left(0,a_{0}\right),\left(1,a_{1}\right),\ldots,\left(\beta_{1},a_{\beta_{1}}\right)\right\} \)

\( \left\{ \left(0,a_{0}\right),\left(1,a_{1}\right),\ldots,\left(\beta_{1},a_{\beta_{1}}\right),\ldots,\left(\beta_{2},a_{\beta_{2}}\right)\right\} \)

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

על פי אותו הגיון, אם תהיה לנו קבוצה שהאיברים שלה הן כל הסדרות שמתאימות לכל אחד מה-\( \beta<\alpha \) האפשריים, איחוד של כל אברי הקבוצה הזו יתן לנו בדיוק את הסדרה \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \) המבוקשת: לכל \( \beta<\alpha \) אכן יהיה בדיוק איבר אחד בסדרה, והסדרה תקיים את החוקיות של דרישה (1). רק צריך להראות שקיימת קבוצה שהאיברים שלה הן כל הסדרות. הקבוצה הזו מתקבלת מאקסיומת ההחלפה כשמפעילים אותה על \( \alpha \) ומחליפים כל \( \beta \) בסדרה \( \left\{ a_{\gamma}\right\} _{\gamma\le\beta_{1}} \) . השימוש הזה באקסיומת ההחלפה דורש בעצמו עבודה טכנית - להראות שיש פסוק שמקבל זוג של \( \beta \) וסדרה \( \left\{ a_{\gamma}\right\} _{\gamma\le\beta} \) ומוודא שהסדרה \( \left\{ a_{\gamma}\right\} _{\gamma\le\beta} \) מקיימת את תנאים 1-2 ושהיא כוללת את כל הסודרים עד וכולל \( \beta \), וש-\( \beta \) הוא בכלל סודר… הבנו את הרעיון, זה הזמן להתחיל לחפף.

לסיום, בואו נוכיח יחידות: נניח ש-\( F,F^{\prime} \) הן שתי פונקציות שמקיימות שתיהן \( F\left(\alpha\right)=G\left(F|_{\alpha}\right) \) ו-\( F^{\prime}\left(\alpha\right)=G\left(F^{\prime}|_{\alpha}\right) \) ונוכיח ש-\( F\left(\alpha\right)=F^{\prime}\left(\alpha\right) \) לכל סודר \( \alpha \) (כאן אנחנו נעזרים בכך שאנחנו כבר יודעים ש-\( F,F^{\prime} \) מוגדרות לכל סודר). איך? באינדוקציה, כמובן! ההוכחה טריוויאלית, כי \( F|_{\alpha}=F^{\prime}|_{\alpha} \) אם אנחנו מניחים את נכונות הטענה לכל \( \beta<\alpha \) (כי צמצמנו את שתי הפונקציות הללו אל תחום שבו הן שוות) ולכן \( F\left(\alpha\right)=G\left(F|_{\alpha}\right)=G\left(F^{\prime}|_{\alpha}\right)=F^{\prime}\left(\alpha\right) \), מה שמסיים את ההוכחה.

דוגמא מועילה במיוחד: ההיררכייה המצטברת

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

אם כן, הרעיון הוא שקיימת סדרה על-סופית \( V_{0},V_{1},V_{2},\ldots \) של קבוצות כך שלכל קבוצה קיימת \( V_{\alpha} \) בהיררכייה שהיא שייכת אליה. דרך אפשרית אחת להגדיר את ההיררכייה היא בתור \( V_{\alpha}=\mathcal{P}\left(\bigcup_{\beta<\alpha}V_{\beta}\right) \), מה שנותן

\( V_{0}=\mathcal{P}\left(\emptyset\right)=\left\{ \emptyset\right\} \)

\( V_{1}=\mathcal{P}\left(\left\{ \emptyset\right\} \right)=\left\{ \emptyset,\left\{ \emptyset\right\} \right\} \)

\( V_{2}=\mathcal{P}\left(\left\{ \emptyset,\left\{ \emptyset\right\} \right\} \right)=\left\{ \emptyset,\left\{ \emptyset\right\} ,\left\{ \left\{ \emptyset\right\} \right\} \left\{ \emptyset,\left\{ \emptyset\right\} \right\} \right\} \)

וכן הלאה וכן הלאה. אז הדרגה של \( \emptyset \) היא 0 ושל \( \left\{ \emptyset,\left\{ \emptyset\right\} \right\} \) היא 2 וכן הלאה.

למה כל קבוצה שייכת לדרגה כלשהי בהיררכייה? ובכן, זה לא לגמרי מובן מאליו - כדי להוכיח את זה אני אשתמש באחת מהאקסיומות של ZFC שאני לא בטוח אם הצגתי עד כה - אקסיומת היסוד. אדבר עליה בפירוט בהמשך; לעת עתה מה שצריך לדעת הוא שהיא באה למנוע סיטואציות הזויות כמו קבוצות \( A \) שמקיימות \( A\in A \), ופורמלית אני מגדיר אותה באופן הבא: לכל קבוצה לא ריקה \( A \), קיים ב-\( A \) איבר מינימלי ביחס ל-\( \in \) (כלומר קיים \( x\in A \) כך שלכל \( y\in A \) מתקיים \( y\notin x \)).

בואו ניקח קבוצה \( A \) כלשהי ונניח שלכל \( x\in A \), קיים סודר \( \alpha_{x} \) כך ש-\( x\in V_{\alpha_{x}} \). אז נגדיר סודר חדש, \( \overline{\alpha}=\bigcup\left\{ \alpha_{x}+1\ |\ x\in A\right\} \). קיבלנו סודר כך ש-\( \alpha_{x}<\overline{\alpha} \) לכל \( x\in A \), אז \( \bigcup_{\beta<\overline{\alpha}}V_{\beta} \) כוללת את כל ה-\( x\in A \)-ים, ולכן \( A\in V_{\overline{\alpha}}=\mathcal{P}\left(\bigcup_{\beta<\overline{\alpha}}V_{\beta}\right) \). אז זה מסביר למה, באופן לא מפתיע, אם כל האיברים של קבוצה שייכים להיררכייה אז היא עצמה שייכת להיררכייה; אבל למה אפשר תמיד להניח שכל האיברים של קבוצה יהיו שייכים להיררכייה?

בבירור מסתתר כאן טיעון כלשהו שמדבר לא רק על קבוצה והאיברים שלה אלא גם על האיברים של האיברים שלה והאיברים-של-האיברים-של-האיברים שלה וכן הלאה. צריך לפרמל את זה איכשהו, אז אפשר לדבר על הסגור הטרנזיטיבי של קבוצה שהוא מה שמכיל את כל הדברים הללו. בשביל הגדרה פורמלית, נגדיר \( A^{\prime}=\bigcup_{x\in A}x \): זו הקבוצה שאבריה הם כל האיברים-של-איברים של \( A \). עכשיו אפשר להגדיר סגור טרנזיטיבי על ידי \( A^{*}=A\cup A^{\prime}\cup A^{\prime\prime}\cup\ldots \). נשאר להוכיח את הטענה שבהינתן \( A \), לכל \( x\in A^{*} \) מתקיים ש-\( x \) שייך להיררכייה המצטברת. זו טענה חזקה יותר מהטענה הקודמת, כי \( A\subseteq A^{*} \) ולכן אם הטענה נכונה עבור \( A^{*} \) היא בוודאי נכונה עבור \( A \); אבל היתרון בכך שהיא חזקה יותר הוא שעכשיו יש לנו גם יותר לעבוד איתו ב”צעד האינדוקציה” (במרכאות, כי אנחנו לא באמת מבצעים פה אינדוקציה).

בואו נניח עכשיו בשלילה שב-\( A^{*} \) יש איברים שאינם שייכים להיררכייה המצטברת. אז בזכות אקסיומת היסוד, אני יכול להניח שיש ביניהם איבר מינימלי \( x \). אם כל האיברים של \( x \) כן שייכים להיררכייה המצטברת, כבר ראינו שמכך ינבע שגם \( x \) שייך. אם כן, יהי \( y\in x \) כלשהו. אם \( x\in A^{\left(n\right)} \) אז \( y\in A^{\left(n+1\right)} \), ולכן \( y\in A^{*} \) בעצמו. המינימליות של \( x \) והעובדה ש-\( y\in x \) אומרת לנו שלא ייתכן שגם \( y \) לא שייך להיררכייה המצטברת, ולכן כל האיברים של \( x \) שייכים להיררכייה המצטברת, ולכן גם \( x \) עצמו, וסיימנו.

מכאן ואילך נוכל להשתמש בחופשיות בהיררכייה המצטברת בהוכחות. פורמלית, לכל קבוצה \( A \) נתאים סודר \( \text{rank}\left(A\right) \) כך ש-\( \text{rank}\left(A\right)=\min\left\{ \alpha\ |\ A\in V_{\alpha}\right\} \) ונקרא לזה הדרגה של \( A \), ואז האינדוקציה/רקורסיה שלנו תהיה על הדרגה. אנחנו רוצים להיות מסוגלים להניח שלכל \( A \), הדרגה של כל האיברים של \( A \) קטנה מהדרגה של \( A \) עצמה (ולכן אפשר להניח באינדוקציה שהטענה נכונה עבורם/להניח שערכם כבר הוגדר ברקורסיה). למה זה נכון? כי אם \( A\in V_{\alpha} \), כש-\( \alpha \) הוא המינימלי בעל תכונה זו, אז \( A\in\mathcal{P}\left(\bigcup_{\beta<\alpha}V_{\beta}\right) \), מה שאומר שכל אברי \( A \) שייכים ל-\( V_{\beta} \) עם \( \beta<\alpha \).

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