בעקבות השערת הרצף, חלק ג': רלטיביזציה ועקרון הרפלקציה

מבוא

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

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

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

בשפה של תורת החבורות סימן היחס היחיד הוא \( = \), אבל יש לנו סימן פונקציה, \( f \) (“כפל”) וסימן קבוע \( e \) (“יחידה”) והאקסיומות הן

1. \( \forall a\forall b\forall c\left(f\left(a,f\left(b,c\right)\right)=f\left(f\left(a,b\right),c\right)\right) \)
2. \( \forall a\left(f\left(a,e\right)=a\wedge f\left(e,a\right)=a\right) \)
3. \( \forall a\exists b\left(f\left(a,b\right)=e\right) \)

בתור קיצור, במקום לכתוב \( f\left(a,b\right) \) אנחנו כותבים \( a\cdot b \) או אפילו סתם \( ab \), מה שמפשט את האקסיומות שהופכות להיות

1. לכל \( a,b,c \): \( \left(ab\right)c=a\left(bc\right) \) .
2. לכל \( a \): \( a\cdot e=e\cdot a=a \).
3. לכל \( a \) קיים \( b \) כך ש-\( ab=e \).

מה שעושים עכשיו הוא להתחיל להסתכל על מבנים: מבנה הוא קבוצה \( \mathcal{M} \) של איברים, ובנוסף “פרשנות” שמתאימה לכל סימן יחס בשפה יחס מעל \( \mathcal{M} \) (חוץ מאשר סימן היחס \( = \) שתמיד מייצג שוויון), לכל סימן פונקציה מתאים פונקציה מעל \( \mathcal{M} \) ולכל סימן קבוע מתאים קבוע מתוך \( \mathcal{M} \). למשל, עבור תורת החבורות, אפשר לקחת \( \mathcal{M}=\mathbb{Z} \) ולהתאים ל-\( f \) את הפונקציה \( + \) (חיבור רגיל) ול-\( e \) להתאים את האיבר \( 0 \).

אם נעשה את זה, ונסתכל על שלוש האקסיומות שכתבתי קודם, נראה שהן כולן מתקיימות (כלומר ערך האמת שלהן הוא T) כאשר מפרשים את הסימנים באופן שתיארתי, והכמתים שבפסוקים רצים על האיברים של \( \mathcal{M} \) (כלומר, כשכתוב \( \forall a \) הכוונה היא “לכל \( a\in\mathbb{Z} \)”). במקרה כזה אומרים ש-\( \mathcal{M} \) הוא מודל של קבוצת האקסיומות.

עוד מודלים עבור אותן אקסיומות: \( \mathbb{R} \) עם פעולת החיבור הרגילה ו-\( e=0 \); \( \mathbb{Q}\backslash\left\{ 0\right\} \) עם פעולת הכפל הרגיל ו-\( e=1 \); מרחב המטריצות ההפיכות מסדר \( 2\times2 \) מעל הממשיים, \( Gl_{2}\left(\mathbb{R}\right) \) עם פעולת כפל המטריצות הרגילה ו-\( e=I \), וכן הלאה. אפשר כמובן גם להציע מבנים שלא יעברו את המחסום של האקסיומות: למשל \( \mathbb{N} \) עם פעולת החיבור הרגילה לא יקיים את האקסיומה השלישית; \( \mathbb{Z} \) עם פעולת החיבור הרגילה ו-\( e=1 \) לא יקיים את האקסיומה השניה; ו-\( \mathbb{Z} \) עם פעולת החיסור במקום חיבור לא יקיים את 1. בכל המקרים הללו יש לנו מבנה לגיטימי שפשוט אינו מודל של קבוצת האקסיומות.

עכשיו, הבה ונתבונן על הפסוק הבא:

• \( \forall a\forall b\left(f\left(a,b\right)=f\left(b,a\right)\right) \)

כלומר, לכל \( a,b \) מתקיים \( ab=ba \). זה פסוק שמתקיים על ידי \( \mathbb{Z} \) ופעולת החיבור הרגילה, אבל לא מתקיים על ידי \( Gl_{2}\left(\mathbb{R}\right) \). משני אלו אנו מקבלים שמערכת ההוכחה הרגילה שלנו לא יכולה להוכיח את הפסוק הזה מתוך האקסיומות. הסיבה לכך היא שמערכת ההוכחה הרגילה שלנו מקיימת משהו שנקרא משפט הנאותות; הוא אומר שאם קבוצת אקסיומות מוכיחה טענה כלשהי, אז נובע מכך שהיא גוררת אותה לוגית: כלומר, שכל מודל של האקסיומות הוא גם מודל של הטענה. גם את זה תיארתי פה כבר בעבר.

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

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

בואו נעבור לדבר מתמטיקה בצורה יותר קונקרטית.

רלטיביזציה ורפלקציה

הכלי הטכני הבסיסי שאנחנו מסתמכים עליו נקרא רלטיביזציה של נוסחאות. הרעיון הוא לקחת נוסחה כללית \( \phi \) בשפה של ZFC ולקחת משתנה \( M \) (משתנה שבא לתאר קבוצה) ולשנות את \( \phi \) כך שבכל פעם שבה מופיע כמת, הטווח של הכמת הזה יהיה רק אברי הקבוצה \( M \). בצורה הזו הנוסחה הכללית \( \phi \) הופכת לנוסחה \( \phi|_{M} \) שהיא יחסית ל-\( M \).

פורמלית:

• אם \( \phi=\forall x\varphi \) אז \( \phi|_{M}=\forall x\left(x\in M\to\varphi\right) \)
• אם \( \phi=\exists x\varphi \) אז \( \phi|_{M}=\exists x\left(x\in M\wedge\varphi\right) \)

כלומר, במקרה של \( \forall \) אנחנו מצמצמים את הדרישות שלנו מ-\( \varphi \): במקום ש-\( \varphi \) יתקיים לכל איבר, הוא צריך להתקיים רק לאיברים של \( M \). עבור \( \exists \) אנחנו מחמירים את הדרישות שלנו: במקום שהוא סתם יתקיים ל-\( x \) כלשהו, אנחנו מוסיפים את הדרישה ש-\( x\in M \).

בואו נראה דוגמא. אחת מהאקסיומות הפשוטות ביותר של ZFC היא אקסיומת הזיווג:

\( \phi=\forall x\forall y\exists A\left(x\in A\wedge y\in A\right) \)

ממנה נקבל את האקסיומה היחסית ל-\( M \):

\( \phi|_{M}=\forall x\left(x\in M\to\forall y\left(y\in M\to\exists A\left(A\in M\wedge x\in A\wedge y\in A\right)\right)\right) \)

עכשיו הטרמינולוגיה שדיברתי עליה קודם עושה קאמבק: אם \( \phi|_{M} \) מקבלת ערך T אז אומרים על זה ש-\( M \) הוא “מודל” של \( \phi \), אבל שימו לב שזו סיטואציה שונה ממה שדיברנו עליה קודם: קודם היה לנו פסוק \( \phi \) ואז הבאנו ממקור חיצוני מבנה \( \mathcal{M} \) שיהיה מודל שלו; הפעם \( M \) הוא משתנה ולכן הערך שלו נקבע כשאנחנו מסתכלים על השמה כלשהי למשתנים של הפסוק. זה לא משהו שבא “מבחוץ”. אבל אפשר לנקוט בגישה שמשלבת את הטוב שבשני העולמות: אם יש לנו קבוצה קונקרטית \( M \) ופסוק \( \phi \) נהוג לסמן \( M\models\phi \) אם \( M \) היא מודל של \( \phi \) (כלומר, הפסוק \( \phi \) מסתפק כאשר הכמתים שמופיעים בו רצים על אברי \( M \)); זה אותו דבר כמו לומר שהנוסחה \( \phi|_{M} \) מסתפקת כאשר אנו מציבים את הקבוצה \( M \) בתוך המשתנה \( M \) שמופיע ב-\( \phi|_{M} \). יש כאן כפל משמעות מזעזע בסימון: \( M \) מייצג גם קבוצה, וגם את “המשתנה שבו מציבים את הקבוצה”. אני לא חושש שזה יגרום לבלבול, כי אפשר להבין מהי \( M \) מתוך ההקשר: האם היא קבוצה, או סימבול שמופיע בתוך נוסחה.

עכשיו יש לנו מספיק טרמינולוגיה כדי שאוכל להציג את “מטרת העל” שלנו בפוסט הזה: אני רוצה שנוכיח שלכל פסוק \( \phi \) קיימת קבוצה \( M \) שהיא פשוטה במיוחד: היא בת מניה והיא טרנזיטיבית, כך שמתקיים \( \phi\leftrightarrow\phi|_{M} \). כאן “מתקיים” פירושו שהנוסחה \( \phi\leftrightarrow\phi|_{M} \), כאשר מציבים את \( M \) בתוך המשתנה \( M \) שבה, היא בעלת ערך T (המשתנה החופשי היחיד בה היה \( M \) ולכן מרגע שהצבנו ערך בתוכו קיבלנו פסוק שערך האמת שלו נקבע באופן יחיד). ה-\( M \) הזו היא מה שכיניתי קודם “יקום זעיר”. שימו לב שזה יקום זעיר קונקרטי שמתאים לפסוק אחד ויחיד \( \phi \); זה לא יקום שמתאים בו זמנית לכל ZFC (וכפי שנראה בהמשך, גם לא נבנה יקום שמתאים בו זמנית לכל ZFC, אבל לא נצטרך).

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

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

רלטיביזציה ואיזומורפיזם

בואו ניקח נוסחה \( \phi\left(x_{1},\ldots,x_{n}\right) \) כלשהי. ההבדל בין “נוסחה כלשהי” ובין “פסוק” הוא שפסוק הוא מקרה פרטי של נוסחה שאין לה משתנים חופשיים; כשאני כותב את ה-\( x_{i} \)-ים הללו בסוגריים אני מתכוון שהמשתנים החופשיים של \( \phi \) נמנים על \( x_{1},\ldots,x_{n} \) (לאו דווקא שכל אחד מה-\( x_{i} \)-ים הזה הוא משתנה חופשי של \( \phi \), רק שכל המשתנים החופשיים של \( \phi \) נמנים איתם).

המטרה שלי היא להבין מתי הרלטיביזציה של \( \phi \) לשתי קבוצות שונות \( M,N \) היא “אותו דבר”, כחלק מהמאמץ שלי למצוא קבוצה “קנונית נחמדה” (בת מניה וטרנזיטיבית) שאליה נעשה רלטיביזציה. הכלי הסטנדרטי בלוגיקה בהקשר הזה הוא מה שנקרא איזומורפיזם של מבנים, שזו פונקציה \( f:M\to N \) שהיא חח”ע ועל ומשמרת את פרשנות יחסי הסדר/קבועים/פונקציות. בשפה שלנו יש רק את יחס הסדר \( \in \) אז הדרישה מ-\( f \), בנוסף לזה שהיא חח”ע ועל, היא רק שיתקיים \( x\in y\iff f\left(x\right)\in f\left(y\right) \).

בהינתן \( f \) כזו, הטענה שאנחנו רוצים להוכיח היא זו: לכל \( a_{1},\ldots,a_{n}\in M \), מתקיים

\( \phi|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\phi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

במילים (שיוצאות הרבה יותר מסורבלות): אם נסתכל על הנוסחה שמתקבלת מכך שלוקחים את \( \phi \), יוצרים שני עותקים שלו, מבצעים רלטיביזציה לשני העותקים, פעם עם המשתנה \( M \) ופעם עם המשתנה \( N \), מציבים את הקבוצה \( M \) במשתנה הראשון ואת הקבוצה \( N \) במשתנה השני, ואז ניגשים אל המשתנים החופשיים של העותק הראשון ומציבים בהם \( a_{1},\ldots,a_{n} \) ובמשתנים החופשיים של העותק השני מציבים \( f\left(a_{1}\right),\ldots,f\left(a_{n}\right) \) ובסוף לוקחים את שני העותקים ומחברים אותם עם הקשר \( \leftrightarrow \) - אחרי כל המהומה הזו מתקבלת נוסחה אחת עם הצבה עבורה, וערך האמת של הנוסחה בהצבה הזו הוא T.

כדי להוכיח טענות כאלו משתמשים בכלי ההוכחה האהוב עלינו מלוגיקה מתמטית: אינדוקציה על המבנה של הנוסחה. כזכור, נוסחה היא או אטומית מהצורה \( x_{1}=x_{2} \) או \( x_{1}\in x_{2} \), או שהיא מהצורה \( \neg\psi \), או \( \psi_{1}\to\psi_{2} \), או \( \forall\psi_{1} \), או… או שום דבר נוסף, בעצם; אפשר להראות שכל קשר וכל כמת אחר ניתן להחלפה באלו הקיימים לקבל נוסחה שקולה, ומספיק להוכיח את הטענה עבור הנוסחה השקולה הזו (אבל איך אומרים? זה תרגיל טוב להוכיח גם עבור הקשרים והכמתים האחרים).

אם \( \phi \) היא מהצורה \( x_{1}=x_{2} \) הטענה מאוד פשוטה: רלטיביזציה במקרה הזה לא עושה כלום (כי אין כמתים) ולכן אנחנו רוצים להוכיח שלכל \( a_{1},a_{2}\in M \) מתקיים \( \left(a_{1}=a_{2}\right)\iff\left(f\left(a_{1}\right)=f\left(a_{2}\right)\right) \) , וזה נובע מיידית מכך ש-\( f \) פונקציה חח”ע.

אם \( \phi \) היא מהצורה \( x_{1}\in x_{2} \) אז באופן דומה צריך לראות ש-\( \left(a_{1}\in a_{2}\right)\iff\left(f\left(a_{1}\right)\in f\left(a_{2}\right)\right) \) וזה נובע ישירות מהדרישה ש-\( f \) היא איזומורפיזם (מכאן הדרישה הזו הגיעה, כמובן). אז לטפל במקרי הבסיס סיימנו.

עכשיו, נניח ש-\( \phi=\left(\neg\psi\right) \), אז

\( \phi|_{M}=\left(\neg\psi\right)|_{M}=\neg\left(\psi|_{M}\right) \)

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

\( \psi|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\psi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

בגלל השקילות בין שני האגפים (שמשמעותה שבהצבה שעליה אנו מסתכלים שניהם מקבלים את אותו ערך אמת), אם נוסיף \( \neg \) בהתחלה של כל אחד מהם נהפוך את ערך האמת שהוא מקבל, אבל שניהם עדיין יקבלו את אותו ערך אמת ולכן הנוסחה כולה עדיין תהיה T.

עבור \( \phi=\left(\psi_{1}\to\psi_{2}\right) \) קורה משהו דומה - רלטיביזציה משפיעה רק על תתי-הפסוקים, כלומר

\( \phi|_{M}=\left(\psi_{1}\to\psi_{2}\right)|_{M}=\left(\psi_{1}|_{M}\to\psi_{2}|_{M}\right) \)

נאחד את קבוצות המשתנים החופשיים שמופיעים ב-\( \psi_{1} \) וב-\( \psi_{2} \) ונסמן את קבוצת המשתנים שקיבלנו ב-\( x_{1},\ldots,x_{n} \) (הנה מקום שבו אנחנו משתמשים בזה שהמשתנים שנכתבים בסוגריים עשויים להיות יותר מאשר המשתנים החופשיים של הנוסחה), ניקח ערכים \( a_{1},\ldots,a_{n}\in M \) ונקבל מהנחת האינדוקציה

\( \psi_{1}|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\psi_{1}|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

\( \psi_{2}|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\psi_{2}|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

משני אלו אנחנו רוצים להסיק ש-

\( \left(\psi_{1}\to\psi_{2}\right)|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\left(\psi_{1}\to\psi_{2}\right)|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

כדי להראות את זה צריך להראות ששני האגפים מקבלים את אותו ערך אמת. הדרך היחידה שבה אגף שמאל יכול לקבל F היא אם \( \psi_{1}|_{M}\left(a_{1},\ldots,a_{n}\right) \) מקבל T וגם \( \psi_{2}|_{M}\left(a_{1},\ldots,a_{n}\right) \) מקבל F, והשקילויות שקיבלנו מהנחת האינדוקציה מראות שבמקרה הזה \( \psi_{1}|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \) מקבל T ו-\( \psi_{2}|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \) מקבל F ולכן גם אגף ימין מקבל F בסך הכל והשקילות נשמרת; אותו הדבר אפשר לעשות גם בכיוון השני, אם מניחים שאגף ימין מקבל F.

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

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

\( \phi|_{M}=\forall x_{i}\left(x_{i}\in M\to\psi\left(x_{1},\ldots,x_{n}\right)\right) \)

עכשיו, מה הנחת האינדוקציה נותנת לנו כאן? אנחנו יודעים שלכל \( a_{1},\ldots,a_{n}\in M \) מתקיים

\( \psi|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\psi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

ומה שאנחנו צריכים לעשות הוא להראות שלכל \( a_{1},\ldots,a_{i-1},a_{i+1},\ldots,a_{n}\in M \) מתקיים

\( \phi|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\phi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

נניח שתחת ההשמה שמציבה את הערכים הללו במשתנים (ואת \( M,N \) במשתנים המתאימים שלהם) אגף שמאל מקבל T. אנחנו צריכים להוכיח שגם אגף ימין מקבל T. בשלב הזה אגף ימין הוא

\( \phi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

או, אם נפתח את ההגדרה של \( \phi|_{N} \), אגף ימין הוא

\( \forall x_{i}\left(x_{i}\in N\to\psi|_{N}\left(f\left(a_{1}\right),\ldots,x_{i},\ldots,f\left(a_{1}\right)\right)\right) \)

זה אומר שכדי להראות שהאגף הזה הוא T, צריך להראות שלכל הצבה של ערך \( b \) ב-\( x_{i} \), אם \( b\in N \) אז \( \psi|_{N}\left(f\left(a_{1}\right),\ldots,b,\ldots,f\left(a_{1}\right)\right)=\text{T} \).

האתגר התקבל! בואו ניקח ערך \( b \) כזה ונניח ש-\( b\in N \) אחרת אין לנו מה לעשות. עכשיו אנחנו סוף כל סוף משתמשים בתכונה של \( f \) שטרם השתמשנו בה: \( f:M\to N \) היא פונקציה על ולכן קיים \( a\in M \) כך ש-\( f\left(a\right)=b \). מכאן שמה שצריך להראות הוא

\( \psi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a\right),\ldots,f\left(a_{1}\right)\right)=\text{T} \)

עכשיו, בואו ניזכר מה הנחת האינדוקציה נתנה לנו; היא נתנה את

\( \psi|_{M}\left(a_{1},\ldots,a_{n}\right)\leftrightarrow\psi|_{N}\left(f\left(a_{1}\right),\ldots,f\left(a_{n}\right)\right) \)

אז מספיק אם נוכיח שעבור \( a_{1},\ldots,a_{i-1},a,a_{i+1},\ldots,a_{n} \) מתקיים

\( \psi|_{M}\left(a_{1},\ldots,a_{n}\right)=\text{T} \)

לצורך כך, בואו ניזכר בהנחה שהתחלנו איתה את השלב הזה בהוכחה, איפה שכתבתי “אגף שמאל מקבל T”. אותו אגף שמאל היה

\( \phi|_{M}\left(a_{1},\ldots,a_{n}\right) \)

וכשפותחים את ההגדרה, מקבלים

\( \forall x_{i}\left(x_{i}\in M\to\psi|_{M}\left(a_{1},\ldots,x_{i},\ldots,a_{n}\right)\right) \)

ולכן, אם הנוסחה הזו מקבלת ערך T תחת ההשמה הנתונה, היא בפרט מקבלת ערך T אם מציבים ב-\( x_{i} \) את \( a \). מכיוון ש-\( a\in M \) אז נובע מכך

\( \psi|_{M}\left(a_{1},\ldots,a,\ldots,a_{n}\right)=\text{T} \)

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

שובן של הקבוצות הטרנזיטיביות

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

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

\( \forall A\forall B\left(\forall x\left(x\in A\leftrightarrow x\in B\right)\to A=B\right) \)

אז הרלטיביזציה של זה אומרת “לכל \( A,B\in M \) , אם \( A\cap M=B\cap M \) אז \( A=B \)”: אין שתי קבוצות שונות ב-\( M \) ש”החלק שלהן שמוכל ב-\( M \)” נראה אותו דבר. או בניסוח אחר: כדי להראות ש-\( A\ne B \) צריך להציג איבר ששייך לאחת הקבוצות אבל לא לשנייה; מובטח לנו שאחד מהאיברים הללו יהיה שייך ל-\( M \).

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

הוכחת היחידות היא קלה יותר, אז נתחיל ממנה. נניח שקיימות \( N_{1}\ne N_{2} \) כך ש-\( N_{1}\cong M\cong N_{2} \). מטרנזיטיביות האיזומורפיזם נקבל \( N_{1}\cong N_{2} \); נסמן את האיזומורפיזם הזה ב-\( g \). מכיוון ש-\( N_{1}\ne N_{2} \) אז \( g \) הוא לא הזהות, כלומר קיים \( a\in N_{1} \) כך ש-\( g\left(a\right)\ne a \), ובעזרת אקסיומת היסוד אפשר לבחור את \( a \) להיות האיבר המינימלי של \( N_{1} \) ביחס ל-\( \in \) שמקיים את התכונה הזו.

עכשיו משתמשים בטריק די סטנדרטי עבור קבוצות טרנזיטיביות: מכיוון ש-\( N_{1},N_{2} \) טרנזיטיביות, אז \( a\subseteq N_{1} \) ו-\( g\left(a\right)\subseteq N_{2} \). בפרט, לכל \( x\in a \) מתקיים \( a\in N_{1} \) ולכן \( g \) מוגדר על \( x \), ומכיוון ש-\( g \) היא איזומורפיזם אז \( x\in a\iff g\left(x\right)\in g\left(a\right) \), כלומר \( g \) היא פונקציה חח”ע ועל בין הקבוצות \( a,g\left(a\right) \). עכשיו, בגלל המינימליות של \( a \), אנחנו יודעים שלכל \( x\in a \) מתקיים \( g\left(x\right)=x \), ולכן מסיקים ש-\( a=g\left(a\right) \), וזו סתירה לכך שבחרנו את \( a \) להיות איבר שמקיים \( g\left(a\right)\ne a \), מה שמסיים את החלק הזה של ההוכחה.

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

ראשית, בואו נסתכל על אותן תת-קבוצות של \( M \) ש”ביחס אל \( M \) נראות טרנזיטיביות”. אם טרנזיטיביות של \( A\in M \) פירושה שלכל \( a\in A \) מתקיים \( a\subseteq A \), כאן אנו רוצים שיתקיים \( a\cap M\subseteq A \). מבין הקבוצות ה”נראות טרנזיטיביות” הללו אנחנו מתעניינים רק באלו שאיזומורפיות לקבוצה טרנזיטיבית - אני אקרא לקבוצות הללו “קבוצות נחמדות”. אני כמובן רוצה להראות ש-\( M \) עצמה היא נחמדה; הטריק יהיה להסתכל על איחוד כל הקבוצות הנחמדות ב-\( M \), שאסמן \( Z \), ולהוכיח שני דברים:

• \( Z \) היא בעצמה קבוצה נחמדה.
• \( Z=M \).

דווקא את החלק השני קל להראות. אם \( Z \) נחמדה, אז יש איזומורפיזם \( f:Z\to N \) עבור קבוצה טרנזיטיבית \( N \) כלשהי. עכשיו, אם \( M\ne Z \), ומכיוון שמלכתחילה \( Z \) היא איחוד של תת-קבוצות של \( M \) ולכן \( Z\subseteq M \), אנו מקבלים ש- \( M\backslash Z\ne\emptyset \); ניקח \( a\in M\backslash Z \) מינימלי (ביחס ל-\( \in \)) שמקיים זאת (אפשר, על פי אקסיומת היסוד).

עכשיו נרחיב את האיזומורפיזם \( f \) על ידי ההגדרה \( f\left(a\right)=\left\{ f\left(x\right)\ |\ x\in a\right\} \); כלומר, הוספנו את \( a \) אל \( Z \), והוספנו את \( \left\{ f\left(x\right)\ |\ x\in a\right\} \) אל \( N \). האיבר החדש הזה ב-\( N \) כולל רק איברים של \( N \) ולכן מוכל ב-\( N \) כך שהוספתו לא פוגמת בטרנזיטיביות; את \( f \) הרחבנו על ידי איבר חדש שעובר לאיבר חדש, כך שהפונקציה המתקבלת היא עדיין חח”ע ועל; וכדי להראות שעדיין יש שימור סדר ראשית נשים לב לכך שלא ייתכן ש-\( a\in x \) עבור \( x\in Z \), כי מכיוון ש-\( Z \) היא קבוצה נחמדה אז \( a\in x \) היה גורר \( a\in Z \). לכן הדבר היחיד שאפשרי הוא \( x\in a \) עבור \( x\in Z \), ובסיטואציה כזו \( f\left(x\right)\in f\left(a\right) \) על פי ההגדרה, כך שגם יחס הסדר נשמר.

המסקנה היא שההרחבה הזו של \( Z \) היא עדיין קבוצה נחמדה בעצמה, אבל אם \( Z \) היא איחוד כל הקבוצות הנחמדות, היא לא יכולה להיות מוכלת ממש בקבוצה נחמדה; אנו מקבלים, אם כן, ש-\( Z=M \).

אבל עדיין לא הוכחנו שאיחוד כל הקבוצות הנחמדות הוא קבוצה נחמדה. התוכנית היא כזו: לכל קבוצה נחמדה \( A\subseteq M \) קיימת קבוצה טרנזיטיבית \( N_{A} \) ואיזומורפיזם \( f_{A}:A\to N_{A} \). עכשיו נבנה את האיחוד \( \bigcup A \); אני רוצה לומר שהוא איזומרפי אל \( \bigcup N_{A} \) עם האיזומורפיזם \( \bigcup f_{A} \). עיקר הקושי הוא להראות שהקבוצה \( \bigcup f_{A} \) היא אכן פונקציה, ולא סתם פונקציה אלא איזומורפיזם; אם יש לנו את זה, צריך להראות ש-\( \bigcup N_{A} \) היא קבוצה טרנזיטיבית אבל זה קל - איחוד של קבוצות טרנזיטיביות הוא טרנזיטיבי ישירות מההגדרה.

אז אנחנו מתמקדים ב-\( f=\bigcup f_{A} \). הקבוצה הזו נוצרת מכך ש”מדביקים ביחד” את כל ה-\( f_{A} \)-ים השונים. החשש הראשון הוא ש-\( f \) לא תהיה בכלל פונקציה; כלומר, שבקבוצה \( \bigcup f_{A} \) יהיו שני איברים \( \left(a,n_{1}\right),\left(a,n_{2}\right) \) שהורסים את תכונת ה”יחידות” שמגדירה פונקציה (לכל קלט קיים פלט יחיד). עכשיו, אם יש שני איברים כאלו, הם חייבים להגיע משני \( A \)-ים שונים (כי אם הם היו נובעים מאותו \( A \), כבר \( f_{A} \) לא הייתה פונקציה). אז ניקח קבוצות \( A_{1},A_{2} \) כלשהן עם איזומורפיזמים \( f_{A_{1}}:A_{1}\to N_{1} \) ו-\( f_{A_{2}}:A_{2}\to N_{2} \) ונוכיח שלכל איבר משותף להן, \( a\in A_{1}\cap A_{2} \), מתקיים \( f_{A_{1}}\left(a\right)=f_{A_{2}}\left(a\right) \).

בשביל לראות את זה, הנה טענה כללית: אם \( g:A\to N \) הוא איזומורפיזם של קבוצה \( A\subseteq M \) וקבוצה טרנזיטיבית \( N \), ואם \( B\subseteq A \), ואם בנוסף לכך \( B \) היא מה שקראתי לו קודם “טרנזיטיבית ביחס ל-\( M \)”, אז גם \( g\left(B\right) \) הוא קבוצה טרנזיטיבית (תת-קבוצה של \( N \)). כדי לראות את זה, ניקח \( y\in x\in g\left(B\right) \) ונוכיח ש-\( y\in g\left(B\right) \): מכיוון ש-\( x\in g\left(B\right) \) קיים \( b_{x}\in B \) כך ש-\( g\left(b_{x}\right)=x \). עכשיו בגלל ש-\( N \) טרנזיטיבית ו-\( y\in x\in N \) אז \( y\in N \) ומכך ש-\( g \) על נקבל שקיים \( b_{y}\in A \) כך ש-\( g\left(b_{y}\right)=y \). אבל מכיוון ש-\( g \) איזומורפיזם, \( b_{y}\in b_{x}\iff g\left(b_{y}\right)\in g\left(b_{x}\right) \), וקיבלנו שיש שרשרת \( b_{y}\in b_{x}\in B \). מכיוון ש-\( b_{y}\in A\subseteq M \) ומכיוון ש-\( B \) היא טרנזיטיבית ביחס ל-\( M \), נובע מכך ש-\( b_{y}\in B \) ולכן \( y=g\left(b_{y}\right)\in g\left(B\right) \), שזה מה שרצינו.

עכשיו אני משתמש במה שהראיתי בפסקה הקודמת זה על החיתוך \( A_{1}\cap A_{2} \). בשביל זה צריך להראות טרנזיטיביות שלו ביחס ל-\( M \), וזה נובע מכך שאם \( a\in A_{1}\cap A_{2} \) אז \( a\in A_{1} \) וגם \( a\in A_{2} \) ולכן \( a\cap M\subseteq A_{1} \) וגם \( a\cap M\subseteq A_{2} \) ולכן \( a\cap M\subseteq A_{1}\cap A_{2} \). מכל זה קיבלנו ש-\( A_{1}\cap A_{2} \) היא אכן קבוצה נחמדה.

איך זה עוזר לנו? בקלות: אני מסתכל על התמונות \( f_{A_{1}}\left(A_{1}\cap A_{2}\right)\cong A_{1}\cap A_{2}\cong f_{A_{2}}\left(A_{1}\cap A_{2}\right) \). קיבלתי ששתי התמונות הללו הן קבוצות טרנזיטיביות שאיזומורפיות זו לזו, ולכן הוכחת היחידות שממנה התחלתי עובדת עבורן - אני מקבל שזו אותה קבוצה, והאיזומורפיזמים, כשמצמצמים אותם ל-\( A_{1}\cap A_{2} \), הם אותו איזומורפיזם. זה בדיוק מה שרציתי להראות.

כל זה הוכיח רק ש-\( f=\bigcup f_{A} \) היא פונקציה. למה היא חח”ע ועל, ולמה היא משמרת את היחס \( \in \)?

זה ש-\( f \) היא על זה מובן מאליו: הטווח של \( f \) הוא \( \bigcup N_{A} \), שהיא איחוד של קבוצות שהתקבלו בתור תמונות של \( A \)-ים; התחום של \( f \) הוא איחוד ה-\( A \)-ים הללו, אז לכל איבר ב-\( \bigcup N_{A} \), המקור שלו נמצא באחד ה-\( A \)-ים הללו וכשאנחנו מפעילים את \( f \) על המקור אנחנו מקבלים את האיבר הזה.

למה \( f \) חח”ע? זה טיפה יותר טריקי. אני צריך להראות שעבור שני \( a_{1},a_{2}\in\bigcup A \) ששונים זה מזה, אם \( f\left(a_{1}\right)=f\left(a_{2}\right) \) אז \( a_{1}=a_{2} \). עכשיו, אם \( a_{1},a_{2}\in A \) עבור קבוצה \( A \) כלשהי זה ברור - ה-\( f_{A} \) על אותה קבוצה היא חח”ע ולכן מקבלים את מה שרוצים. אבל מה אם \( a_{1}\in A_{1} \) ו-\( a_{2}\in A_{2} \) עבור קבוצות שונות?

זה הזמן להחזיר הנחה שלא השתמשתי בה בכלל עד עכשיו - ש-\( M \) היא היקפית. כלומר, שאם \( a_{1},a_{2}\in M \) (כמו במקרה שלנו) אז מספיק להראות \( a_{1}\cap M=a_{2}\cap M \) כדי להסיק \( a_{1}=a_{2} \). במילים אחרות, מספיק להראות שלכל \( x\in M \) מתקיים \( x\in a_{1}\iff x\in a_{2} \).

כעת, \( A_{1},A_{2} \) הן קבוצות “נחמדות”, ובפרט טרנזיטיביות ביחס ל-\( M \). כלומר, אם למשל \( x\in a_{1}\in A_{1} \) אז \( x\in A_{1} \). זה אומר ש-\( f \) מוגדר על \( x \), ומכך ש-\( f \) איזומורפיזם אנחנו מקבלים \( f\left(x\right)\in f\left(a_{1}\right)=f\left(a_{2}\right) \), ועכשיו מ-\( f\left(x\right)\in f\left(a_{2}\right) \) אנחנו מקבלים \( x\in a_{2} \), וזה מה שרצינו; הכיוון השני (\( x\in a_{2} \) גורר \( x\in a_{1} \)) זהה. זה מוכיח ש-\( a_{1}=a_{2} \) ומסביר למה הייתי צריך להניח ש-\( M \) היקפית.

הוכחנו ש-\( f \) היא פונקציה חח”ע ועל; רק נשאר לטפל בשימור הסדר, כלומר להראות שאם \( x,a\in\bigcup A \) וגם \( x\in a \) אז \( f\left(x\right)\in f\left(a\right) \). זה נראה כמו תכונה שהשתמשתי בה זה עתה! וזה נכון: זה ש-\( a\in\bigcup A \) אומר ש-\( a\in A \) עבור קבוצה נחמדה כלשהי \( A \); זה ש-\( A \) נחמדה מאפשר להסיק מ-\( x\in a \) את \( x\in A \) בתנאי שאנחנו יודעים ש-\( x\in M \), אבל הרי התחלנו מכך שגם \( x\in\bigcup A\subseteq M \), כך שאנחנו יודעים את זה. קיבלנו ש-\( x,a \) שייכים לאותה קבוצה ולכן \( x\in a \) גורר \( f_{A}\left(x\right)\in f_{A}\left(a\right) \) אבל כפי שכבר ראינו, \( f=f_{A} \) עבור אברי \( A \). זה מסיים את ההוכחה!

נעבור לרפלקציה

בואו נעצור לרגע וניזכר מה אנחנו רוצים להוכיח, שנקרא “עקרון הרפלקציה”: שלכל פסוק \( \phi \) (פסוק הוא נוסחה ללא משתנים חופשיים, כלומר שערך האמת שלו קבוע ואינו תלוי בהשמה ספציפית) קיימת קבוצה טרנזיטיבית ובת מניה \( M \) כך ש-\( \phi\leftrightarrow\phi|_{M} \).

את \( \phi\leftrightarrow\phi|_{M} \) צריך להבין בתור נוסחה (לא פסוק) שיש בה משתנה חופשי \( M \), וכשאני אומר ש-\( \phi\leftrightarrow\phi|_{M} \) “מתקיים” אני מתכוון שבהשמה שבה אני מציב את הקבוצה \( M \) בתוך המשתנה \( M \), הנוסחה מקבלת ערך T.

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

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

בואו נתחיל עם הבניה של \( M \). כאמור, מה שעומד לנגד העיניים שלנו כשאנחנו בונים את \( M \) לא יהיה פסוק בודד אלא קבוצה סופית של נוסחאות, \( \phi_{1},\ldots,\phi_{n} \), כך שהמשתנים החופשיים של כל אחת מהנוסחאות הללו נופלים בתוך הקבוצה \( x_{1},\ldots,x_{m} \). אני אבנה את \( M \) כך שמתקיים הדבר הבא: לכל \( 1\le i\le n \) ו-\( 1\le j\le m \) ולכל קבוצה של ערכים \( a_{1},\ldots,a_{j-1},a_{j+1},\ldots,a_{m}\in M \):

אם \( \exists x_{j}\phi_{i}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבל את הערך T

אז \( \exists x_{j}\left(x_{j}\in M\wedge\phi_{i}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \) מקבל את הערך T (כשמציבים את הקבוצה \( M \) במשתנה \( M \)).

הרעיון פה הוא שכדי לספק נוסחאות של “קיים” מספיק איבר אחד, ומכיוון שמלכתחילה יש לנו רק מספר סופי של נוסחאות, קבוצת כל האיברים שנזדקק להם היא לא גדולה. למה זה לא טריוויאלי לחלוטין? כי ברגע שהוספנו ל-\( M \) משהו, גם הגדלנו את טווח הסיטואציות שלנו. “סיטואציה” כזו כוללת נוסחה \( \phi_{i} \) ומשתנה \( x_{j} \) ויש רק מספר סופי של זוגות כאלו, אבל היא כוללת גם את ההצבה שהצבנו בכל משתני \( \phi_{i} \) למעט \( x_{j} \), וכשאני מגדיל את \( M \) אני גם מוסיף הרבה הצבות חדשות שכאלו.

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

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

טוב, קשקשתי מספיק והגיע הזמן להוכחה. הטריק כאמור יהיה לבנות את \( M \) בשלבים, \( M_{0},M_{1},M_{2},\ldots \) כשבכל שלב נוסיף ל-\( M_{k} \) איברים לקבלת \( M_{k+1} \) ובסוף נגדיר \( M=\bigcup_{k=0}^{\infty}M_{k} \). הבניה עצמה פשוטה: נגדיר \( M_{0}=\left\{ \emptyset\right\} \) ובהינתן \( M_{k} \) נבנה מתוכה את \( M_{k+1} \) על ידי כך שניקח את כל אברי \( M_{k} \) ובנוסף לכל \( 1\le i\le n \) וכל \( 1\le j\le m \) וכל סדרת ערכים \( a_{1},\ldots,a_{j-1},a_{j+1},\ldots,a_{m}\in M_{k} \), אם קיים איבר (ביקום הגדול של תורת הקבוצות, לא ב-\( M_{k} \) או משהו) שכשמציבים אותו ב-\( x_{j} \) הנוסחה \( \phi_{i}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת T, אז נוסיף את האיבר הזה אל \( M_{k+1} \). בבניה הזו \( M_{0} \) סופית ואם \( M_{k} \) סופית גם \( M_{k+1} \) סופית, ולכן קיבלנו בסך הכל אוסף סופי של קבוצות, ומכיוון ש-\( M \) היא איחוד בן מניה של קבוצות סופיות קיבלנו ש-\( M \) בת מניה.

עכשיו, בואו ניזכר מה צריך להוכיח ש-\( M \) מקיימת:

לכל \( 1\le i\le n \) ו-\( 1\le j\le m \) ולכל קבוצה של ערכים \( a_{1},\ldots,a_{j-1},a_{j+1},\ldots,a_{m}\in M \):

אם \( \exists x_{j}\phi_{i}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבל את הערך T

אז \( \exists x_{j}\left(x_{j}\in M\wedge\phi_{i}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \) מקבל את הערך T

כל אחד מהערכים \( a_{1},\ldots,a_{m} \) הללו התווסף אל \( M \) בשלב כלשהו, אז אם ניקח את \( k \) להיות השלב המקסימלי מביניהם אנחנו מקבלים שכל האיברים הללו שייכים אל \( M_{k} \), ולכן ב-\( M_{k+1} \) יש לנו בדיוק איבר קונקרטי של \( M \) שעבורו הנוסחה השניה מקבלת T, כי כך בנינו את \( M \). זה מסיים את הבניה.

עכשיו אנחנו רוצים לחזור אל המטרה שלנו: נתון פסוק \( \phi \) ואנחנו רוצים לבנות \( M \) כך ש-

\( \phi\leftrightarrow\phi|_{M} \)

מה שנעשה הוא לקחת את \( \phi \) וליצור ממנה רשימת נוסחאות באופן הבא:

• אם \( \neg\psi \) ברשימה, נוסיף לרשימה גם את \( \psi \)
• אם \( \psi_{1}\to\psi_{2} \) ברשימה, נוסיף לרשימה גם את \( \psi_{1},\psi_{2} \)
• אם \( \forall x_{j}\psi \) ברשימה, נוסיף לרשימה גם את \( \psi \)

אנחנו מפעילים את הכללים הללו על רשימה שבהתחלה כוללת רק את \( \phi \) ואת אקסיומת ההיקפיות (כזכור, צריך גם אותה), ומקבלים רשימה סופית של נוסחאות, \( \phi_{1},\ldots,\phi_{n} \) שהמשתנים החופשיים שלהם נופלים בתוך הקבוצה \( x_{1},\ldots,x_{m} \). עד כאן, הכל מתקדם על פי התוכנית. שימו לב שגם פה השתמשתי בכך שמספיקים הקשרים \( \neg,\to \) והכמת \( \forall \) כדי לתאר את כל הנוסחאות, כי כל נוסחה שיש לה קשר או כמת אחרת ניתן להחליף בנוסחה שקולה בלעדיו. זה מרגיש לי קצת מוזר כי הרי לפני רגע ההוכחה שלי דיברה על נוסחאות שמופיע בהן הכמת \( \exists \), אבל זו לא בעיה כי אני הולך להשתמש בטריק: כזכור, \( \exists x_{j}\psi \) שקול אל \( \neg\forall x_{j}\left(\neg\psi\right) \), ומה שאני אעשה, במקום לבנות \( M \) עבור הנוסחאות \( \phi_{1},\ldots,\phi_{n} \), זה לבנות \( M \) עבור השלילה שלהן, \( \neg\phi_{1},\ldots,\neg\phi_{n} \). עכשיו בואו נראה שזה עובד.

כרגיל, כשעובדים עם נוסחאות נוח להוכיח באינדוקציה על המבנה שלהן. בזכות האופן שבו בנינו את קבוצת הנוסחאות שלנו, כל נוסחה בקבוצה שלנו שאינה אטומית נבנית מנוסחאות פשוטות יותר שגם כן שייכות לקבוצה, ולכן הוכחה אינדוקטיבית תעבוד כאן. הטענה הכללית שאנחנו מוכיחים היא שלכל השמה של הערכים \( a_{1},\ldots,a_{m}\in M \) למשתנים של \( \psi \) מתקיים

\( \psi\left(a_{1},\ldots,a_{m}\right)\leftrightarrow\psi|_{M}\left(a_{1},\ldots,a_{m}\right) \)

כבר ראינו הוכחה אינדוקטיבית אחת שמערבת רלטיביזציה, וכזכור רובה הייתה טריוויאלית: אם \( \psi \) היא נוסחה אטומית אז רלטיביזציה שלה לא משנה אותה בכלל ולכן כמובן ש-\( \psi\leftrightarrow\psi|_{M} \). עבור \( \psi=\neg\psi^{\prime} \) אנחנו יודעים ש-\( \psi|_{M}=\neg\left(\psi^{\prime}|_{M}\right) \) ומהנחת האינדוקציה \( \psi^{\prime}|_{M}\leftrightarrow\psi^{\prime} \) ולכן נקבל \( \psi|_{M}\leftrightarrow\psi \) (הטיעון המובלע פה הוא שאם \( \psi_{1}\leftrightarrow\psi_{2} \) אז \( \neg\psi_{1}\leftrightarrow\neg\psi_{2} \)).

באופן דומה, אם \( \psi=\psi_{1}\to\psi_{2} \) אז מכך ש-\( \psi|_{M}=\psi_{1}|_{M}\to\psi_{2}|_{M} \) נקבל \( \psi|_{M}\leftrightarrow\psi \). החלק המאתגר היחיד מגיע כשהנוסחה היא מהצורה \( \forall x_{j}\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \).

עכשיו מגיעה הוכחה דו כיוונית שאני אעשה טיפה שונה מבדרך כלל. ראשית אני אניח ש-\( \forall x_{j}\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת T ואוכיח שגם \( \forall x_{j}\psi|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת T . אחר כך אני אניח ש-\( \forall x_{j}\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת F ואוכיח שגם \( \forall x_{j}\psi|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת F. יאללה לעבודה.

בואו נניח קודם כל שהנוסחה \( \forall x_{j}\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת ערך T, ונוכיח מזה שהנוסחה \( \forall x_{j}\left(x_{j}\in M\to\psi|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \) מקבלת T. זה כמובן החלק הקל; לכל ערך שנציב ב-\( x_{j} \), ההנחה שלנו אומרת ש-\( \psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) תקבל T ולכן מהנחת האינדוקציה גם \( \psi|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) תקבל T.

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

נניח עכשיו ש-\( \forall x_{j}\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבלת F. בניסוח שקול: \( \neg\left(\forall x_{j}\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \) מקבלת T, והרי הנוסחה הזו שקולה אל \( \exists x_{j}\neg\psi\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \). והנה זה הגיע: בשביל זה כשבנינו את \( M \) השתמשנו בשלילה של ה-\( \psi \)-ים שלנו.

בואו ניזכר שוב באופן שבו בנינו את \( M \). עשינו זאת כך שיתקיים

אם \( \exists x_{j}\phi_{i}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right) \) מקבל את הערך T

אז \( \exists x_{j}\left(\phi_{i}|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \) מקבל את הערך T.

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

\( \exists x_{j}\left(\left(\neg\psi\right)|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \)

מכיוון שההשמה ל-\( x_{j} \) שמראה שהנוסחה מקבלת T מציבה בו איבר מתוך \( M \) (כלומר, כזה שמקיים את הנוסחה האטומית \( x_{j}\in M \)) נקבל שגם הנוסחה הבאה מקבלת T:

\( \exists x_{j}\left(x_{j}\in M\wedge\left(\neg\psi\right)|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \)

מה שאומר שבאופן שקול, הנוסחה הבאה מקבלת F:

\( \forall x_{j}\left(x_{j}\in M\to\psi|_{M}\left(a_{1},\ldots,x_{j},\ldots,a_{m}\right)\right) \)

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

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