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

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

הקדמה

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

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

נסתכל על הקבוצה  - אוסף כל הפונקציות מתת קבוצה סופית של קבוצת המספרים הטבעיים לקבוצה {0,1}, עם יחס הסדר של הכלה הפוכה (כלומר x חזק מ-y אם x מכיל את y). ניתן לראות כי אם G הוא מסנן גנרי על P אז  היא פונקציה מהטבעיים ל־{0,1}. ניתן לחשוב על f כפונקציה המציינת של תת-קבוצה של המספרים הטבעיים. כיוון ש-G הוא גנרי קבוצה זו שונה מכל תת-קבוצה של הטבעיים שהייתה ב-M: 

אם  ו-g היא הפונקציה המציינת שלה, אז הקבוצה  היא קבוצה צפופה (כל תנאי הוא סופי וניתן להרחיב אותו כך שלא יתאים ל-g), והיא נמצאת במודל הבסיס ולכן G חייב להיחתך איתה. 
באופן הזה ניתן להוכיח כי שלילתה של אקסיומת הבנייה () עקבית - נתחיל ממודל שמקיים את אקסיומת הבנייה ונוסיף לו קבוצה גנרית. הקבוצה החדשה לא הייתה במודל הקודם ולכן לא ניתנת לבנייה, מכאן שהמודל החדש לא מקיים את אקסיומת הבנייה.
בנייה כמעט זהה תספק מודל שלא מקיים את השערת הרצף: 
נוסיף למודל הבסיס את המסנן הגנרי המתאים לסדר החלקי של כל הפונקציות הסופיות מ- ל־{0,1} ( הוא הסודר הראשון שעוצמתו  ו- הוא הסודר של קבוצת המספרים הטבעיים). באמצעות אותם טיעונים כמו בפסקה הקודמת ניתן להראות שאם נאחד את כל האיברים שנמצאים במסנן הגנרי G נקבל פונקציה, שניתן לחשוב עליה כ- פונקציות מציינות של קבוצת טבעיים. טיעונים דומים יראו כי כל הקבוצות המתקבלות שונות ולכן במודל M[G]‎ מתקיים . באופן עקרוני, כפייה יכולה להוסיף פונקציה שממוטטת את  (למשל פונקציה מהטבעיים על ), אך במקרה הזה, על ידי שימוש בתכונות יחס הסדר (ראו בהמשך), ניתן להראות כי זה לא קורה ומתקיים .

מיטוט מונים

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

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

ניתן להגדיר את מושג הכפייה גם באמצעות שימוש באלגבראות בוליאניות. הרעיון הוא שבהינתן אלגברה בוליאנית שלמה B שנמצאת בתוך המודל M אפשר להגדיר "מודל" שערכי האמת שלו אינם רק "נכון" ו"שגוי" אלא איברים מ-B. בפרט לכל x,y לטענה  יהיה ערך ששייך ל-B. 
המודל הבוליאני הזה יקיים למשל שאם טענה אחת גוררת את התקיימות הטענה השנייה, אז ערך האמת של השנייה הוא גדול יותר משל הראשונה, במונחים של יחס הסדר החלקי המוגדר על B. בנוסף, אם M קיים את אקסיומות ZFC אז המודל הבוליאני יקיים אותן עם ערך אמת 1 (המקסימום של B). 
המקבילה שלנו למסנן הגנרי עבור יחס סדר כללי, היא על-מסנן ב-B שהוא M-שלם, כלומר על מסנן בו לכל , יש חסם תחתון ב-G לאיברי X. אפשר לחשוב על על-המסנן הזה כ"החלטה" אלו ערכי מתוך B מייצגים "אמת" ואלו מייצגים "שקר", ובכך G הופך את המודל עם הערכים הבוליאניים למודל סטנדרטי של תורת הקבוצות. 
ההגדרה הזו שקולה להגדרה שהצגנו לעיל, כיוון שמצד אחד כפייה עם יחס הסדר החלקי  מספקת על מסנן כרצוי, ומצד שני כל יחס סדר חלקי משוכן באופן צפוף באלגברה בוליאנית שלמה. 
הבחירה המקובלת, שמשמעות היחס p < q היא "q חלש יותר מ-p" (עבור זוג תנאים במושג הכפייה), נובעת מכיוון הסימון המקובל באלגבראות בוליאניות - שם ככל שתנאי גדול יותר הוא מוסר פחות אינפורמציה על על-המסנן אליו הוא שייך. שהרן שלח נוהג לסמן את כיוון יחס הסדר של הכפייה באופן הפוך, כלומר במאמריו, משמעות הביטוי p < q היא "q חזק יותר מ-p". מנהג זה התקבל בקרב מספר מתמטיקאים ישראלים נוספים, בעקבות העבודות של שלח.

פורמליזם

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