כמה קומפקטי יכול להיות הסבר על משפט הקומפקטיות?

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

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

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

ובכן, להגיד "נכון" או "לא נכון" כאן יהיה עניין של הגדרה בלבד; וכאן בוחרים להגדיר את המשפט כולו במקרה הזה כאמיתי. המוטיבציה המתמטית לכך היא שבדרך כלל המטרה של ה"אז" הזה, שבצורה פורמלית מכונה "גרירה לוגית", היא לספק תנאי מספיק לכך שמשהו יתקיים. כך למשל קל לראות הגיון במשפט "אם הפונקציה $latex f(x)=x^2$ גזירה, אז היא רציפה" כי ידוע לכל סטודנט לחשבון אינפיניטסימלי שגזירות גוררת רציפות. לכן כל אחד משלושת האפשרויות הבאות אפשרית: או שהפונקציה גזירה ורציפה, או שהיא לא גזירה אבל כן רציפה – גם זה בסדר, כי זה לא מפריך את המשפט – או שהיא לא גזירה ולא רציפה – וגם זה לא מפריך את המשפט. הדבר היחיד שיכול להפריך את המשפט (כלומר, לתת לו ערך "שקר") הוא אם הפונקציה גזירה אבל לא רציפה. כלומר, למשפט "A גורר B" נותנים ערך שקר רק כאשר A אמיתי ואילו B שקרי.

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

הפסוקים האטומיים הם פשוט משתנים – שמסומנים, נניח, בתור $latex x_n$ לכל $latex n$ טבעי. כלומר, יכולים להיות אינסוף (בן מניה) של משתנים. הקשרים המקובלים הם "וגם", שמסומן ב-$latex \wedge$; "או", שמסומן ב-$latex \vee$; "לא" (שלילה) שמסומן ב-$latex \neg$ ו"גרירה", שמסומן ב-$latex \rightarrow$. יש עוד קשרים אפשריים (ואפשר להסתדר גם בלי כל הקשרים שתיארתי כאן) אבל אלו לרוב הפופולריים ביותר בגלל הפשטות היחסית שלהם.

הנה דוגמה לפסוק אופייני: $latex ((x_1\vee x_2)\wedge(\neg x_3))\rightarrow x_4$ מה הפסוק בעצם אומר? האם הוא אמיתי או שקרי? זה תלוי במשמעויות שאנחנו נותנים למשתנים. למשל, אם למשתנה הראשון ניתן את ערך הטענה האטומית "מתחשק לי לצאת מהבית" ולמשתנה השני את "מגרשים אותי מהבית" ולשלישי "יורד גשם" ולרביעי "יצאתי לטיול" אפשר לקרוא את המשפט כולו בתור "אם יתחשק לי לצאת מהבית או שיגרשו אותי מהבית, וגם לא ירד גשם, אז אצא לטיול". המשפט יהיה שקרי, למשל, אם אכן מגרשים אותי מהבית ולא יורד גשם, אך איני יוצא לטיול.

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

עד עכשיו ערך האמת של הפסוקים שנתתי היה תלוי בפרשנות שנתתי למשתנים. עם זאת, אפשר לעזוב את הפרשנות המילולית בצד, ולדבר על השורה התחתונה – איזה ערך אמת קיבל כל משתנה, ומה ערך האמת של הפסוק כולו במקרה זה. כך למשל הפסוק שדנו בו כרגע יקבל ערך "שקר" (שאסמן ב-0, וערך אמת אסמן ב-1) עבור ההשמה הבאה: $latex x_1=1, x_2=0, x_3=0, x_4=0$ . כלומר, ניתן להעלות על הדעת פרשנות כלשהי של הפסוק שבה הוא יהיה שקרי. אם אשנה את $latex x_4$ להיות $latex x_4=1$ אבטיח שהפסוק יקבל ערך אמת – כלומר, יש פרשנות שבה הפסוק הוא אמיתי. בקיצור, זה תלוי בהשמה של ערכי האמת למשתנים.

האם זה נכון תמיד? התשובה שלילית. למשל, הפסוק הבא: $latex x_1\vee \neg x_1 $. במילים: "או שירד גשם או שלא ירד גשם". הפסוק האידיוטי הזה הוא מה שנקרא "טאוטולוגיה" – הוא נכון תמיד, בלי תלות בהשמת ערכי האמת אליו. באותו האופן $latex x_1\wedge\neg x_1$ יהיה שקרי תמיד – פסוק כזה נקרא "סתירה". שאלה מעניינת בהינתן פסוק היא "האם הוא סתירה?", אך לרוב שואלים את השאלה בעזרת טרמינולוגיה שונה. נהוג לומר שהשמה מספקת פסוק אם היא נותנת לו ערך אמת, והשאלה "האם הוא סתירה?" היא היפוך השאלה "האם הוא ספיק?", כלומר האם קיימת השמה שמספקת אותו. כבר דיברתי פעם על העניין הזה – עושה רושם שבהינתן פסוק כלשהו שנתון בצורה קנונית שלא ניכנס אליה כעת, בדיקה האם הוא ספיק יכולה להיות מסובכת ולקחת זמן רב – בסדרי גודל דומים לזה של "בדוק את כל ההשמות האפשריות" (הצורה הקנונית אינה הכרחית – אך כאמור, לא ניכנס לזה).

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

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

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

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

6 תגובות בנושא “כמה קומפקטי יכול להיות הסבר על משפט הקומפקטיות?”

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

    ישר כח
    אופיר מאור, פ"ת

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

  3. אגב,
    אני לא יודע אם התכוונת בתרגיל על a ו-b ל"הוכח" או "הפרך",
    אבל אם a,b שליליים ו-a קטן מ-b, אכן יתקבל משפט שקרי…

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *