צורה למציאות

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

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

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

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

אנחנו עושים את זה מדי יום, גם בלי המחשה בצבעים: "או-או", "אם... אז..." ועוד ועוד. תצלום: בריוני

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

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

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

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

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

הנה, למשל, שני טיעונים:

״כל הפוליטיקאים הם פושעים, וחלק מהפושעים הם שקרנים, אז כל הפוליטיקאים הם שקרנים״.

״חלק מהפוליטיקאים הם פושעים וכל הפושעים הם שקרנים, אז חלק מהפוליטיקאים הם שקרנים״.

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

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

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

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

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

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

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

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

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

בשלהי במאה ה-19 התחזקה הנטייה להקצין את המתמטיקה על ידי צמצומה למבנים הלוגיים של האריתמטיקה

בשלהי במאה ה-19 התחזקה הנטייה להקצין את המתמטיקה על ידי צמצומה למבנים הלוגיים של האריתמטיקה, תאוריית המספרים הטבעיים – אלה שניתן להגיע אליהם מאפס על ידי תוספת חוזרת ונשנית של 1 – באמצעות פעולות כמו חיבור וכפל. המתמטיקאי ריצ׳רד דדקינד (Dedekind) הראה אז כיצד האריתמטיקה עצמה ניתן לרדוקציה לתאוריה הכללית של כל הסדרות הנוצרות מנקודת התחלה נתונה על ידי יישום חוזר ונשנה של אופרציה נתונה (0,1,2,3...). התאוריה הזו קרובה מאוד ללוגיקה. הוא הציג שתי מגבלות על הפעולה: ראשית, היא לעולם אינה מניבה את אתה תוצאה עבור נתונים שונים; שנית, היא לעולם לא מניבה את נקודת ההתחלה המקורית. בהתאם למגבלות אלה, הסדרה אינה יכולה לחזור על עצמה והיא חייבת להיות אינסופית.

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

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

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

ישנם בדיוק שני תפוחים.

ישנם בדיוק שני תפוזים.

שום תפוח אינו תפוז.

לכן:

ישנם בדיוק ארבעה תפוחים ותפוזים.

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

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

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

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

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

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

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

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

השפיע השפעה עמוקה על הפילוסופיה של הלשון, המתמטיקה והלוגיקה: גוטלוב פרגה (1879). תצלום: ויקיפדיה

מאחר שברור למה אנחנו מתכוונים באומרנו ״קבוצה שאינה חברה בעצמה״, אנו יכולים להחליף את הביטוי ב-Xבעיקרון ההכלה הבלתי מוגבלת. לכן, ישנה קבוצת כל הקבוצות שאינן חברות בעצמן. קראו לסט הזה R (לכבודו של ראסל). האם R היא חברה בעצמה? במילים אחרות, האם R היא קבוצה שאינה חברה בעצמה? כשחושבים על כך, מגלים כי אם R היא חברה בעצמה, אז היא איננה, וגם היא איננה, אז היא כזו – חוסר עקביות!

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

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

לוגיקנים ומתמטיקאים בחנו דרכים רבות להגבלת העיקרון במידה שתמנע סתירות, אבל לא תפגע בחקירות המתמטיות הרגילות. בחיבורם העצום Principia Mathematica (״עקרונות המתמטיקה״, משנת 1910-13), ראסל ואלפרד נורת׳ וייטהד כפו מגבלות קשיחות מאוד כדי להשיב את העקביות תוך שמירה על כוח מתמטי מספיק שיאפשר המשך של וריאציה על הפרויקט של פרגה, אגב רדוקציה של מרבית המתמטיקה למערכת לוגית עקבית. אולם, למטרות מתמטיות מסורבל מדי לעבוד עם המערכת הזו. מתמטיקאים מעדיפים כעת מערכת פשוטה וחזקה יותר, שנוצרה בערך באותה עת כמו זו של ראסל, על ידי ארנסט צמרלו ומאוחר יותר הורחבה על ידי אברהם פרנקל. בבסיסה מונחים מושגים איטרטיביים (חזרתיים), משום שאקסיומת זמרלו-פרנקל מתארת כיצד יותר ויותר קבוצות נוצרות על ידי איטרציה של אופרציות לבניית קבוצות. למשל, עבור כל קבוצה ישנה קבוצה של כל תתי הקבוצות, שהיא גדולה יותר.

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

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

קורט גדל חולל מהפכה כשהוכיח שלכל מערכת כללים יש תחום משלה, ושלוגיקה כללית לא תוכל להקיף את כל התחומים. תצלום: AK Rockefeller

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

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

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

הניח פצצה מחשבתית-לוגית בדמות פרדוקס לוגי: ברטרנד ראסל (1957), תצלום: ויקיפדיה

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

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

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

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

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

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

כמעט בו זמנית בשנים 1935-36, הראו אלונזו צ׳רץ׳ בארצות הברית ואלן טיורינג בבריטניה כי אלגוריתם כזה אינו אפשרי. לשם כך, הם נאלצו ראשית כל להתאמץ ולחשוב באופן יצירתי מה בדיוק אמור להיות האלגוריתם – דרך מכאנית לגמרי לפתרון בעיה שלב אחר שלב – שאינו מותיר מקום לשיפוט או החלטה. כדי להפוך אותו לקונקרטי יותר, טיורינג העלה תיאור מדויק של מכונת חישוב אוניברסלית דמיונית, שיכולה בעיקרון לבצע כל אלגוריתם. הוא הוכיח ששום מכונה כזו לא תוכל לפתור את ״בעיית ההכרעה״. למעשה, הוא המציא את המחשב (אם כי בזמנו המילה ״מחשב״ שימשה לתיאור בני אדם שתפקידם היה לבצע חישובים; ישנו פילוסוף שאהב לציין כי הוא נישא למחשב[ת]). שנים ספורות לאחר מכן, טיורינג בנה מחשב חשמלי כדי לפצח את הצפנים הגרמניים בזמן אמת במהלך מלחמת העולם השנייה, ותרם בכך תרומה מרכזית לתבוסת הצוללות הגרמניות בצפון האוקיאנוס האטלנטי. התוכנות על המחשב האישי שלכם הוא תשובה אחת מעשית לשאלה ״למה חשובה הלוגיקה?״

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

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

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

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

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

טימותי ויליאמסון (Williamson) מלמד לוגיקה באוניברסיטת אוקספורד. תחומי המחקר העיקריים שלו הם לוגיקה פילוסופית, אפיסטמולוגיה, מטפיזיקה ופילוסופיה של השפה. ספריו האחרונים כוללים את Suppose and Tell (משנת 2020) ו- Debating the A Priori (אשר נכתב בשנת 2020 ביחד עם פול בוגוסיאן).

AEON Magazine. Published on Alaxon by special permission. For more articles by AEON, follow us on Twitter.

תרגם במיוחד לאלכסון: דפנה לוי

תמונה ראשית: "קומפוזיציה מס' 11" מאת פיט מונדריאן מועמדת למכירה בבית המכירות "כריסטי'ס" בלונדון, אפריל 2021. תצלום: Yui Mok, עבור PA Images, אימג'בנק / גטי ישראל