בעקבות השערת הרצף, חלק ב': האקסיומות של צרמלו-פרנקל

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

ראשית כל, ZFC היא מה שנקרא תורה מסדר ראשון. הסברתי את זה לא מזמן כשדיברתי על מחלקות, אבל הנה עוד תזכורת זריזה, פורמלית יותר: באופן כללי, שפה מסדר ראשון נבנית כוללת אוסף של סימנים עבור יחסים \( R_{1},R_{2},\ldots,R_{n} \), עבור פונקציות ועבור קבועים, אבל במקרה של ZFC אין שימוש בסימני פונקציה או קבועים וזה מפשט משמעותית עניינים מסויימים, כך שלא אכנס להגדרות הנוספות שקשורות ליצורים הללו (הנה פוסט שלי על לוגיקה מסדר ראשון כללית, לסקרניות).

אל סימני היחסים אנחנו מצרפים עוד דברים: קבוצה אינסופית בת מניה של סימנים עבור משתנים, וסימנים של קשרים לוגיים \( \neg,\wedge,\vee,\to,\leftrightarrow \) וכמתים לוגיים \( \forall,\exists \) וסימנים לסוגריים. מכל אלו בונים נוסחאות על פי ההגדרה הרקורסיבית הבאה:

• אם \( R \) הוא סימן יחס עם \( n \) מקומות ו-\( x_{1},\ldots,x_{n} \) הם משתנים כלשהם (לאו דווקא \( n \) המשתנים הראשונים בקבוצת המשתנים שלנו; כל אוסף של \( n \) משתנים), אז \( R\left(x_{1},\ldots,x_{n}\right) \) היא נוסחה. נוסחאות שנבנות כך נקראות נוסחאות אטומיות כי הן הסוג הבסיסי ביותר של נוסחה - זה שלא ניתן לחלק אותו עוד ועדיין לקבל נוסחה.
• אם \( \varphi,\psi \) הן נוסחאות אז \( \left(\neg\varphi\right),\left(\varphi\wedge\psi\right),\left(\varphi\vee\psi\right),\left(\varphi\to\psi\right),\left(\varphi\leftrightarrow\psi\right) \) הן נוסחאות.
• אם \( \varphi \) היא נוסחה ו-\( x \) הוא משתנה אז \( \left(\forall x\varphi\right) \) ו-\( \left(\exists x\varphi\right) \) הן נוסחאות.

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

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

הגדרה אחת אחרונה היא של משתנה חופשי ומשתנה קשור. לא פורמלית, משתנה הוא חופשי בתוך נוסחה מסויימת אם הוא לא נופל תחת כמת עבורו בתוך הנוסחה, וקשור אם הוא לא חופשי. למשל בנוסחה \( \forall x\left(x=y\right) \) המשתנה \( y \) הוא חופשי (כי הוא נופל רק תחת הכמת \( \forall x \) שמיועד עבור \( x \) ולא עבורו והמשתנה \( x \) הוא קשור.

אם \( \varphi \) היא נוסחה אטומית, המשתנים שמופיעים בה כולם חופשיים. המשתנים החופשיים בנוסחאות כמו \( \left(\neg\varphi\right),\left(\varphi\wedge\psi\right),\left(\varphi\vee\psi\right),\left(\varphi\to\psi\right),\left(\varphi\leftrightarrow\psi\right) \) הם המשתנים החופשיים של \( \varphi,\psi \). לעומת זאת, המשתנים החופשיים של \( \left(\forall x\varphi\right) \) ושל \( \left(\exists x\varphi\right) \) הם המשתנים החופשיים של \( \varphi \) למעט \( x \) אם הוא הופיע במשתנים החופשיים הללו.

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

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

• (היקפיות): אם לשתי קבוצות יש את אותם איברים, הן שוות.
• (זיווג) לכל שתי קבוצות \( x,y \) קיימת הקבוצה \( \left\{ x,y\right\} \).
• (איחוד) לכל קבוצה \( X \) קיימת הקבוצה \( \bigcup X \).
• (קבוצת החזקה): לכל קבוצה \( x \), הקבוצה \( \mathcal{P}\left(x\right) \) של כל תתי הקבוצות של \( x \) קיימת.
• (יסוד): לכל קבוצה לא ריקה קיים איבר מינימלי ביחס ל-\( \in \).
• (אינסוף): קיימת קבוצה \( x \) כך ש-\( \emptyset\in x \) ואם \( y\in x \) אז גם \( y\cup\left\{ y\right\} \in x \).
• (סכמת ההפרדה): לכל קבוצה \( x \) תת-הקבוצה של האיברים \( u\in x \) שעבורם \( \varphi \) מתקיים קיימת.
• (סכמת ההחלפה): לכל \( x \), אם \( \varphi\left(u,v\right) \) שמצומצמת ל-\( x \) היא פונקציה \( x \) אז הקבוצה \( \varphi\left(x\right) \) קיימת.
• (בחירה): לכל אוסף \( X \) של קבוצות לא ריקות קיימת פונקציית בחירה: \( f:X\to\bigcup X \) כך ש-\( f\left(a\right)\in a \) לכל \( a\in X \).

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

עכשיו אפשר לראות את הניסוח הפורמלי עד הסוף. כדי לעשות אותו קצת קל יותר לקריאה אני אשתמש במשתנים \( A,B \) כדי לתאר קבוצות, \( x,y,z \) כדי לתאר “איברים של קבוצות” (שהם בעצמם קבוצות כמובן) ו-\( \mathcal{F} \) כדי לתאר “משפחה של קבוצות” (שגם היא קבוצה, כמובן).

• (היקפיות): \( \forall A\forall B\left(\forall x\left(x\in A\leftrightarrow x\in B\right)\to A=B\right) \)
• (זיווג): \( \forall x\forall y\exists A\left(x\in A\wedge y\in A\right) \)
• (איחוד): \( \forall\mathcal{F}\exists X\left(\forall A\forall x\left(\left(A\in\mathcal{F}\wedge x\in A\right)\to x\in X\right)\right) \)
• (קבוצת החזקה): \( \forall A\exists X\forall B\left(\forall x\left(x\in B\to x\in A\right)\to B\in X\right) \)

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

\( \forall A\exists X\forall B\left(B\subseteq A\to B\in X\right) \)

כאשר \( B\subseteq A \) הוא סימון לא פורמלי, כלומר, הסימן \( \subseteq \) הוא לא סימן יחס, הוא פשוט כתיב מקוצר; אנחנו כותבים \( B\subseteq A \) במקום לכתוב את הנוסחה \( \forall x\left(x\in B\to x\in A\right) \) שהופיעה קודם. נזדקק לגישה המקוצרת הזו אם לא נרצה להשתגע כשיגיע הזמן לנסח את אקסיומת האינסוף, למשל.

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

בואו ננסח את אקסיומת ההפרדה הכי פורמלי שאפשר. ניקח נוסחה \( \varphi\left(u,p_{1},\ldots,p_{n}\right) \) כלשהי כך שהמשתנים החופשיים שלה שייכים לקבוצה \( \left\{ x,p_{1},\ldots,p_{n}\right\} \). קונספטואלית אנחנו חושבים על \( p_{1},\ldots,p_{n} \) בתור משתנים שמגדירים פרמטרים ועל \( x \) בתור המשתנה שמקבל את האיברים שבודקים את שייכותם לתת-הקבוצה שאקסיומת ההפרדה בונה. עכשיו אפשר לעבור לאקסיומה עצמה:

• (סכמת אקסיומת ההפרדה): \( \forall A\forall p_{1}\ldots\forall p_{n}\exists B\forall x\left(x\in B\leftrightarrow x\in A\wedge\varphi\right) \)

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

בואו נשתמש בזה כדי לייצר את הקבוצות של אקסיומות הזיווג/איחוד/קבוצת החזקה. עבור הזיווג, נשתמש בנוסחה \( z=x\vee z=y \) (כאשר כאן \( z \) הוא המשתנה שמייצג את האיבר שאנחנו “מסננים” מתוך \( A \)) - הנוסחה הזו מבטיחה שהאיבר שאנחנו מסננים יהיה או \( x \) או \( y \) ושום דבר פרט אליהם.

עבור איחוד הקבוצות ששייכות ל-\( X \), נשתמש בנוסחה \( \exists A\left(A\in X\wedge z\in A\right) \) שמבטיחה שנסנן רק איברים שנמצאים באחת מהקבוצות ב-\( X \). ועבור קבוצת החזקה, נשתמש בנוסחה \( \exists B\left(B\subseteq A\wedge z\in B\right) \) (כאן השתמשנו שוב ב-\( \subseteq \) בתור קיצור לנוסחה מורכבת יותר).

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

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

את הנוסחה הזו אני אסמן בצורה מקוצרת בתור \( \exists!y\varphi\left(x,y,p_{1},\ldots,p_{n}\right) \).

עוד דבר ששווה לכתוב בצורה מקוצרת הוא הגבלה של כמת כך שירוץ רק על אברי קבוצה מסוימת. אני ארצה לכתוב דבר כזה בתור \( \forall x\in A\left(\psi\right) \) או \( \exists x\in A\left(\psi\right) \). הראשון הוא סימון מקוצר עבור \( \forall x\left(x\in A\to\psi\right) \) והשני עבור \( \exists x\left(x\in A\wedge\psi\right) \).

כל אלו יקלו עלינו לכתוב את סכמת אקסיומת ההחלפה:

• (סכמת אקסיומת ההחלפה): \( \forall A\forall p_{1}\ldots\forall p_{n}\left(\forall x\in A\exists!y\varphi\to\exists B\forall x\in A\exists y\in B\varphi\right) \)

גם כאן, שימו לב שזה לא מוכיח באופן ישיר שהקבוצה \( \varphi\left(A\right) \) קיימת; רק שקיימת קבוצה שמכילה את \( \varphi\left(A\right) \) ואפשר לקבל אותה בעזרת אקסיומת ההפרדה.

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

בואו נתחיל מאקסיומת היסוד. באופן לא פורמלי היא אומרת “לכל קבוצה לא ריקה קיים איבר מינימלי ביחס ל-\( \in \)”. כלומר, לכל קבוצה \( A \), אם \( A\ne\emptyset \), אז קיימת \( B\in A \) כך ש… מה? איך מנסחים את “\( B \) מינימלית ביחס ל-\( \in \)”? זה נראה לי מפחיד בהתחלה אבל זה בעצם די פשוט: אם \( B \) אינה מינימלית ביחס ל-\( \in \) זה אומר שקיימת ב-\( A \) קבוצה נוספת, \( C\in A \), כך ש-\( C\in B \); הרי המשמעות של “\( b \) הוא איבר מינימלי” בהקשר של יחס סדר \( \le \) היא שאין \( c \) כך ש-\( c\le b \); זה בדיוק מה שמדובר עליו פה. עכשיו, אם הייתה קיימת \( C \) כזו כך ש-\( C\in A \) וגם \( C\in B \), אז היה מתקיים \( C\in B\cap A \); זה מה שאני הולך להשתמש בו.

אם כן, בכתיב פורמלי, אפשר לתאר את האקסיומה כך:

• (אקסיומת היסוד): \( \forall A\left(A\ne\emptyset\to\exists B\left(B\in A\wedge B\cap A=\emptyset\right)\right) \)

זה כתיב פורמלי, אבל עם סימונים מקוצרים שצריך להסביר איך כותבים בצורה מלאה. ראשית, \( A\ne\emptyset \) זו הנוסחה \( \exists x\left(x\in A\right) \). שנית, \( B\cap A=\emptyset \) זו הנוסחה \( \neg\exists x\left(x\in B\wedge x\in A\right) \).

את אקסיומת האינסוף כבר ניסחנו בצורה המפורשת שלה - במקום לומר “קיימת קבוצה אינסופית”, אמרנו “קיימת קבוצה \( x \) כך ש-\( \emptyset\in x \) ואם \( y\in x \) אז גם \( y\cup\left\{ y\right\} \in x \)”. מכאן הפורמליזציה מגיעה מעצמה:

• (אקסיומת האינסוף): \( \exists A\left(\emptyset\in A\wedge\forall x\left(x\in A\to x\cup\left\{ x\right\} \in A\right)\right) \)

גם כאן השתמשתי בקיצורים. ראשית, \( \emptyset\in A \) הוא קיצור ל-\( \exists y\left(\forall z\neg\left(z\in y\right)\wedge y\in A\right) \). שנית, \( x\cup\left\{ x\right\} \in A \) זה קיצור ל-\( \exists y\left(y\in A\wedge\forall z\left(z\in y\leftrightarrow\left(z=x\vee z\in x\right)\right)\right) \).

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

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

• (אקסיומת הבחירה): \( \forall A\left(\emptyset\notin A\to\exists f:A\to\bigcup A\forall a\in A\left(f\left(a\right)\in a\right)\right) \)

כאן הקיצורים באמת קשים לניסוח פורמלי. ב-\( \emptyset\notin A \) קל לטפל, כי זה בסך הכל \( a\in A\to\exists b\left(b\in a\right) \). אבל קיום של פונקציה \( f \)? פונקציה היא קבוצה של זוגות סדורים שמקיימת כל מני תנאים. צריך קיצורים בתוך הקיצורים. בואו נפרוט את זה צעד-צעד.

ראשית, מופיע שם \( \bigcup A \) וזה מסבך אותי. אז נוסיף לפסוק את \( \exists X\left(\forall B\forall b\left(B\in A\wedge b\in B\right)\to b\in X\right) \) - די דומה לאקסיומת האיחוד שכבר ראינו. אחרי שהוספנו את הנוסחה הזו לפסוק, במקום לכתוב \( \bigcup A \) אפשר לכתוב את \( X \) וזהו. אז כשאני בא לכתוב את \( \exists f:A\to\bigcup A \) אני אראה איך במקום זה כותבים פסוק עבור \( \exists f:A\to B \) עם \( A,B \) כלליים.

ה-\( f:A\to B \) אומר בעצם שלושה דברים:

• \( f \) היא קבוצה של זוגות סדורים \( \left(a,b\right) \) כך ש-\( a\in A \) ו-\( b\in B \).
• לכל \( a\in A \) קיים \( b\in B \) כך ש-\( \left(a,b\right)\in f \).
• לכל \( a\in A \) ולכל \( b_{1},b_{2}\in B \), אם מתקיים \( \left(a,b_{1}\right)\in f \) וגם \( \left(a,b_{2}\right)\in f \) אז \( b_{1}=b_{2} \).

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

• \( \forall a\forall b\left(\left(a,b\right)\in f\to\left(a\in A\wedge b\in B\right)\right) \)
• \( \forall a\left(a\in A\to\exists b\left(b\in B\wedge\left(a,b\right)\in f\right)\right) \)
• \( \forall a\forall b_{1}\forall b_{2}\left(\left(\left(a,b_{1}\right)\in f\wedge\left(a,b_{2}\right)\in f\right)\to b_{1}=b_{2}\right) \)

וגם קל לתאר את \( f\left(a\right)\in a \) בהינתן שאנחנו יודעים לתאר זוגות סדורים:

• \( \exists b\left(\left(a,b\right)\in f\wedge b\in a\right) \)

אז מה שנשאר לי לעשות הוא להסביר איך לתאר משהו כמו \( \left(a,b\right)\in f \). זה תלוי באופן שבו אנחנו בונים זוגות סדורים מלכתחילה; הבניה הסטנדרטית, שהראיתי כבר כאן, היא \( \left(a,b\right)\triangleq\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \). אז בתור \( \left(a,b\right)\in f \) אפשר לכתוב

• \( \exists A\left(A\in f\wedge A=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \right) \)

אבל איך אני כותב ביטוי כמו \( A=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \) פורמלית? הנה בעיה קצת יותר כללית: איך אני כותב \( A=\left\{ a_{1},\ldots,a_{n}\right\} \), עבור קבוצה סופית \( A \) כלשהי? פשוט מאוד:

• \( a_{1}\in A\wedge\ldots\wedge a_{n}\in A\wedge\forall b\left(b\in A\to\left(b=a_{1}\vee\ldots\vee b=a_{n}\right)\right) \)

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

בהינתן שאנחנו יודעים לכתוב פסוק כזה, ברור איך לממש את \( A=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \):

• \( \exists B\exists C\left(B=\left\{ a\right\} \wedge C=\left\{ a,b\right\} \wedge A=\left\{ B,C\right\} \right) \)

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

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

לאן הולכים עכשיו? השלב הראשון יהיה להציג באופן פורמלי את הרעיון של צמצום היקום של תורת הקבוצות לכדי “תת-יקום” כלשהו \( \mathcal{M} \) ש-ZFC מתקיימת גם בו במובן מסוים - רעיון שנקרא רלטיביזציה. את זה נראה בפוסט הבא.