כפייה (לוגיקה מתמטית)

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

הקדמה

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

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

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

הרעיון המרכזי בשיטת הכפייה הוא לצאת ממודל נתון של תורת הקבוצות, נאמר M, ולהרחיב אותו באמצעות הוספת קבוצה גנרית G; המודל המתקבל, $\ M[G]$, הוא האוסף הקטן ביותר של קבוצות הכולל את M ואת הקבוצה החדשה G, ומקיים את אקסיומות ZFC - אלו הקבוצות שאפשר לבנות מתוך איברי M והקבוצה G. לא ניתן להוסיף קבוצה שרירותית G כיוון שאז ייתכן שחלק מהאקסיומות של ZFC לא יתקיימו. שיטת הכפייה מספקת דרך כללית ביותר להוספת קבוצות שתספק מודלים של ZFC.

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

הגדרה פורמלית

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

נתחיל ממודל בן מנייה של ZFC,‏ M (ראו פרדוקס סקולם). M יקרא מודל הבסיס.

בתוך M נבחר קבוצה סדורה חלקית $\mathbb {P} \in M$. קבוצה זו תקרא קבוצת תנאי הכפייה ונחשוב על איבריה כמידע חלקי לגבי הקבוצה הגנרית G שאנחנו רוצים להוסיף. התכונות של המודל $M[G]$ ייקבעו על ידי התכונות של יחס הסדר. עבור זוג איברים $x,y\in \mathbb {P}$ נאמר ש-x חזק יותר מ-y (או מספק יותר מידע על G מ-y) אם x < y, ביחס הסדר של P. לשם הפשטות נניח כי יש ליחס הסדר איבר מקסימלי (שיסומן 1). נחשוב על האיבר הזה כתנאי שלא מספק לנו שום מידע על G.

קבוצה G תקרא מסנן גנרי עבור P אם היא מקיימת את שלושת התנאים הבאים:

1. G סגורה להחלשה: $x\in G,x<y\rightarrow y\in G$.
2. לכל שני איברים ב-G יש איבר מ-G שחזק יותר משניהם: $x,y\in G\rightarrow \exists z\in G,z\leq x\land z\leq y$
3. לכל קבוצה צפופה D במודל הבסיס, $G\cap D\neq \emptyset$, כאשר D תקרא קבוצה צפופה אם לכל $x\in P$ יש $y\in D$ כך ש-$y\leq x$.

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

המודל M[G]‎ יוגדר באופן הבא: נגדיר בתוך מודל הבסיס M מחלקה של שמות. שמות אלו יהיו קבוצות בתוך M שעל ידי ידיעת G יתורגמו לאיברים של M[G]‎. באופן פורמלי, אנחנו מגדירים אותם ברקורסיה כקבוצות של זוגות סדורים מהצורה $(\tau ,p)$ כאשר $\tau$ הוא שם ו-$p\in \mathbb {P}$. התרגום על ידי G של שם x יוגדר גם באופן רקוסיבי: $val(x,G)=\{val(y,G)|(y,p)\in x,p\in G\}$.

ניתן לתת שמות קנוניים לאיברי M שיתורגמו לעצמם עבור כל מסנן גנרי, ולכן $M\subset M[G]$.

כעת, נוכל לדבר על שפת הכפייה - בתוך M נוכל להגדיר את הביטוי $p\Vdash _{\mathbb {P} }\psi (\tau _{0},\tau _{1},\dots ,\tau _{n-1})$ ("p כופה את הפסוק") עבור נוסחה $\psi$ ושמות $\tau _{i}$, שמשמעותו תהיה שלכל מסנן גנרי G המכיל את p המודל M[G]‎ מקיים את הנוסחה $\psi (val(\tau _{0},G),...,val(\tau _{n-1},G))$.

הגדרה זו, כפי שנוסחה להלן, לא נעשית בתוך M (כיוון ש-M לא מכיל אף מסנן גנרי), אך ניתן להגדיר הגדרה שקולה עבור אותו מושג שמתייחסת רק לתכונות של יחס הסדר P, אותן מודל הבסיס M "מכיר". לכן, בתוך M, אפשר לדבר על קבוצות של שמות עבורן מתחת לתנאי מסוים p מתקיימת טענה מסוימת. עובדה זו מאפשרת לנו להוכיח שאם M מקיים את אקסיומות ZFC גם M[G]‎ יקיים אותן.

בנוסף גם הכיוון ההפוך נכון: כל נוסחה שמתקיימת במודל M[G]‎ נכפית על ידי תנאי $p\in G$ מסוים. כלומר, ניתן לנתח תכונות של המודל החדש על ידי בחינת נוסחאות בשפת הכפייה במודל הבסיס: במודל M ניתן לנסח ולהוכיח טענות כמו למשל "התנאי 1 כופה ש-x הוא שם של פונקציה מהטבעיים על קבוצת החזקה של הטבעיים של M", ששקולה לכך שקיימת פונקציה ב-M[G]‎ מהטבעיים על קבוצת החזקה של מודל הבסיס. M לא מכיר פונקציה כזו (כי הוא מקיים את ZFC, ובפרט את משפט קנטור), אך הוא יכול לתת שם כך שלכל מסנן גנרי השם יתפרש כפונקציה מתאימה.

כפיית ממשי כהן ושלילת השערת הרצף

נסתכל על הקבוצה $\mathbb {P} =\{p\subset \mathbb {N} \times \{0,1\}|p{\mbox{ is a finite function}}\}$ - אוסף כל הפונקציות מתת קבוצה סופית של קבוצת המספרים הטבעיים לקבוצה {0,1}, עם יחס הסדר של הכלה הפוכה (כלומר x חזק מ-y אם x מכיל את y). ניתן לראות כי אם G הוא מסנן גנרי על P אז $f_{G}=\cup _{x\in G}x$ היא פונקציה מהטבעיים ל־{0,1}. ניתן לחשוב על f כפונקציה המציינת של תת-קבוצה של המספרים הטבעיים. כיוון ש-G הוא גנרי קבוצה זו שונה מכל תת-קבוצה של הטבעיים שהייתה ב-M:
אם $A\subset \mathbb {N} ,A\in M$ ו-g היא הפונקציה המציינת שלה, אז הקבוצה $D_{g}=\{p\in \mathbb {P} |\exists n\in \mathbb {N} \,\,p(n)\neq g(n)\}$ היא קבוצה צפופה (כל תנאי הוא סופי וניתן להרחיב אותו כך שלא יתאים ל-g), והיא נמצאת במודל הבסיס ולכן G חייב להיחתך איתה.

באופן הזה ניתן להוכיח כי שלילתה של אקסיומת הבנייה ($V\neq L$) עקבית - נתחיל ממודל שמקיים את אקסיומת הבנייה ונוסיף לו קבוצה גנרית. הקבוצה החדשה לא הייתה במודל הקודם ולכן לא ניתנת לבנייה, מכאן שהמודל החדש לא מקיים את אקסיומת הבנייה.

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

נוסיף למודל הבסיס את המסנן הגנרי המתאים לסדר החלקי של כל הפונקציות הסופיות מ-$\omega _{2}\times \omega$ ל־{0,1} ($\omega _{2}$ הוא הסודר הראשון שעוצמתו $\aleph _{2}$ ו-$\omega$ הוא הסודר של קבוצת המספרים הטבעיים). באמצעות אותם טיעונים כמו בפסקה הקודמת ניתן להראות שאם נאחד את כל האיברים שנמצאים במסנן הגנרי G נקבל פונקציה, שניתן לחשוב עליה כ-$\aleph _{2}$ פונקציות מציינות של קבוצת טבעיים. טיעונים דומים יראו כי כל הקבוצות המתקבלות שונות ולכן במודל M[G]‎ מתקיים $2^{\aleph _{0}}\geq \aleph _{2}$. באופן עקרוני, כפייה יכולה להוסיף פונקציה שממוטטת את $\aleph _{2}$ (למשל פונקציה מהטבעיים על $\omega _{2}$), אך במקרה הזה, על ידי שימוש בתכונות יחס הסדר (ראו בהמשך), ניתן להראות כי זה לא קורה ומתקיים $\omega _{2}^{M}=\omega _{2}^{M[G]}$.

תנאי שרשרת

נסתכל על הכפייה שתוארה בסעיף הקודם - הוספת $\aleph _{2}$ תת-קבוצות חדשות של הטבעיים. כדי להוכיח שהמודל שמתקבל אכן לא מקיים את השערת הרצף, אנחנו צריכים להראות שהמונה שהיה מעוצמה $\aleph _{2}$ במודל הבסיס נשאר מעוצמה $\aleph _{2}$ - כלומר שהמסנן הגנרי שהוספנו לא שינה את המונים של המודל.

הדרך להראות זאת היא על ידי שימוש בתנאי השרשרת: כפייה מקיימת את תנאי אנטי-השרשרת הבת-מנייה (c.c.c.) אם כל אוסף איברים לא מתיישבים בזוגות בתוכו הוא לכל היותר בן מנייה (כאשר זוג איברים p,q נקבע מתיישב אם יש תנאי r שחזק משניהם: r<p,r<q).

תנאי זה מגביל מאוד את האפשרויות לקבוצות של סודרים שאנחנו מוסיפים על ידי כפייה, ומאפשר למעשה לחסום אותם באמצעות פונקציות ממודל הבסיס. למשל, נניח כי אנחנו מוסיפים פונקציה מהטבעיים ל-$\omega _{1}$. לפונקציה הזו יש שם ($\sigma$), ותנאי $p\in G$ שכופה אותו להיות פונקציה כזו:

$p\Vdash \sigma :\omega \rightarrow \omega _{1}$

כעת, אנחנו יודעים שמתחת לכל איבר במושג הכפייה יש איבר שקובע את הערך הראשון של הפונקציה. נבחר (במודל הבסיס) אנטי שרשרת מקסימלית של איברים במושג הכפייה שקובעים את הערך הראשון - A. קל לראות, שהמסנן הגנרי G בהכרח יכיל בדיוק איבר אחד מתוך A. אבל A הוא בן מנייה וכל איבר מ-A מאפשר רק ערך אחד לערך הראשון של הפונקציה ולכן בסך הכל אוסף האפשרויות לערך הראשון של הפונקציה הוא קבוצה בת מנייה במודל הבסיס. נמשיך כך ונקבל פונקציה במודל הבסיס $F:\omega \rightarrow 2^{\omega _{1}},F\in M$ כך שמתקיים $\forall i\in \omega \,,|F(i)|\leq \aleph _{0}$

$p\Vdash \sigma \subset F$

כלומר הצלחנו לחסום את הפונקציה החדשה שהוספנו (בעלת השם $\sigma$) על ידי הפונקציה F שנמצאת במודל הבסיס, ו-F מאפשרת לכל ערך רק $\aleph _{0}$ אפשרויות. מכאן, קל להראות כי הכפייה לא יכולה להפוך את $\omega _{1}$ לבן מנייה ובאופן כללי היא אינה משנה את הקופינליות של הסודרים. בפרט, כל המונים של מודל הבסיס הם מונים גם במודל המורחב.

מיטוט מונים

בניגוד לסעיף הקודם, קיימות כפיות רבות בהן אנחנו דווקא רוצים לשנות את המונים של מודל הבסיס. אם סודר מסוים הוא לא מונה, אז יש פונקציה חח"ע ממנו אל סודר קטן ממנו. פונקציה זו תישאר גם המודל המורחב ולכן כפייה לא יכולה להפוך סודר שאינו מונה למונה. לעומת זאת, הכיוון ההפוך יכול לקרות - ייתכן שמודל הבסיס "חושב" שסודר $\kappa$ מסוים הוא מונה אבל המסנן הגנרי שנוסיף יוסיף פונקציה חח"ע ממנו אל מונה קטן יותר $\lambda$. במקרים כאלו נאמר כי הכפייה "מוטטה" את המונה $\kappa$ ל-$\lambda$. למשל, מושג הכפייה $P=\{f\subset \omega \times \omega _{1}||f|<\aleph _{0},f{\mbox{ is function}}\}$, עם הסדר החלקי של הכלה הפוכה, ממוטט את $\aleph _{1}$.

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

מודלים בוליאניים

ניתן להגדיר את מושג הכפייה גם באמצעות שימוש באלגבראות בוליאניות. הרעיון הוא שבהינתן אלגברה בוליאנית שלמה B שנמצאת בתוך המודל M אפשר להגדיר "מודל" שערכי האמת שלו אינם רק "נכון" ו"שגוי" אלא איברים מ-B. בפרט לכל x, y לטענה $x\in y$ יהיה ערך ששייך ל-B.

המודל הבוליאני הזה יקיים למשל שאם טענה אחת גוררת את התקיימות הטענה השנייה, אז ערך האמת של השנייה הוא גדול יותר משל הראשונה, במונחים של יחס הסדר החלקי המוגדר על B. בנוסף, אם M קיים את אקסיומות ZFC אז המודל הבוליאני יקיים אותן עם ערך אמת 1 (המקסימום של B).

המקבילה שלנו למסנן הגנרי עבור יחס סדר כללי, היא על-מסנן ב-B שהוא M-שלם, כלומר על מסנן בו לכל $X\subset G,X\in M$, יש חסם תחתון ב-G לאיברי X. אפשר לחשוב על על-המסנן הזה כ"החלטה" אלו ערכי מתוך B מייצגים "אמת" ואלו מייצגים "שקר", ובכך G הופך את המודל עם הערכים הבוליאניים למודל סטנדרטי של תורת הקבוצות.

ההגדרה הזו שקולה להגדרה שהצגנו לעיל, כיוון שמצד אחד כפייה עם יחס הסדר החלקי $B\setminus \{0\}$ מספקת על מסנן כרצוי, ומצד שני כל יחס סדר חלקי משוכן באופן צפוף באלגברה בוליאנית שלמה.

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

פורמליזם

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

ניתן להתגבר על הבעיה הזו באמצעות עקרון ההשתקפות - לכל קבוצה סופית של אקסיומות, ניתן להוכיח ב-ZFC כי קיים סודר $\alpha$ כך שהאוסף $V_{\alpha }$ (שהוא אוסף כל הקבוצות מדרגה שחסומה על ידי $\alpha$), הוא מודל של אותן אקסיומות, ובפרט ניתן לקחת תת-מודל אלמנטרי בן מנייה של $V_{\alpha }$.

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

ראו גם

• אקסיומת מרטין

קישורים חיצוניים

• כפייה, באתר MathWorld (באנגלית)