אז מה זה חשבון מודולרי?

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

לפני שנתחיל להיכנס לפרטים, הנה האינטואיציה הקלאסית: חשבון מודולורי הוא מה שכולנו עושים כשאנחנו מנסים לדעת מה תהיה השעה עוד כך וכך שעות. אם עכשיו השעה היא 19:00 ואנחנו שואלים "מה תהיה השעה עוד 10 שעות?" אנחנו מוסיפים 10 ל-19, מקבלים 29, ואז מחלקים ב-24 (מספר השעות ביממה), לוקחים את השארית – 5, וזו התשובה. חלקנו עושים את זה אחרת, כמובן; ראשית שואלים "עוד כמה שעות יש עד 24?", רואים שזה 5, ואומרים "אוקיי, אז אחרי חצות יש עוד 5 שעות להוסיף, ומגיעים ל-5" אבל האפקט בשני המקרים הוא אותו אפקט, ואנחנו מקבלים את המספר שמתקבל מפעולת החשבון ה"רגילה" כשאחריה מחלקים ב-24 ולוקחים את השארית. חשבון מודולרי זה בדיוק זה, רק לאו דווקא עם 24 בתור מה שמחלקים בו.

ועכשיו בואו נעבור לפרטים.

מה זה חשבון "רגיל", כולנו יודעים – יש לנו מספרים, יש לנו פעולות של חיבור, כפל, חיסור וחילוק, ואנחנו עושים איתן… דברים. בדרך כלל אנחנו מתחילים את המשחק מהמספרים הטבעיים – \(0,1,2,3,\dots\) (שאני כולל בהם גם את 0). עכשיו, אני רוצה שתשימו לב לכך שבמובן מסויים אפשר להסתפק רק בפעולות של חיבור וכפל, ולהגדיר חיסור וחילוק באמצעותן. למשל, הפתרון למשוואה \(x=5-2\) הוא מספר \(x\) אשר מקיים \(2+x=5\) (כלומר 3), והפתרון למשוואה \(x=6:3\) הוא מספר אשר מקיים \(3\cdot x=6\) (כלומר 2). לא תמיד קיימים פתרונות למשוואות הללו במספרים הטבעיים, למשל למשוואה \(x=2-5\) אין פתרון במספרים הטבעיים, ולכן אנחנו מכניסים לתמונה מספרים שליליים ושברים; אבל בפוסט הזה לא אדבר עליהם בכלל כי לא יהיה בכך צורך.

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

עכשיו, אם יש לנו מספר טבעי \(a\) ומספר טבעי \(n\) שהוא גדול מאפס, אז אפשר לחלק עם שארית את \(a\) ב-\(n\), כפי שרובנו למדנו בבית הספר היסודי. המשמעות של זה היא שאפשר למצוא מספרים שלמים \(q\) ("מנה") ו-\(r\) ("שארית") כך שמתקיים השוויון \(a=nq+r\), ובנוסף לכך \(0\le r<n\). דרך נוחה להוכיח שאפשר לעשות זאת היא באינדוקציה על הגודל של \(a\): אם \(0\le a<n\) אז \(a=n\cdot0+a\) הוא השוויון שלנו (כלומר, \(q=0,r=a\) עובד במקרה הזה). אם \(a\ge n\) אז נתבונן על \(a-n\): מהנחת האינדוקציה אנחנו יודעים שקיימים \(q,r\) כך ש-\(a-n=nq+r\) כך ש-\(0\le r<n\), ולכן (על ידי העברת אגפים) נקבל ש-\(a=n\left(q+1\right)+r\) וזה שוב שוויון כפי שרצינו לקבל.

אם \(a=nq\), כלומר השארית של חלוקת \(a\) ב-\(n\) היא 0, אומרים (באופן מתבקש למדי) ש-\(n\) מחלק את \(a\) והסימון המקובל לכך הוא \(n|a\).

כעת נציג הגדרה חשובה במיוחד: שני מספרים \(a,b\) (טבעים או אפילו שלמים – כלומר, כולל שליליים, שלא תיארתי בפוסט הזה) הם שקולים מודולו \(n\), ואני כותב זאת \(a\equiv_{n}b\), אם השארית שלהם בחלוקה ב-\(n\) היא זהה. כלומר, אם קיים \(0\le r<n\) וקיימים \(q_{1},q_{2}\) כך ש-\(a=nq_{1}+r\) ו-\(b=nq_{2}+r\) אז \(a\equiv_{n}b\). שימו לב שאם השוויונות הללו מתקיימים אז \(a-b=n\left(q_{1}-q_{2}\right)+\left(r-r\right)=n\left(q_{1}-q_{2}\right)\), כלומר \(n|a-b\), וגם ההפך נכון: אם \(n|a-b\) אז \(a-b=nq\) עבור איזה שהוא \(q\), כלומר \(a=nq+b\). נכתוב \(b=nt+r\) כך ש-\(0\le r<n\) ונקבל ש-\(a=n\left(q+t\right)+r\), כלומר השארית של חלוקת \(a\) ב-\(n\) שווה לשארית של חלוקת \(b\) ב-\(n\) והיא \(r\). מסקנה: \(a\equiv_{n}b\) אם ורק אם \(n|a-b\). זה תנאי נוח יותר לבדיקה לעתים קרובות ולכן הצגתי אותו. עוד הערה קטנה היא שלרוב בספרות המתמטית כותבים \(a\equiv b\left(\mbox{mod }n\right)\) כדי לציין שקילות מודולו \(n\); אני אישית פחות אוהב את הסימון הזה והוא פחות נוח לי ולכן אני משתמש ב-\(a\equiv_{n}b\) (שגם הוא סימון סטנדרטי אבל הרבה פחות מקובל).

עכשיו, שקילות מודולו \(n\) היא מה שנקרא במתמטיקה יחס שקילות. זה אומר שהיא מקיימת שלוש תכונות: ראשית, \(a\equiv_{n}a\) לכל \(a,n\) טבעיים (כש-\(n>0\); לא אטרח לציין זאת במפורש כל פעם). זאת מכיוון ש-\(a-a=0\) וכמובן ש-\(n|0\). התכונה לפיה כל \(a\) שקול מודולו \(n\) לעצמו נקראת רפלקסיביות.

כמו כן, שקילות מודולו \(n\) היא סימטרית, כלומר אם \(a\equiv_{n}b\) אז זה אומר ש-\(n|a-b\) ולכן \(n=q\left(a-b\right)\) עבור \(q\) כלשהו, ולכן \(n=-q\left(b-a\right)\) ולכן \(b\equiv_{n}a\), כלומר השאלה מי בצד ימין ומי בצד שמאל אינה ממש חשובה כשמדברים על שקילות מודולו \(n\).

לבסוף, שקילות מודולו \(n\) היא טרנזיטיבית, ומשמעות הדבר היא זו: אם \(a\equiv_{n}b\) וגם \(b\equiv_{n}c\) אז זה אומר שקיימים \(q_{1},q_{2}\) כך ש-\(q_{1}n=a-b\) ו-\(q_{2}n=b-c\). נחבר את שתי המשוואות ונקבל ש-\(\left(q_{1}+q_{2}\right)n=\left(a-b\right)+\left(b-c\right)=a-c\) ולכן \(a\equiv_{n}c\).

באופן כללי במתמטיקה, כל יחס שקילות שמוגדר על קבוצה כלשהי – במקרה שלנו, קבוצת המספרים הטבעיים \(\mathbb{N}\), אבל באותה מידה זה יעבוד עבור השלמים \(\mathbb{Z}\) – משרה על הקבוצה חלוקה למחלקות שקילות. מחלקת שקילות של מספר \(a\) כלשהי, שמסומנת בתור \(\left[a\right]\), היא קבוצת כל המספרים ששקולים לו על פי יחס השקילות הזה. זה מושג לא קל להבנה, אז בואו נראה מה הוא עבור המקרים שלנו. נתחיל בקטן – שקילות מודולו \(2\). מהי מחלקת השקילות של 0 מודולו 2? היא כוללת את כל המספרים \(a\) כך ש-\(2|a-0\), כלומר ש-\(2|a\), כלומר את כל הזוגיים. מסמנים זאת \(\left[0\right]=\left\{ 0,2,4,6,8,\dots\right\} \). באופן דומה, \(\left[1\right]=\left\{ 1,3,5,7,9,\dots\right\} \), כלומר מחלקת השקילות של 1 כוללת את כל האי זוגיים (כי אי זוגי הוא תמיד מהצורה \(2k+1\), ולכן כשנחסר ממנו 1 נקבל משהו שמתחלק ב-2), ואלו כל מחלקות השקילות של היחס "שקילות מודולו 2".

אפשר לעשות את אותו דבר עבור 3, ונגלה שיש שלוש מחלקות שקילות מודולו 3: \(\left[0\right]=\left\{ 0,3,6,9,12,\dots\right\} \) של כל המספרים שמתחלקים ב-3; \(\left[1\right]=\left\{ 1,4,7,10,13,\dots\right\} \) של כל המספרים שמתחלקים ב-3 עם שארית 1, ו-\(\left[2\right]=\left\{ 2,5,8,11,14,\dots\right\} \) של כל המספרים שמתחלקים ב-3 עם שארית 2. ומה קורה באופן כללי? עבור שקילות מודולו \(n\) יהיו לנו \(n\) מחלקות שקילות, שנוח לתאר בתור \(\left[0\right],\left[1\right],\dots,\left[n-1\right]\) – כאן המספרים \(0,1,2,\dots,n-1\) משמשים בתור נציגים של מחלקות השקילות.

ועכשיו נכנסת לתמונה ההגדרה המתמטית המרכזית בפוסט: לכל \(n\) טבעי, אנו מגדירים את הקבוצה \(\mathbb{Z}_{n}=\left\{ \left[0\right],\left[1\right],\dots,\left[n-1\right]\right\} \) של כל מחלקות השקילות מודולו \(n\) של מספרים טבעיים (אם לחדד, לרוב מדברים על מחלקות שקילות של מספרים שלמים, כלומר כולל השליליים, אבל לא היה לי צורך בזה כאן). הקבוצה הזו לכשעצמה היא לא מעניינת; מה שמעניין הוא שאפשר להגדיר עליה פעולות חדשות של חיבור וכפל ש"מושרות" באופן טבעי מהפעולות עבור מספרים רגילים. איך? ובכן, בהינתן \(\left[a\right],\left[b\right]\), איך אפשר להגדיר בצורה הטבעית ביותר את \(\left[a\right]+\left[b\right]\)? בבירור מתבקש להגדיר זאת על ידי \(\left[a\right]+\left[b\right]=\left[a+b\right]\). כלומר, מחלקת השקילות שתוחזר מהחיבור של מחלקות השקילות \(\left[a\right]\) ו-\(\left[b\right]\) תהיה מחלקת השקילות של האיבר \(a+b\). אלא שיש כאן בעיה שצצה באופן כללי כשמגדירים דברים על מחלקות שקילות בעזרת נציגים שלהן: לא מובטח שההגדרה עובדת, כי ייתכן שהיא תלויה בנציג, וצריך להוכיח במפורש שהיא לא.

למה אני מתכוון? ובכן, אני צריך להוכיח שהסיטואציה הבאה אינה אפשרית: שיש לנו \(a,a^{\prime}\) שמייצגים אותה מחלקת שקילות, כלומר \(\left[a\right]=\left[a^{\prime}\right]\), ושיש \(b,b^{\prime}\) כך ש-\(\left[b\right]=\left[b^{\prime}\right]\), אבל שמתקיים \(\left[a+b\right]\ne\left[a^{\prime}+b^{\prime}\right]\). כי אם שתי אלו הן מחלקות שונות, אני אקבל ש-\(\left[a\right]+\left[b\right]=\left[a+b\right]\ne\left[a^{\prime}+b^{\prime}\right]=\left[a^{\prime}\right]+\left[b^{\prime}\right]=\left[a\right]+\left[b\right]\) וקיבלתי סתירה במתמטיקה, שמצביעה על כך שפעולת החיבור של מחלקות שקילות שהגדרתי היא לא חוקית. למרבה המזל, זה לא מה שקורה בפועל; בואו נוכיח את זה.

אני רוצה להראות ש-\(\left[a+b\right]=\left[a^{\prime}+b^{\prime}\right]\), כלומר ש-\(a+b\equiv_{n}a^{\prime}+b^{\prime}\), כלומר ש-\(n|\left(a-a^{\prime}\right)+\left(b-b^{\prime}\right)\). כעת, אני יודע ש-\(a\equiv_{n}a^{\prime}\) ולכן יש \(q_{1}\) כך ש-\(a-a^{\prime}=nq_{1}\). בדומה, \(b\equiv_{n}b^{\prime}\) ולכן \(b-b^{\prime}=nq_{2}\) עבור איזה שהוא \(q_{2}\). מסקנה: \(\left(a-a^{\prime}\right)+\left(b-b^{\prime}\right)=n\left(q_{1}+q_{2}\right)\) ולכן באמת מתקיים \(a+b\equiv_{n}a^{\prime}+b^{\prime}\) ופעולת החיבור מוגדרת היטב. מעולה. ומה עם כפל?

כפל יעבוד באותו האופן: \(\left[a\right]\left[b\right]=\left[ab\right]\), אבל ההוכחה טיפה יותר טריקית. כמקודם, אנחנו יודעים ש-\(a-a^{\prime}=nq_{1}\) ו-\(b-b^{\prime}=nq_{2}\), אבל איך מגיעים מכאן לכך ש-\(ab-a^{\prime}b^{\prime}=nq\) עבור \(q\) כלשהו? נסו לעשות זאת בעצמכם לרגע כדי להרגיש את ה"בעיה".

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

\(ab-a^{\prime}b^{\prime}=ab-ab^{\prime}+ab^{\prime}-a^{\prime}b^{\prime}=a\left(b-b^{\prime}\right)+b^{\prime}\left(a-a^{\prime}\right)=n\left(aq_{2}+b^{\prime}q_{1}\right)\)

זה מוכיח שפעולת הכפל של מחלקות שקילות מוגדרת היטב. אם כל זה קצת אבסטרקטי מדי עבורכם, הנה ניסוח "ברמת המשוואה" של מה שראינו: אם \(a\equiv_{n}a^{\prime}\) ו-\(b\equiv_{n}b^{\prime}\), אז

\(a+b\equiv_{n}a^{\prime}+b^{\prime}\)

\(ab\equiv_{n}a^{\prime}b^{\prime}\)

מה שאומר שבכל פעם שיש לנו משוואה פולינומית מודולרית, אפשר לקחת כל מספר שמופיע בה ולהחליף אותו במספר ששקול לו, מה שלעתים קרובות עוזר לפשט את התוצאה. הנה דוגמא: נניח שאנו רוצים לדעת מהו \(10^{100}\) מודולו 9. אז אנחנו כותבים את המשוואה \(x\equiv_{9}10^{100}\). מה עכשיו? מכיוון ש-\(10\equiv_{9}1\), אפשר להמשיך את המשוואה ולכתוב:

\(x\equiv_{9}10^{100}\equiv_{9}1^{100}\equiv_{9}1\)

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

אם כן, חשבון מודולרי מודולו \(n\) הוא חשבון שמתבצע עם האיברים של \(\mathbb{Z}_{n}\) במקום עם מספרים טבעיים רגילים, או מנקודת מבט קצת אחרת – זה חשבון שמתבצע עם מספרים טבעיים רגילים, אבל כזה שבו אנחנו מחליטים על קבוצת נציגים (שהם מספרים טבעיים) למחלקות השקילות שמהוות את \(\mathbb{Z}_{n}\), עובדים רק עם הנציגים הללו, ובכל פעם שבה אנחנו "חורגים" מהם, אנחנו חוזרים אליהם (על ידי חלוקה ולקיחת שארית). מכיוון שלכתוב \(\left[0\right]\) ו-\(\left[a\right]\) וכדומה כל הזמן זה מסורבל, אנחנו לרוב נוקטים בפועל בשיטה השניה.

עכשיו בואו נדבר על שתי הפעולות שעליהן טרם דיברתי – חיסור וחילוק. מה זה חיסור, באופן כללי? ובכן, נתחיל מחיבור דווקא: יש לנו איבר שהוא "אדיש" לחיבור, במובן זה שאם מחברים אותו עם \(x\) כלשהו, מקבלים \(x\). האיבר הזה הוא 0. עכשיו, לכל מספר טבעי \(a\) קיים מספר נגדי, שאם מחברים אותו עם \(a\) מקבלים את האיבר האדיש לחיבור, כלומר \(0\). אנחנו מסמנים את המספר הנגדי הזה ב-\(-a\), ואנחנו יודעים שהוא לא מספר טבעי (אלא מספר שלילי). אלא שבחשבון מודולרי מתרחש "קסם" – אנחנו לא צריכים להרחיב את מערכת המספרים שלנו כדי לקבל איברים נגדיים: הנגדי של \(a\) הוא פשוט \(n-a\). מה שאומר שלפעמים איבר יכול להיות אפילו הנגדי של עצמו. למשל, בחשבון מודולו \(6\), הנגדי של 2 הוא 4, והנגדי של 3 הוא 3. זה אומר שאפשר לכתוב משוואות כמו \(3\equiv_{6}-3\) והן יהיו תקינות לחלוטין.

איך זה קשור לחיסור? ובכן, כי חיסור אפשר תמיד לראות כפעולה של "חיבור עם נגדי". בואו ננסה להיזכר מאיפה נוצר הצורך בפעולת חיסור בכלל: נניח שיש לנו משוואה מהצורה \(x+a=b\); הדרך לפתור אותה היא לחסר \(a\) משני האגפים ולקבל \(x=b-a\). הסיבה שאנחנו מחסרים היא שאנחנו רוצים להיפטר מ-\(a\) באגף שמאל; אבל מה שאנחנו בעצם עושים כאן הוא לחבר לאגף שמאל את הנגדי של \(a\), ש"מאפס" אותו. לכן בחשבון מודולרי אפשר לחסר בלי בעיות – פשוט מחברים עם הנגדי. למשל, אם יש לנו את המשוואה \(x+2\equiv_{6}5\) פשוט מחברים 4 לשני האגפים ומקבלים \(x\equiv_{6}5+4\equiv_{6}9\equiv_{6}3\). לרוב אנחנו מרשים לעצמנו לכתוב דברים כמו \(-2\) גם בחשבון מודולרי, מתוך הבנה שזה ייצוג של הנגדי של \(2\) (שמודולו 6, למשל, הוא 4). אגב, דרך פשוטה אחרת לחשוב על זה היא ש-\(-2\) הוא פשוט מחלקת השקילות של \(-2\) על פי יחס השקילות מודולו (כאשר מגדירים אותו על כל \(\mathbb{Z}\); אבל חלק מהפואנטה שלי בפוסט הזה היא שאפשר לחשוב על חשבון מודולרי גם בלי לדבר על שלילייים).

חילוק הוא כבר סיפור מעניין יותר. ראשית, התיאוריה הכללית, שמאוד דומה לזו של חיבור. יש לנו איבר אדיש לכפל – 1. לכל מספר \(a\) אפשר להגדיר את ההופכי שלו בתור מספר \(a^{\prime}\)כך ש-\(aa^{\prime}=1\). מסמנים את ההופכי לרוב בתור \(a^{-1}\). עכשיו אפשר להגדיר חילוק בתור כפל בהופכי: אם \(ax=b\) אז \(x=a^{-1}b\) (למה?). לרוע המזל, כאן יש לנו בעיה: ל-0 אין הופכי. אפשר להוכיח בקלות ש-\(0\) כפול כל מספר יהיה 0, ולכן לא נוכל לקבל אף פעם 1 באופן הזה. הנה הוכחה קצרה:

\(0\cdot a=\left(0+0\right)\cdot a=0\cdot a+0\cdot a\)

ועל ידי העברת אגפים מקבלים \(0\cdot a=0\).

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

הבעיה בחשבון מודולרי היא שזה יכול לקרות לעוד איברים חוץ מ-0.

נתחיל ממקרה פשוט שבו זה דווקא לא קורה, חשבון מודולו 7: מי הוא, למשל, ההופכי של 3 מודולו 7? קל לראות שזה 5, כי \(3\cdot5\equiv_{7}15\equiv_{7}1\). אבל האם יש דרך שיטתית ומסודרת למצוא הופכי של מספרים מודולו משהו? התשובה חיובית ואסביר זאת בקרוב.

כעת, אם אני רוצה לחלק ב-3 מודולו 7, אני פשוט כופל ב-5. למשל, כדי לחלק את 6 ב-3 אני כופל ב-5 ומקבל 30, ששקול מודולו 7 ל-2. קסם! בדרך דומה אפשר לחלק בכל מספר מ-1 עד 6, אבל לא ב-0. אם כן, איפה כן יש בעיות עם מספרים ששונים מאפס?

בואו נעבור לדבר על חשבון מודולו 6. בחשבון מודולו 6 לא קשה לראות ש-5 הוא הפיך – תכפלו אותו בעצמו ותקבלו 1. אז כפל ב-5 וחלוקה ב-5 זה בעצם אותו דבר. כנ"ל עבור 1. אבל מה עם שאר המספרים? בואו נתחיל מ-2 ו-3. שימו לב שהמכפלה של שניהם נותנת 6, ששקול מודולו 6 לאפס, כלומר \(2\cdot3\equiv_{6}0\). זו תופעה שפשוט לא קיימת בחשבון "רגיל" – כופלים שני מספרים שונים מאפס, ומקבלים אפס. למספרים כאלו קוראים מחלקי אפס, ואני טוען שאם מספר הוא מחלק אפס מודולו \(n\) הוא לא יכול להיות הפיך מודולו \(n\). הסיבה פשוטה: אם \(ab\equiv_{n}0\) ו-\(b\not\equiv_{n}0\), ואם \(a\) הפיך, אז אפשר לחלק ב-\(a\) ולקבל \(b\equiv_{n}0\), בסתירה למה שהנחנו.

במי עוד לא טיפלנו מודולו 6? ב-4. קל לראות שגם הוא מחלק 0, כי \(4\cdot3=12\equiv_{6}0\). זה מסיים את הסיפור: האיברים שהם הפיכים מודולו \(6\) הם רק \(1,5\). באופן כללי, את האיברים ב-\(\mathbb{Z}_{n}\) שהם הפיכים מודולו \(n\) נהוג לסמן בתור \(\mathbb{Z}_{n}^{*}\). כלומר, ראינו ש-\(\mathbb{Z}{}_{7}^{*}=\left\{ 1,2,3,4,5,6\right\} \) ואילו \(\mathbb{Z}_{6}^{*}=\left\{ 1,5\right\} \). אבל האם יש הגיון כללי שמאפשר לדעת מתי איבר הוא הפיך או מחלק אפס מודולו \(n\)? והאם איבר הוא בהכרח או זה או זה? (שימו לב לכך שבמספרים השלמים הטענה "איבר הוא או מחלק אפס או הפיך" אינה נכונה – למשל, 2 אינו הפיך ואינו מחלק אפס). כאן צריך להכניס לתמונה עוד קצת מתמטיקה; בפרט את מה שנקרא האלגוריתם האוקלידי.

בואו נתחיל מלדבר על שאלה שבמבט ראשון אולי נראית לא קשורה. נניח שיש לנו שני מספרים שלמים \(a,b\), ואנחנו מסתכלים על כל המספרים שניתן לקבל מחיבורים וחיסורים שלהם, כלומר על כל הצירופים הלינאריים \(ax+by\) כאשר \(x,y\) הם מספרים שלמים. האם יש דרך פשוטה לתאר את כל המספרים שיכולים להתקבל בצורה הזו?

יש שלל סיבות שבגללן השאלה הזו מעניינת, אבל בהקשר שלנו היא מעניינת כי תשובה לה נותנת לנו תשובה לשאלה "אילו ערכים מודולו \(n\) יש לכפולות של \(a\)?". מה שנעשה הוא להתבונן על כל המספרים מהצורה \(t=ax+ny\), וכשניקח את המשוואה מודולו \(n\) נקבל \(t\equiv_{n}ax\) (כי \(ny\equiv_{n}0\)). בפרט, \(a\) הפיך מודולו \(n\) אם ורק אם קיימים \(x,y\) כך ש-\(ax+ny=1\). אם כן, שווה לחקור בצורה קצת יותר כללית את אוסף כל הצירופים הלינאריים \(ax+by\) ולהבין איך הוא מתנהג עבור \(a,b\) כלשהם.

נתחיל מאבחנה פשוטה: אם \(d\) הוא מספר טבעי כלשהו כך ש-\(d|a\) וגם \(d|b\) אז \(d|ax+by\) (זה תרגיל קל שדומה לחישובים שכבר עשינו בפוסט). לכן אפשר להציג את כל המספרים מהצורה \(ax+ny\) בתור כפולה של כל \(d\) אשר מחלק את \(a,b\). האם זה אומר גם ההפך – שכל כפולה של \(d\) ניתן לייצג כצירוף לינארי שכזה? הבה ונראה דוגמה. ניקח את המספרים \(a=12,b=8\). שניהם מתחלקים על ידי 2 ולכן ברור שכל צירוף לינארי שלהם יהיה זוגי, אבל האם אפשר לכתוב את 2 כצירוף לינארי שלהם? על פניו לא ברור איך. את 4 קל לכתוב: \(4=12-8\). אבל את 2? אפשר לנסות לפעול שיטתית כך: ראשית "נקפיא" את \(12\) ונראה אילו מספרים אפשר לקבל כשמחברים ומחסרים את 8 ממנו: נגלה את הסדרה \(\dots,-20,-12,-4,4,12,20,\dots\). נראה ש"פספסנו" את 2. עכשיו, בואו נחבר את 12 לעצמו ונקבל 24. איזו סדרה אפשר לקבל כשמחברים או מחסרים כפולות של 8 מ-24? הסדרה \(\dots,-16,-8,0,8,16,24,32,\dots\). שוב "פספסנו" את 2. אבל אולי אם נתחיל מ-36? הבנתם את הרעיון.

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

הסיבה שבגללה כל כפולה של 4 יכולה להתקבל היא שאפשר לקבל את 4 עצמו בתור צירוף לינארי של 12 ו-8. באופן כללי, אם עבור \(d\) כלשהו מתקיים \(d=ax+by\) אז כדי לקבל כפולה כלשהי של \(d\) פשוט נכפיל את המשוואה במה שאנו זקוקים לו, ונקבל \(td=axt+aty\). מה שהופך את 4 למיוחד הוא שמצד אחד, אפשר לקבל את כל הכפולות שלו כצירוף לינארי של 8 ו-12, ומצד שני הוא מחלק כל צירוף לינארי של 8 ו-12, ולכן קבוצת "הצירופים הלינאריים של 8 ו-12" וקבוצת "הכפולות של 4" הן בדיוק אותה קבוצה. זה גם מבהיר מדוע אנחנו לא מסוגלים לקבל את 2 כצירוף לינארי של 8 ו-12: פשוט מאוד, 4 אינו מחלק את 2.

הטענה הזו עובדת באופן כללי. בהינתן \(a,b\) אנו מסמנים ב-\(d=\mbox{gcd}\left(a,b\right)\) את המחלק המשותף המקסימלי של \(a,b\). כדי להוכיח שכל כפולה של \(d\) מתקבלת כצירוף לינארי של \(a,b\) צריך להוכיח שקיים צירוף לינארי שלהם שנותן את \(d\) עצמו, כלומר שקיימים \(x,y\) כך ש-\(ax+by=d\). אציג כעת אלגוריתם, האלגוריתם האוקלידי שבהינתן \(a,b\) גם מוצא את \(d\) וגם כותב אותו כצירוף לינארי של \(a,b\), ובנוסף לכך הוא גם עושה זאת ביעילות, מה שקריטי לחלוטין עבור תורת המספרים החישובית.

האלגוריתם הוא רקורסיבי באופיו, כלומר מתבסס על קריאה לעצמו על מקרה פשוט יותר. בואו נניח שאנחנו מקבלים כקלט \(a,b\) שהם טבעיים ומקיימים \(a>b\). אז אפשר לחלק את \(a\) ב-\(b\) עם שארית ולקבל \(a=qb+r\). כעת, אם \(r=0\) זה אומר ש-\(b\) מחלק את \(a\) ולכן המחלק המשותף הגדול ביותר של שניהם הוא \(b\) עצמו, שאפשר להציג בתור צירוף לינארי טריוויאלי: \(a\cdot0+b\cdot1=b\).

כעת, אם \(r\) גדול מ-0, מגיעה האבחנה המרכזית הבאה: \(\mbox{gcd}\left(a,b\right)=\mbox{gcd}\left(b,r\right)\). כדי לראות זאת, מספיק לשים לב לכך ש-\(a=qb+r\) ולכן אם מישהו מחלק את \(b,r\) הוא בוודאי מחלק את \(a\), וש-\(r=a-qb\) ולכן אם מישהו מחלק את \(a,b\) הוא בוודאי מחלק את \(r\). לכן הקבוצה "המחלקים המשותפים של \(a,b\)" והקבוצה "המחלקים המשותפים של \(b,r\)" שוות. הוכחנו את האבחנה, וממנה נובעת שארית האלגוריתם: באופן רקורסיבי, אנו מוצאים \(x^{\prime},y^{\prime}\) כך ש-\(\mbox{gcd}\left(a,b\right)=bx^{\prime}+ry^{\prime}\), וכעת אנו מציבים \(a-qb\) במקום \(r\), ומקבלים \(\mbox{gcd}\left(a,b\right)=ay^{\prime}+b\left(x^{\prime}-qy^{\prime}\right)\), כלומר \(\mbox{gcd}\left(a,b\right)=ax+by\) כאשר \(x=y^{\prime}\) ו-\(y=x^{\prime}-qy^{\prime}\). קל מאוד לתכנת את זה בפועל.

חזרה לענייננו: יהא \(n\) טבעי כלשהו ונרצה לדעת מתי \(a\) הפיך מודולו \(n\). כפי שהראיתי כבר, אם \(\mbox{gcd}\left(a,n\right)=1\) אז קיימים \(x,y\) כך ש-\(ax+ny=1\) ולכן \(ax\equiv_{n}1\) ומכאן ש-\(a\) הפיך ו-\(x\) הוא ההופכי שלו ויש לנו אלגוריתם יעיל למצוא אותו (ולכן אלגוריתם יעיל לביצוע פעולות חילוק מודולו \(n\)). ומה אם \(\mbox{gcd}\left(a,n\right)=d>1\)? במקרה הזה \(a\) הוא מחלק אפס, כי בואו נסתכל על \(a\cdot\frac{n}{d}\): מכיוון ש-\(d\) מחלק את \(n\), הרי ש-\(\frac{n}{d}\) הוא מספר שלם, וקטן מ-\(n\) (כי \(d>1\)). מצד שני, הביטוי הזה שווה ל-\(\frac{a}{d}\cdot n\equiv_{n}0\) כי \(d\) מחלק גם את \(a\). אז מצאנו ש-\(a\) כפול משהו שאיננו 0 מודולו \(n\) שווה ל-0 מודולו \(n\), והמסקנה היא ש-\(a\) אינו הפיך.

אם כן, מצאנו ש-\(a\) הפיך מודולו \(n\) אם ורק אם המחלק המשותף הגדול ביותר שלהם הוא 1; זו תכונה כל כך חשובה שנותנים לה שם: \(a\) ו-\(n\) הם זרים אם המחלק המשותף המקסימלי שלהם הוא 1. לכן \(\mathbb{Z}_{n}^{*}\) היא קבוצת כל המספרים שזרים ל-\(n\) וקטנים ממנו. זה מסביר למה \(\mathbb{Z}{}_{7}^{*}=\left\{ 1,2,3,4,5,6\right\} \): עבור מספר ראשוני, כל מספר חיובי קטן ממנו זר לו. זה גם מסביר למה \(\mathbb{Z}_{6}^{*}=\left\{ 1,5\right\} \): 2 מחלק את 6 וכך גם 3, ואילו ל-4 יש מחלק משותף גדול מ-1 עם 6: 2.

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

מכסחי הכמתים

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

מה זה? שניה לפני שאפציץ עם ההגדרות הפורמליות, אינטואיציה: הנוסחאות בלוגיקה מסדר ראשון נבנות מתוך כל מני רכיבים בסיסיים שמחוברים עם פעולות לוגיות כמו "וגם", "או", "שלילה", "גורר", וגם שני כמתים – "לכל" ו"קיים". הכמתים הללו אחראים לחלק לא מבוטל מהסיבוך שיש לתורות בלוגיקה מסדר ראשון. הנה דוגמה פשוטה, ואני מזהיר מראש שאני הולך לשקר בה קצת ולגלות איך שיקרתי רק בסוף: את הטענה "\(t\) הוא פתרון של המשוואה \(ax^{2}+bx+c=0\)" קל לבדוק אם נותנים לנו ליד את הערכים של \(t\) ושל \(a,b,c\). לעומת זאת, הטענה "קיים \(t\) שהוא פתרון של המשוואה \(ax^{2}+bx+c=0\)" היא כבר טענה מורכבת משמעותית יותר, שמצריכה אותנו להבין את המשוואה הזו.

איך "מבינים" משוואה כזו? קודם כל צריך להבין מה בכלל ההקשר של המשוואה. האם זו משוואה מעל המספרים הממשיים? מעל המרוכבים? מעל המספרים השלמים בלבד? מודולו 7? האם אנחנו ב-\(p\)-אדיים? על הירח? במאדים? בואו נניח שאנחנו מדברים על המשוואה מעל \(\mathbb{R}\), כדי שיהיה מעניין. פורמלית, האופן שבו כותבים את הטענה הלוגית שטוענת שקיים פתרון למשוואה הוא פשוט הנוסחה\(\exists x\left(ax^{2}+bx+c=0\right)\), והשאלה שלנו היא אם במודל של המספרים הממשיים (שבו פעולות החיבור והכפל הן הפעולות ה"רגילות" על ממשיים) הפסוק הזה הוא בעל ערך אמת. ואיך יודעים דבר כזה? הרי ברור שאי אפשר לעבור על כל המספרים הממשיים ולנסות אחד אחד להציב אותם במשוואה, יש הרבה יותר מדי מהם.

ובכן, קרוב לודאי שרובכם זוכרים משהו על משוואות ריבועיות ויודעים שהתשובה לשאלה תלויה איכשהו בערכים של \(a,b,c\), שהם "משתנים חופשיים" של הפסוק. עבור הצבות מסויימות של ערכים למשתנים יהיה פתרון למשוואה, ועבור הצבות אחרות – לא. איך יודעים? ובכן, נוסחת השורשים מלמדת אותנו שפתרונות המשוואה \(ax^{2}+bx+c=0\) הם \(\frac{-b\pm\sqrt{b^{2}-4ac}}{2a}\). הפתרונות הללו עשויים להיות מספרים מרוכבים ולא ממשיים טהורים; מתי זה עשוי לקרות אם \(a,b,c\) הם ממשיים טהורים? ובכן, רק אם \(b^{2}-4ac<0\) ואז הוצאת השורש תחזיר מספר מרוכב (או, למקרה שלא שמעתם על מספרים מרוכבים, היא פשוט תהיה "פעולה לא חוקית" ולכן לא יהיה פתרון – ממשי – למשוואה). אם \(b^{2}-4ac\ge0\) אז בודאות מוחלטת יש פתרון למשוואה (בגלל החשיבות של הביטוי \(b^{2}-4ac\) יש לו שם וסימון מיוחדים: דיסקרימיננטה, והוא מסומן ב-\(\Delta\)). זה אומר שהנוסחה \(\exists x\left(ax^{2}+bx+c=0\right)\) שקולה לוגית לנוסחה \(b^{2}-4ac\ge0\). למה הכוונה ב"שקולה לוגית"? בחרו ערכים קונקרטיים עבור \(a,b,c\); מובטח לנו שלשתי הנוסחאות יהיה אותו ערך אמת עבור הערכים הללו.

מה ההבדל בין שתי הנוסחאות? ובכן, \(b^{2}-4ac\ge0\) היא נוסחה פשוטה משמעותית יותר מ-\(\exists x\left(ax^{2}+bx+c=0\right)\) כי אין בה כמתים – כדי לבדוק אם היא נכונה או לא, פשוט מבצעים חישוב קצר שכולל את \(a,b,c\), ואת זה אפשר לעשות חיש קל, בזמן שעבור \(\exists x\left(ax^{2}+bx+c=0\right)\) לא הייתה לנו שום שיטה ישירה לדעת אם היא נכונה או לא. הצלחנו "לחסל" את הכמת שהופיע בנוסחה הזו ולהחליף אותה בנוסחה שקולה, פשוטה יותר, ובכך הפכנו בעייה שנראתה בלתי אפשרית מבחינה חישובית (לבדוק אם יש פתרון למשוואה) לבעיה טריוויאלית מבחינה חישובית. זה, על רגל אחת, כל הרעיון שמאחורי חיסול כמתים.

כמובן שמייד צצות כמה שאלות. הנוסחה \(b^{2}-4ac\ge0\) בכלל לא נראית דומה לנוסחה \(\exists x\left(ax^{2}+bx+c=0\right)\), אז איך הגענו אליה? האם יש שיטה כללית לחיסול כמתים? האם תמיד אפשר לבצע חיסול כמתים? כמה זה מסובך? התשובה היא שחיסול כמתים הוא עניין קשה. לעתים קרובות צריך ידע נוסף כדי לבצע אותו עבור מקרים קונקרטיים, וברוב המקרים אי אפשר לבצע אותו בכלל. אבל לפעמים כן אפשר לעשות אותו באופן כללי מאוד – להראות שעבור תורה מסויימת קיים חילוץ כמתים עבור כל הנוסחאות (תכף אסביר מה זה בדיוק אומר – זו לא הגדרה טריוויאלית) וכשהפלא הזה קורה, קורים דברים מגניבים למדי. גולת הכותרת שאני חותר אליה (אבל לא אגיע אליה בפוסט הזה) היא ההוכחה שאריתמטיקת פרסבורגר היא כריעה, וההוכחה עוברת דרך חילוץ כמתים. מה זו אריתמטיקת פרסבוגר? זו כמעט התורה שעליה חל משפט אי השלמות של גדל (שמוכיח שתורת המספרים אינה כריעה), רק בלי כפל. אסביר יותר כשאגיע לשם.

לפני שנעבור לפורמליזם, זמן להסביר איך שיקרתי לכם, ואני בטוח שחלקכם שמו לב לזה. נוסחת השורשים היא נכונה אך ורק כאשר \(a\ne0\). אם \(a=0\) אז \(ax^{2}+bx+c=0\) היא בכלל משוואה ממעלה ראשונה, והתנאי \(b^{2}-4ac\ge0\) תמיד מתקיים למרות שייתכן שלמשוואה לא יהיה פתרון. מתי ייתכן שאין לה פתרון? ובכן, באופן כללי למשוואה \(bx+c=0\) יש את הפתרון \(x=-\frac{c}{b}\), אז די בבירור יש לה פתרון תמיד, למעט המקרה שבו \(b=0\) אבל \(c\ne0\). לכן הנוסחה השקולה האמיתית ל-\(\exists x\left(ax^{2}+bx+c=0\right)\) היא לא \(b^{2}-4ac\ge0\) אלא \(\left(a\ne0\wedge b^{2}-4ac\ge0\right)\vee\left(a=0\wedge\left(b\ne0\vee c=0\right)\right)\), שהיא יותר גדולה ומסורבלת (ולכן לא הצגתי אותה מייד אלא שיקרתי) אבל גם כן חסרת כמתים.

ועכשיו בואו נעבור להגדרות. כפי שהדוגמה שנתתי רומזת, כשמדברים על חילוץ כמתים תמיד עושים את זה ביחס לתורה ספציפית. מה זו תורה? בואו נזכיר בקצרה. בלוגיקה מסדר ראשון תמיד יש לנו מילון שאנחנו עובדים ולפיו ואומר לנו מהם סימני היחסים, הפונקציות והקבועים שבהם אנחנו יכולים להשתמש. למשל, בדוגמה שלעיל, המילון כלל סימני פונקציה עבור חיבור וכפל (\(ax^{2}\), למשל, הוא קיצור של \(a\cdot x\cdot x\)) וסימן יחס עבור \(\ge\) (וגם עבור \(=\) אבל אני נוהג להניח ש-\(=\) מגיע עם כל תורה מסדר ראשון ומפורש תמיד כ"שווה"). בעזרת הסימונים של המילון והסימונים הלוגיים הסטנדרטיים (למשל \(\wedge\) עבור "וגם", או סימונים עבור משתנים) אפשר לבנות נוסחאות. תורה \(T\) היא בסך הכל אוסף של פסוקים, כש"פסוק" הוא נוסחה בלי משתנים חופשיים, ולכן משהו שעבור כל מבנה אפשרי יש לו ערך אמת או שקר. אה, מה זה מבנה? טוב, זו כבר חזרה די ארוכה… יש לי פוסט שמציג את הכל במסודר, ואפשר גם לקרוא בכל ספר לוגיקה סטנדרטי.

עכשיו, אם \(T\) היא תורה ו-\(\varphi\left(\overline{x}\right)\) היא נוסחה שאולי יש בה משתנים חופשיים (אני מסמן ב-\(\overline{x}\) "וקטור של משתנים חופשיים"), אנחנו משתמשים בסימון \(T\models\varphi\left(\overline{x}\right)\) ("\(\varphi\) נובעת לוגית מ-\(T\)") אם לכל מודל \(\mathcal{M}\) שמספק את \(T\), וכל וקטור של איברים \(\overline{a}\) שנלקחים מתוך \(D^{\mathcal{M}}\), \(\varphi\left(\overline{a}\right)\) מסתפקת (מקבלת את הערך True). עד כאן, הכל ברור. זה מוביל אותנו להגדרה האולטרה-חשובה הבאה: שתי נוסחאות \(\varphi,\psi\) הן שקולות מודולו התורה \(T\), אם \(T\models\varphi\leftrightarrow\psi\). כלומר, לכל מודל של \(T\) וכל השמה מתוך המודל למשתנים של \(\varphi,\psi\) (יכולים להיות להם משתנים משותפים וגם משתנים לא משותפים), או ששתי הנוסחאות מסתפקות, או ששתיהן אינן מסתפקות. חשוב מאוד להדגיש שזו אינה שקילות "אבסולוטית" אלא היא מאוד תלויה בתורה \(T\), שכן התורה היא מעין "מסננת" שקובעת אילו מודלים בכלל רלוונטיים לצורך השקילות של \(\varphi,\psi\). הנה דוגמה ממש מטופשת להבהרת הנקודה: הנוסחה \(\exists x\left(x^{2}=a\right)\) שקולה לנוסחה \(a=a\) (שהיא נוסחה שתמיד מקבלת את ערך האמת True) כאשר המודל הרלוונטי הוא המספרים המרוכבים עם הפרשנות ה"רגילה"; אבל במודל של המספרים הממשיים, הנוסחה אינה נכונה אם \(a\) הוא שלילי. לכן המודל הוא קריטי כאן.

והנה הגענו להגדרה. לתורה \(T\) יש חיסול כמתים אם לכל נוסחה \(\varphi\) בשפה של התורה קיימת נוסחה \(\psi\) שקולה מודולו \(T\) שהיא חסרת כמתים. אפשר לחדד טיפה את ההגדרה הזו ולהגדיר אוסף של "נוסחאות בסיסיות" שהן עצמן יכולות להכיל כמתים, וחיסול כמתים פירושו יהיה שאפשר לקבל מ-\(\varphi\) נוסחה שקולה שבנויה מתוך הנוסחאות הבסיסיות באמצעות פעולות בוליאניות בלבד (\(\wedge,\vee,\neg,\to,\leftrightarrow\)) ובלי כמתים. לא נצטרך את זה בהמשך, אז מבחינתי "חסר כמתים" זה אכן חסר כמתים. לגמרי.

בואו נתחיל עם קצת עבודה טכנית. ראשית, הסימנים הלוגיים \(\wedge,\vee,\neg,\to,\leftrightarrow\) הם נחמדים אבל רובם מיותרים: אפשר להסתפק ב-\(\wedge,\vee,\neg\) בלבד, כי \(\alpha\to\beta\equiv\left(\neg\alpha\vee\beta\right)\) ו-\(\alpha\leftrightarrow\beta\equiv\left(\alpha\to\beta\right)\wedge\left(\beta\to\alpha\right)\) (למעשה, אפשר גם לוותר על אחד מבין \(\vee,\wedge\) אבל אשתמש בשניהם בהמשך מטעמי נוחות). שנית, גם \(\forall\) מיותר כי \(\forall x\alpha\left(x\right)\equiv\neg\exists x\neg\alpha\left(x\right)\). לכן מלכתחילה נתעניין בפועל רק בנוסחאות שמורכבות מ-\(\neg,\wedge,\vee,\exists\) ורק עליהן נצטרך להוכיח דברים (מטעמי נוחות אני עדיין אשתמש בסימנים האחרים כשזה מקל עלי, מתוך הבנה שהם בסך הכל סימונים מקוצרים לנוסחאות לעיל).

עכשיו, בדוגמה שלמעלה עיקר האתגר היה לעבור מנוסחה עם כמת "קיים" יחיד לנוסחה בלי כמת כזה בכלל. מסתבר שזה גם האתגר באופן כללי – אם יודעים לטפל רק בכמת "קיים" אחד, אז יש חיסול כמתים. פורמלית, אשתמש במילה "ליטרל" כדי לתאר נוסחה אטומית (כזו שהיא יחס שמופעל על שמות עצם) או שלילה של נוסחה אטומית. אני טוען שאם עבור תורה \(T\) ניתן להמיר כל נוסחה מהצורה \(\exists x\left(\alpha_{1}\wedge\dots\wedge\alpha_{n}\right)\), כאשר כל \(\alpha\) הוא ליטרל, לנוסחה שקולה חסרת כמתים מודולו \(T\), אז ל-\(T\) יש חיסול כמתים. ההוכחה של הטענה היא באינדוקציה על מבנה כל הנוסחאות, ובואו נעשה אותה כדי לקבל תחושה עד כמה זה פשוט:

ראשית, אם \(\alpha\) היא נוסחה אטומית, אז אין בה כמתים, ולכן היא מהווה את חיסול הכמתים של עצמה (כמובן ש-\(T\models\alpha\leftrightarrow\alpha\)).

עכשיו, אם \(\alpha=\neg\beta\) כאשר ל-\(\beta\) כבר יש חיסול כמתים, כלומר יש \(\beta^{\prime}\) חסרת כמתים ששקולה ל-\(\beta^{\prime}\), אז \(\alpha^{\prime}=\neg\beta^{\prime}\) היא נוסחה שקולה חסרת כמתים עבור \(\alpha\). בדומה, השקול של נוסחה מהצורה \(\alpha\wedge\beta\) הוא הנוסחה \(\alpha^{\prime}\wedge\beta^{\prime}\) כך ש-\(\alpha^{\prime}\) ו-\(\beta^{\prime}\) הם השקולים של \(\alpha,\beta\).

נשאר לנו לטפל בנוסחה מהצורה \(\exists x\alpha\), כאשר ל-\(\alpha\) קיימת נוסחה שקולה \(\alpha^{\prime}\) חסרת כמתים (למרות – וזו נקודה מהותית – שב-\(\alpha\) יכולים להיות כמתים). אז \(\exists x\alpha\) שקול ל-\(\exists x\alpha^{\prime}\) (את זה כדאי להוכיח אם לא משוכנעים בכך). עכשיו, \(\alpha^{\prime}\) חסר כמתים, אז אפשר לכתוב אותו בצורה קנונית של פסוק בתחשיב הפסוקים: DNF. כלומר, לכתוב \(\alpha^{\prime}=\bigvee C_{i}\) כך שכל \(C_{i}\) הוא מהצורה \(\left(\alpha_{1}\wedge\dots\wedge\alpha_{n}\right)\) כאשר ה-\(\alpha\) הם ליטרלים (כאן קריטי שהם יהיו ליטרלים ולא "סתם" פסוקים אטומיים – בלי היכולת להשתמש בשלילה זה לא עובד). עכשיו, לא קשה לראות ש-\(\exists x\left(\bigvee C_{i}\right)\) שקול ל-\(\bigvee\exists xC_{i}\), וכל \(\exists xC_{i}\) הוא מהצורה \(\exists x\left(\alpha_{1}\wedge\dots\wedge\alpha_{n}\right)\) שעליה הנחנו שאנחנו יודעים למצוא נוסחה שקולה חסרת כמתים, כך שזה מסיים את ההוכחה. נקודה שיש לתת עליה את הדעת היא שפסוק ה-DNF ששקול ל-\(\alpha^{\prime}\) עשוי להיות גדול לאין שיעור יותר מ-\(\alpha^{\prime}\), וזה בעייתי מאוד למי שמתעניינים בסיבוכיות של הליך חיסול הכמתים (כי יש לזה השפעה ישירה על השאלה עד כמה נוכל להשתמש בחיסול כמתים בפועל) אבל אני לא אומר על זה כמעט כלום בינתיים.

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

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

  1. \(\forall x\forall y\forall z\left(x<y\wedge y<z\to x<z\right)\) (טרנזיטיביות היחס \(<\))
  2. \(\forall x\neg\left(x<x\right)\) (אי-רפלקסיביות היחס).
  3. \(\forall x\forall y\left(x=y\vee x<y\vee y<x\right)\) (לינאריות היחס – אפשר להשוות כל שני איברים).
  4. \(\forall x\forall y\left(x<y\to\exists z\left(x<z\wedge z<y\right)\right)\) (צפיפות היחס – אם \(x<y\) אז יש ביניהם איבר).
  5. \(\forall x\exists y\exists z\left(y<x\wedge x<z\right)\) (אין נקודות קצה: לכל \(x\) קיים איבר גדול ממנו ואיבר קטן ממנו).

אילו מודלים אנחנו מכירים לתורה הזו? ובכן, יחס הסדר על המספרים הטבעיים הוא בוודאי לא טוב כי 0 היא נקודת קצה; גם על השלמים הוא לא טוב כי הוא לא צפוף (אין כלום בין 0 ו-1, למשל). דוגמה טובה אחת למודל של התורה הזו היא המספרים הרציונליים \(\mathbb{Q}\) עם יחס הסדר הרגיל, ודוגמה טובה אחרת היא המספרים הממשיים \(\mathbb{R}\) עם יחס הסדר הרגיל (לעומת זאת המרוכבים \(\mathbb{C}\) אינם דוגמה טובה כי אין עליהם יחס סדר לינארי טבעי).

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

אז מה אנחנו רוצים לעשות? לקחת נוסחה מהצורה \(\exists x\left(\alpha_{1}\wedge\dots\wedge\alpha_{n}\right)\) כאשר כל \(\alpha\) הוא ליטרל, ולהמיר אותה למשהו שקול מודולו \(T\) ללא כמתים. ראשית כל, מהו פסוק אטומי בשפה של התורה \(T\)? יש לנו רק שני סימני יחס ואין בכלל סימני קבועים או פונקציות, אז פסוק אטומי חייב להיות מאוד פשוט: או \(x<y\) או \(x=y\), עבור שני משתנים \(x,y\) כלשהם. לכן כל \(\alpha\) הוא מאחת מארבע צורות אפשריות: \(x<y\) או \(x=y\) או \(\neg\left(x<y\right)\) או \(\neg\left(x=y\right)\).

נתחיל מכך שאפשר להיפטר מהשלילות. שימו לב ש-\(\neg\left(x<y\right)\) שקול מודולו \(T\) ל-\(\left(x=y\vee y<x\right)\). כאן ה"מודולו \(T\)" קריטי, כי השקילות הזו נובעת מאקסיומה 3 של \(T\) ובלעדיה היא פשוט לא נכונה. בדומה, \(\neg\left(x=y\right)\) שקול מודולו \(T\) ל-\(\left(x<y\vee y<x\right)\), גם כן מאקסיומה 3. שימו לב שכאן כבר השתמשנו באופן חזק בפרטים הספציפיים הן של השפה שלנו, והן של התורה \(T\).

הבעיה היא שאמנם נפטרנו מהשלילות, אבל במחיר של החלפת ה-\(\alpha\)-ות שלנו, שהיו נוסחאות אטומיות או שלילות שלהן, בנוסחאות שכוללות \(\vee\)-ים. פורמלית, קיבלנו CNF שהוא מונוטוני, כלומר אין בו ליטרלים שליליים (השם "מונוטוני" מגיע מכך שאם ניקח השמה מסויימת לפסוק ונחליף בה 0 ל-1, הערך של הפסוק יכול רק להשתנות מ-0 ל-1 ולא ההפך). מה שנחמד ב-CNF-ים כאלו הוא שניתן להמיר אותם ב-DNF-ים מונוטוניים (איך? ובכן, לכל השמה שמספקת את הפסוק בונים פסוקית DNF מהצורה \(\left(x_{1}\wedge\dots\wedge x_{n}\right)\) כאשר \(x_{1},\dots,x_{n}\) הם בדיוק המשתנים שמקבלים 1 בהשמה המספקת – בדקו שזה עובד!). לכן נקבל בסופו של דבר \(\bigvee\) של נוסחאות מהצורה \(\exists x\left(\alpha_{1}\wedge\dots\wedge\alpha_{n}\right)\) כאשר הפעם מובטח לנו שכל הליטרלים \(\alpha\) הם ללא שלילה, כלומר או מהצורה \(x<y\) או מהצורה \(x=y\). כל שנותר לעשות הוא לחסל את הכמת בנוסחאות כאלו.

עכשיו, אם \(\alpha_{1}\) שפשוט לא מכילה את המשתנה \(x\), אז הנוסחה \(\exists x\left(\alpha_{1}\wedge\dots\wedge\alpha_{n}\right)\) שקולה לנוסחה \(\exists x\left(\alpha_{2}\wedge\dots\wedge\alpha_{n}\right)\wedge\alpha_{1}\), ובאופן דומה אפשר יהיה להוציא מהסוגריים כל \(\alpha\) שלא מכילה את \(x\). בואו נעבור לדבר על \(\alpha\)-ות שכן כוללות את \(x\). ראשית בואו נטפל בכאלו שהן שוויון. אם \(\alpha\) כלשהי היא מהצורה \(x=x\) אז היא תמיד נכונה, בלי תלות ב-\(x\), ואפשר פשוט להסיר אותה (אם כל הנוסחה "נעלמת" בגלל הסרות כאלו אפשר להחליף אותה בנוסחה \(z=z\) עבור משתנה \(z\) כלשהו שלא יהיה מכומת). מה עוד אפשרי? \(x=y\) עבור משתנה \(y\) כלשהו שאיננו \(x\), כלומר איננו מכומת. זה מקרה משמח במיוחד, כי פירוש הדבר הוא שאפשר למחוק את \(x\) מכל ה-\(\alpha\)-ות ולהחליף אותו ב-\(y\) וחסל.

הנה דוגמה: נניח שיש לנו את הנוסחה \(\exists x\left(\left(x=y\right)\wedge\left(x<z\right)\wedge\left(z<w\right)\right)\); אפשר להחליף אותה בנוסחה \(\left(y=y\right)\wedge\left(y<z\right)\wedge\left(z<w\right)\) ולקבל משהו חסר כמתים ששקול לנוסחה המקורית, ואז סיימנו. לכן נשאר רק לטפל במקרים של \(\alpha\)-ות שהן יחס סדר (התעלול הזה, של "אם המשתנה המכומת שווה למשתנה לא מכומת אז הגיע חזון אחרית הימים" הוא כן משהו סטנדרטי שחוזר על עצמו גם בחיסולי כמתים אחרים).

אז סיימנו עם ליטרלים של \(=\), ונשאר לטפל באלו של \(<\), כלומר ליטרלים מהצורה \(x<y\) או \(z<x\), או \(x<x\), אבל מכיוון שהליטרל האחרון אף פעם לא מסתפק במודל \(T\) (בגלל אקסיומה 2), אם הוא מופיע אפשר להחליף את כל הנוסחה פשוט ב-\(z<z\) (שהוא תמיד False) וחסל. אם כן, אפשר לפצל את הליטרלים שלנו לשתי קבוצות – אלו של "משהו קטן מ-\(x\)" ואלו של "משהו גדול מ-\(x\)". כלומר, הנוסחה שלנו היא \(\exists x\left(\bigwedge_{i}\left(z_{i}<x\right)\wedge\bigwedge_{j}\left(x<y_{j}\right)\right)\). עצרו לשניה וחשבו איך אפשר לחסל את הכמת בנוסחה הזו. זה כבר קל מספיק כדי שאפשר יהיה לראות את זה בעיניים.

התשובה היא זו:

\(\bigwedge_{i,j}\left(z_{i}<y_{j}\right)\). כלומר, לכל זוג של משתנה \(z_{i}\) ומשתנה \(y_{j}\) שהופיעו בנוסחה המקורית, אנו כותבים את אי השוויון \(z_{i}<y_{j}\). למה הנוסחה הזו שקולה לנוסחה המקורית? או, כאן אנחנו משתמשים באופן חזק בתכונות של הסדר. כיוון אחד הוא טריוויאלי: אם \(\exists x\left(\bigwedge_{i}\left(z_{i}<x\right)\wedge\bigwedge_{j}\left(x<y_{j}\right)\right)\) הסתפקה, ברור שגם \(\bigwedge_{i,j}\left(z_{i}<y_{j}\right)\) תסתפקת בגלל טרנזיטיביות יחס הסדר (אקסיומה 1), אבל בכיוון השני הייתה עשויה להיות בעיה, בתיאוריה, אם ה-\(z_{i}\) הגדול ביותר היה "צמוד" ל-\(y_{j}\) הקטן ביותר. למשל, אם המודל שלנו היה הטבעיים, \(z_{i}=5\) ו-\(y_{j}=6\). אלא שהמודל של הטבעיים הוא בלתי אפשרי שכן הסדר הוא צפוף (אקסיומה 4), ולכן תמיד אפשר יהיה למצוא \(x\) בין ה-\(z_{i}\) הגדול ביותר וה-\(y_{j}\) הקטן ביותר.

רגע, רגע, רגע! איפה השתמשנו באקסיומה 5, שאומרות שאין נקודות קצה? היא הכרחית לגמרי, אבל באופן קצת עקיף ומחוכם. נניח שהנוסחה שאנחנו רוצים לחסל בה את הכמת היא פשוטה: \(\exists x\left(x<y\right)\), כלומר אין לנו כאן ליטרלים משני הסוגים (גם \(x<y\) וגם \(z<x\)). במה אנחנו אמורים להחליף אותה? ובכן, ב-\(\bigwedge\) "ריק", שהוא פשוט True (אז אפשר לשים את הנוסחה \(z=z\)). אבל זה נכון רק אם \(\exists x\left(x<y\right)\) היא אכן True; וזה כך רק אם אין בסדר שלנו נקודות קצה, כי אם \(y\) היא נקודת הקצה השמאלית – האיבר הקטן ביותר בסדר – אז \(x\) שמקיים \(x<y\) לא קיים. אם כן, כל חמש האקסיומות נחוצות לנו כאן. זה לא מוכיח, כמובן, שאי אפשר לקבל חיסול כמתים אם אני מסיר את אחת מהאקסיומות; רק ששיטת ההוכחה שבה השתמשתי כאן לא תעבוד.

עכשיו, בואו נקטוף את הפירות. יש שתי מסקנות מיידיות שנובעות מכך שיש חיסול כמתים עבור \(T\): האחד הוא ש-\(T\) היא שלמה, והשני הוא ש-\(T\) היא כריעה. נתחיל משלמות. שלמות פירושה שכל פסוק \(\varphi\) מקיים ש-\(T\models\varphi\) או ש-\(T\models\neg\varphi\). עכשיו, אם יש לנו פסוק \(\varphi\) (כלומר, אין בו משתנים חופשיים), אז אחרי חיסול כמתים נקבל ממנו נוסחה \(\psi\) בלי כמתים, ושהמופעים היחידים של משתנים בה הם מהצורה \(z=z\) או \(z<z\) (שהם פשוט דרך עקומה לציין את הנוסחאות הקבועות True ו-False). כלומר, ערך האמת של \(\psi\) בכלל לא תלוי במודל, ולכן \(T\models\psi\) או \(T\models\neg\psi\) (או שכל המודלים של \(T\) מספקים את \(\psi\), או שכולם מספקים את \(\neg\psi\)), ומכיוון ש-\(\psi\) שקול ל-\(\varphi\) מודולו \(T\) קיבלנו את מה שרצינו ולכן \(T\) שלמה. זה די נחמד לראות תורה שלמה שהיא גם לא טריוויאלית לחלוטין; בפעם הבאה שמישהו יגיד לכם שמשפטי אי השלמות של גדל מוכיחים שכל תורה מתמטית היא לא שלמה, תדעו מה לענות לו!

נעבור לכריעות. לומר ש-\(T\) כריעה פירושו שלכל פסוק \(\varphi\) ניתן לקבוע אלגוריתמית אם הוא יכיח מ-\(T\) או לא, מה ששקול לכך שהוא נובע לוגית מ-\(T\) (בגלל משפט השלמות של גדל). כאן האלגוריתם די מובן מאליו: נתון \(\varphi\)? בנו ממנו את הנוסחה \(\psi\) חסרת הכמתים השקולה ותבדקו אם היא True או False. סוף הסיפור. את הליך הבניה תיארתי קודם – הוא היה קונסטרוקטיבי למהדרין (אבל כלל כמה שלבים לא יעילים של מציאת DNF של דברים – זה חשוב כשנכנסים לשאלות של סיבוכיות, אבל אני לא עושה את זה הפעם).

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

מטריצות צמודות, הרמיטיות, אוניטריות

אולי התוצאה המעניינת ביותר באלגברה לינארית בסיסית היא הקשר שיש בין טרנספורמציות לינאריות \(T:V\to V\) המוגדרות על מרחב וקטורי ממימד סופי \(V\) ובין מטריצות. כזכור, מרגע שבו אנחנו קובעים בסיס \(B\) ל-\(V\), אוטומטית נובעת מכך התאמה חד-חד-ערכית ועל בין אוסף הטרנספורמציות הלינאריות \(T:V\to V\) (לפעמים אכתוב "אופרטור לינארי" במקום; המילה "אופרטור" רומזת שמדובר על טרנספורמציה ממרחב לעצמו) ובין המטריצות מסדר \(n\times n\) מעל אותו שדה כמו \(V\), כאשר \(n\) הוא מימד המרחב \(V\). הרעיון בהתאמה הזו הוא שמתקיים השוויון \(\left[T\right]_{B}\left[v\right]_{B}=\left[T\left(v\right)\right]_{B}\) – במילים, הכפלת המטריצה שמייצגת את האופרטור \(T\) בוקטור הקואורדינטות שמייצג את הוקטור \(v\) על פי הבסיס \(B\) מחזירה את וקטור הקואורדינטות של \(T\left(v\right)\) על פי \(B\). עבור בסיסים שונים, ל-\(T\) יהיו מטריצות מייצגות שונות, ואחד מהדברים שעוסקים בהם באלגברה לינארית הוא השאלה הבאה: בהינתן \(T\), אילו בסיסים קיימים שבהם \(\left[T\right]_{B}\) היא פשוטה במיוחד (למשל, אלכסונית)?

על כל זה כבר דיברתי בעבר. ההקשר הנוכחי שלנו הוא מרחבים וקטוריים עם מבנה נוסף – מרחבי מכפלה פנימית. בפרט, אנחנו רוצים להבין איך המושג של אופרטור צמוד בא לידי ביטוי במטריצות. כזכור, אם \(T\) הוא אופרטור אז קיים אופרטור יחיד \(T^{*}\) כך שמתקיים \(\left\langle T\left(v\right),u\right\rangle =\left\langle v,T^{*}\left(u\right)\right\rangle \) לכל \(v,u\in V\). הוכחת הקיום של \(T^{*}\) היא אמנם קונסטרוקטיבית, במובן זה שאפשר להבין ממנה איך למצוא את \(T^{*}\), אבל בדרך עקיפה וסבוכה; יהיה הרבה יותר פשוט לקבוע בסיס כלשהו ולמצוא ל-\(T^{*}\) מטריצה מייצגת על פי הבסיס הזה בהינתן המטריצה המייצגת של \(T\). אלא שכפי שנראה בקרוב, כבר אי אפשר לקחת "סתם" בסיס – כדי שמציאת המטריצה של \(T^{*}\) מתוך המטריצה של \(T\) תהיה פשוטה, אנחנו צריכים לקחת בסיס אורתונורמלי למרחב. למזלנו מובטח לנו שתמיד יש כזה, אבל מציאה של בסיס כזה עשויה להיות כרוכה לפעמים בחישובים לא נעימים.

אם כן, יהא \(B=\left\{ b_{1},\dots,b_{n}\right\} \) בסיס אורתונורמלי ל-\(V\)ותהא \(T\) טרנספורמציה כלשהי. נסמן \(A=\left[T\right]_{B}\). איך נראית \(A\)? העמודה ה-\(j\)-ית של \(A\) היא בעצם וקטור הקואורדינטות, לפי \(B\), של \(T\left(b_{j}\right)\) (למה? ובכן, צריך להוכיח את זה). עכשיו, עבור בסיסים אורתונורמליים אנחנו יודעים למצוא בקלות את הקואורדינטות של וקטור \(v\) לפי הבסיס \(B\): הקואורדינטה שמתאימה לאיבר הבסיס \(b_{i}\) היא פשוט \(\left\langle v,b_{i}\right\rangle \). לכן במקרה שלנו, \(A_{ij}=\left\langle T\left(b_{j}\right),b_{i}\right\rangle \) (הכניסה בשורה ה-\(i\) והעמודה ה-\(j\) במטריצה היא המכפלה הפנימית \(\left\langle T\left(b_{j}\right),b_{i}\right\rangle \)).

באופן דומה, אם \(A^{*}\) היא המטריצה המייצגת של \(T^{*}\) אז יתקיים עבורה \(A_{ij}^{*}=\left\langle T^{*}\left(b_{j}\right),b_{i}\right\rangle \). עכשיו אעשה תעלול קטן ופשוט אחליף את האינדקסים: \(A_{ji}^{*}=\left\langle T^{*}\left(b_{i}\right),b_{j}\right\rangle \). כעת שימו לב לזה:

\(A_{ij}=\left\langle T\left(b_{j}\right),b_{i}\right\rangle =\left\langle b_{j},T^{*}\left(b_{i}\right)\right\rangle =\overline{\left\langle T^{*}\left(b_{i}\right),b_{j}\right\rangle }=\overline{A_{ji}^{*}}\)

מה הלך פה? השתמשתי במעברים פה בכך ש-\(T^{*}\) צמודה ל-\(T\), ובכך שמכפלה פנימית מקיימת הרמיטיות – אפשר להחליף את הסדר של שני המוכפלים, במחיר של הצמדה (במשמעות של "צמוד מרוכב") של הערך של המכפלה (כבר הסברתי בעבר למה ההצמדה הזו הכרחית). הגענו למסקנה ש-\(A^{*}\) מתקבלת מ-\(A\) על ידי הצמדה (מרוכבת) ושחלוף של \(A\) (הפיכת השורה ה-\(i\) של \(A\) לעמודה ה-\(i\) של \(A^{*}\)). לדוגמה, אם

\(A=\left[\begin{array}{cc}1 & -3\\5-i & i\end{array}\right]\)

אז

\(A^{*}=\left[\begin{array}{cc}1 & 5+i\\-3 & -i\end{array}\right]\)

זה מוביל אותנו להגדרה – אם \(A\) היא מטריצה ריבועית, אז \(A^{*}\) היא המטריצה שמתקבלת משחלוף והצמדה של \(A\) והיא נקראת המטריצה הצמודה של \(A\). זה זמן טוב להזכיר עוד מטריצה שגם היא נקראת לפעמים "המטריצה הצמודה" והתנגשות השמות הזו היא אסון – מטריצה שקראתי לה המטריצה המצורפת ל-\(A\), שמסומנת בתור \(\mbox{adj}A\) ותיארתי בעבר בבלוג.

עכשיו, דיברנו על אופרטורים צמודים לעצמם ועל אופרטורים אוניטריים, וההגדרות עוברות באופן חלק למטריצות: מטריצה שמקיימת \(A^{*}=A\) נקראת מטריצה צמודה לעצמה או מטריצה הרמיטית, ואילו מטריצה שמקיימת \(A^{-1}=A^{*}\) נקראת מטריצה אוניטרית. בואו ננסה להבין איך הן נראות.

בתור התחלה, אם \(A^{*}=A\) עבור מטריצה שכל הכניסות בה ממשיות, פירוש הדבר הוא שהמטריצה סימטרית. כי היא שווה לשחלוף של עצמה. עבור כניסות מרוכבות המצב קצת יותר מסובך. הנה דוגמה למטריצה הרמיטית:

\(\left[\begin{array}{cc}1 & -i\\i & 1\end{array}\right]\)

כמו שאתם רואים, היא לא בדיוק סימטרית. אם נפרק אותה לסכום של שתי מטריצות שאחת מהן כוללת את כל הרכיבים הממשיים והשניה את כל הרכיבים המדומים נקבל שהמטריצה הממשית היא סימטרית, בעוד שהמטריצה המדומה היא אנטי-סימטרית (מטריצה אנטי סימטרית היא מטריצה \(A\) כך ש-\(A^{t}=-A\)). בפרט, האיברים על האלכסון הראשי של המטריצה שווים להצמדה של עצמם ולכן הם חייבים להיות מספרים ממשיים "טהורים". זה יהיה חשוב בהמשך.

בואו נעבור לדבר על מטריצות אוניטריות. ראשית כל אני רוצה להבין מה הדטרמיננטה של מטריצה כזו יכולה להיות. אם \(A^{-1}=A^{*}\) אז \(A\cdot A^{*}=I\) ולכן \(1=\left|I\right|=\left|AA^{*}\right|=\left|A\right|\left|A^{*}\right|\). ומהי \(\left|A^{*}\right|\)? תחושת הבטן היא ש-\(\left|A^{*}\right|=\overline{\left|A\right|}\), כלומר הדטרמיננטה של הצמוד היא ההצמדה המרוכבת של הדטרמיננטה של \(A\). לא קשה לראות את זה ישירות מההגדרה הפורמלית של דטרמיננטה, למשל בתור סכום של מכפלות. זכרו שלכל מספר מרוכב \(z\) מתקיים \(z\cdot\overline{z}=\left|z\right|^{2}\), ולכן המסקנה היא ש-\(\left|\det A\right|^{2}=1\) (עברתי לסמן דטרמיננטה ב-\(\det\) מסיבות ברורות). מכאן שהדטרמיננטה של \(A\) חייבת להיות 1 בערכה המוחלט (מכיוון שהיא עשויה להיות מספר מרוכב זה עדיין נותן לה לא מעט אפשרויות).

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

\(A=\left[\begin{array}{cc}a & b\\c & d\end{array}\right]\)

אז ההופכית שלה היא

\(A^{-1}=\frac{1}{\left|A\right|}\left[\begin{array}{cc}d & -b\\-c & a\end{array}\right]\)

לא מאמינים? פשוט תכפילו ותראו… הנוסחה הזו היא מקרה פרטי של המשפט לפיו \(A^{-1}=\frac{\mbox{adj}A}{\left|A\right|}\) שהראיתי בעבר. עכשיו, באופן כללי מתקיים

\(A^{*}=\left[\begin{array}{cc}\overline{a} & \overline{c}\\\overline{b} & \overline{d}\end{array}\right]\)

כך שאם מתקיים \(A^{-1}=A^{*}\) אנחנו יכולים להסיק את \(c,d\) בתור פונקציות של \(a,b\):

\(c=-\left|A\right|\overline{b}\)

\(d=\left|A\right|\overline{a}\)

מכיוון ש-\(\left|A\right|=ad-bc\) אז בפרט נקבל \(\left|A\right|=\left|A\right|a\overline{a}+\left|A\right|b\overline{b}=\left|A\right|\left(\left|a\right|^{2}+\left|b\right|^{2}\right)\), כלומר \(\left|a\right|^{2}+\left|b\right|^{2}=1\).

כעת, אפשר לכתוב קונקרטית \(\left|A\right|=e^{i\theta}\) עבור \(0\le\theta\le2\pi\) – זו דרך ההצגה הקוטבית של מספר מרוכב עם ערך מוחלט 1. לכן נקבל שמטריצה \(A\) מסדר \(2\times2\) היא אוניטרית אם ורק אם היא מהצורה

\(\left[\begin{array}{cc}a & b\\-e^{i\theta}\overline{b} & e^{i\theta}\overline{a}\end{array}\right]\)

כך ש-\(\left|a\right|^{2}+\left|b\right|^{2}=1\).

במקרה של מטריצה עם מקדמים ממשיים העסק הופך לפשוט מאוד: במקרה הזה \(\overline{a}=a,\overline{b}=b\) ואילו \(e^{i\theta}\) יכול להיות רק 1 או \(-1\). לכן נקבל שיש בדיוק שני סוגים של מטריצות אוניטריות ממשיות:

\(\left[\begin{array}{cc}a & b\\-b & a\end{array}\right]\)

או

\(\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\)

בשני המקרים חייב להתקיים \(a^{2}+b^{2}=1\).

עכשיו, כל מטריצה כזו מגדירה אופרטור לינארי על \(\mathbb{R}^{2}\). מה האופרטורים הללו עושים? ראשית כל, השוויון הנחמד \(a^{2}+b^{2}=1\) מזכיר לי את הזהות המתמטית \(\sin^{2}\theta+\cos^{2}\theta=1\), אז בואו נסמן \(a=\cos\theta\) ו-\(b=-\sin\theta\) (שימו לב שצריך להוכיח שזה אפשרי – אשאיר זאת לכם). אז מטריצה מהסוג הראשון היא מהצורה

\(\left[\begin{array}{cc}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{array}\right]\)

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

\(\left[\begin{array}{cc}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{array}\right]\left[\begin{array}{c}1\\0\end{array}\right]=\left[\begin{array}{c}\cos\theta\\\sin\theta\end{array}\right]\)

\(\left[\begin{array}{cc}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{array}\right]\left[\begin{array}{c}0\\1\end{array}\right]=\left[\begin{array}{c}-\sin\theta\\\cos\theta\end{array}\right]\)

אני מתעצל לצייר את זה, אבל ציירו! השוויון הראשון אומר שהוקטור האופקי שפונה "ימינה" (לצד החיובי של ציר \(x\)) עובר לוקטור שיוצר זווית של \(\theta\) מעל הכיוון החיובי של ציר \(x\). הוקטור שפונה "למעלה" עובר לוקטור שיוצר זווית \(\theta\) משמאל לכיוון החיובי של ציר \(y\), ובסך הכל המטריצה מסובבת את שני הוקטורים הללו בזווית \(\theta\) נגד כיוון השעון. מכיוון שהיא עושה זאת לוקטורים של בסיס כלשהו למרחב, זה מה שהיא עושה לכל וקטור – זוהי מטריצת סיבוב בזווית \(\theta\) (ובחרתי את \(a\) להיות \(\cos\theta\) ואת \(b\) להיות \(-\sin\theta\) כדי לקבל סיבוב במובן שאנחנו רגילים אליו – אם הייתי בוחר, למשל \(a=\sin\theta\) ו-\(b=\cos\theta\) עדיין הייתי מקבל סיבוב, אבל חשבו מה תהיה הזווית ומה יהיה הכיוון של הסיבוב).

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

\(\left[\begin{array}{cc}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{array}\right]\left[\begin{array}{c}r\cos t\\r\sin t\end{array}\right]=\left[\begin{array}{c}r\cos\theta\cos t-r\sin\theta\sin t\\r\sin\theta\cos t+r\sin t\cos\theta\end{array}\right]=\left[\begin{array}{c}r\cos\left(t+\theta\right)\\r\sin\left(t+\theta\right)\end{array}\right]\)

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

אם כן, הבנו מה עושה כל מטריצה אוניטרית מהצורה \(\left[\begin{array}{cc}a & b\\-b & a\end{array}\right]\). מה עם מטריצות מהצורה השניה? יש כמה דרכים להבין מה הן עושות, אבל בואו נתחיל מדרך שבה כדאי לנקוט תמיד עם מטריצות לא ברורות – ננסה ללכסן. המטריצה שלנו, כזכור, היא מהצורה

\(\left[\begin{array}{cc}a & b\\b & -a\end{array}\right]\)

כאשר \(a^{2}+b^{2}=1\). הפולינום האופייני, אם כן, הוא

\(\left(a-x\right)\left(-a-x\right)-b^{2}=x^{2}-a^{2}-b^{2}=x^{2}-1\)

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

\(\left[\begin{array}{cc}a-1 & b\\b & -a-1\end{array}\right]\left[\begin{array}{c}x\\y\end{array}\right]=\left[\begin{array}{c}0\\0\end{array}\right]\)

נניח ש-\(b\ne0\) ונפתור אותה עם דירוג סטנדרטי, תוך שימוש בכך ש-\(a^{2}+b^{2}=1\):

\(\left[\begin{array}{cc}a-1 & b\\b & -a-1\end{array}\right]\to\left[\begin{array}{cc}-1 & b+\frac{a\left(a+1\right)}{b}\\b & -a-1\end{array}\right]\to\left[\begin{array}{cc}1 & -\frac{1+a}{b}\\b & -\left(1+a\right)\end{array}\right]\to\left[\begin{array}{cc}1 & -\frac{1+a}{b}\\0 & 0\end{array}\right]\)

מכאן נקבל שכל פתרון של המשוואה הוא מהצורה \(\left(\frac{1+a}{b}t,t\right)\). אם נבחר, לצורך נוחות, \(t=b\) נקבל את היוצר \(\left(1+a,b\right)\). בדקו ישירות כדי לראות שהוא אכן וקטור עצמי!

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

\(\frac{1}{x^{2}+y^{2}}\left[\begin{array}{cc}x^{2}-y^{2} & 2xy\\2xy & y^{2}-x^{2}\end{array}\right]\)

ומה שראינו עכשיו הוא שאם \(\left(x-1\right)^{2}+y^{2}=1\) אז המטריצה שמתקבלת היא מהצורה

\(\left[\begin{array}{cc}x-1 & y\\y & 1-x\end{array}\right]\)

שהיא נחמדה יותר, אבל לא תמיד \(\left(x-1\right)^{2}+y^{2}=1\) ולא פשוט למצוא \(\left(x,y\right)\) שמקיימים את זה אם נתון לנו הישר שאנו רוצים לשקף דרכו.

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

\(\left[\begin{array}{cc}\cos\theta & \sin\theta\\\sin\theta & -\cos\theta\end{array}\right]\left[\begin{array}{c}r\cos t\\r\sin t\end{array}\right]=\left[\begin{array}{c}r\cos\theta\cos t+r\sin\theta\sin t\\r\sin\theta\cos t-r\sin t\cos\theta\end{array}\right]=\left[\begin{array}{c}r\cos\left(\theta-t\right)\\r\sin\left(\theta-t\right)\end{array}\right]\)

זה מזכיר סיבוב, אבל זה לא סיבוב בגלל שהזווית של הוקטור המקורי, \(t\), הפכה למינוס \(t\). קצת חשבון מראה שעבור \(t=\frac{\theta}{2}\) נקבל נקודות שבת של האופרטור, ולכן הפעולה שהאופרטור מבצע היא שיקוף ביחס לציר שהזווית שלו עם הכיוון החיובי של ציר \(x\) היא \(\frac{\theta}{2}\).

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

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

טרנספורמציות אוניטריות

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

בואו ניזכר מה זו בכלל טרנספורמציה לינארית. אם יש לנו שני מרחבים וקטוריים \(V,W\) אז טרנספורמציה לינארית היא פונקציה \(T:V\to W\) שמשמרת את המבנה של המרחבים הלינאריים. מבנה של מרחב לינארי מתבטא בפעולות חשבוניות שמוגדרות עליו – חיבור של שני איברים, וכפל בסקלר של איבר. \(T\left(v+u\right)=T\left(v\right)+T\left(u\right)\) פירושו שבהינתן שני וקטורים \(v,u\) זה לא משנה אם קודם נחבר אותם ואז נפעיל עליהם את \(T\) או אם קודם נפעיל עליהם את \(T\) ואז נחבר אותם – בכל מקרה נקבל את אותה התוצאה בסוף (את הרעיון הזה מתארים לפעמים בעזרת דיאגרמה קומוטטיבית והוא חזק למדי, אבל אלו דברים שיחכו לפוסט אחר). אותו הדבר עם כפל בסקלר: \(T\left(\lambda v\right)=\lambda T\left(v\right)\) פירושו שלא משנה אם קודם נכפול את \(v\) בסקלר \(\lambda\) ואז נפעיל עליו את \(T\) או שקודם נפעיל עליו את \(T\) ואז נכפול ב-\(\lambda\) – בכל מקרה נקבל את אותה התוצאה.

עכשיו, מהו מרחב מכפלה פנימית? הוא מרחב וקטורי שהוספנו לו עוד מבנה, שמתבטא בפונקציה של מכפלה פנימית, שהיא פונקציה שמקבלת שני וקטורים ומחזירה סקלר, \(\left\langle v,u\right\rangle :V\times V\to\mathbb{C}\). אם נמשיך את קו המחשבה של שתי הדוגמאות הקודמות, אנחנו רואים שמחלקה מעניינת של טרנספורמציות לינאריות תהיה המחלקה של הטרנספורמציות שמשמרות את המכפלה הפנימית. כלומר, אם \(V,W\) הם שני מרחבי מכפלה פנימית ו-\(T:V\to W\), מעניין אותנו אם אפשר קודם להפעיל את \(T\) על זוג וקטורים ואז לכפול אותם, או קודם לכפול אותם ואז להפעיל עליהם את \(T\)… רגע, רגע, רגע, משהו לא מסתדר פה!

הנקודה שצריך לתת עליה את הדעת היא שמכפלה פנימית "מוציאה" אותנו מהמרחב \(V\). בניגוד לחיבור, שקיבל זוג וקטורים ב-\(V\) והחזיר וקטור ב-\(V\), מכפלה פנימית מעבירה אותנו מ-\(V\) אל \(\mathbb{C}\) ולכן כל עניין ה"התחלפות" שתיארתי לא עובד. עדיין, זו אינטואיציה טובה לדרישה שאני כן הולך לדרוש: שהמכפלה הפנימית של זוג וקטורים לא תשתנה אם נפעיל עליהם את \(T\), ובאופן פורמלי, \(\left\langle v,u\right\rangle =\left\langle T\left(v\right),T\left(u\right)\right\rangle \). שימו לב שהמכפלה הפנימית באגף שמאל היא המכפלה הפנימית של \(V\) ואילו זו באגף ימין היא המכפלה הפנימית של \(W\). לטרנספורמציה לינארית שמקיימת את התכונה הזו אקרא אוניטרית. דוגמאות מיידיות לטרנספורמציות כאלו הן גאומטריות באופיין: חשבו על \(\mathbb{R}^{2}\) עם המכפלה הפנימית הרגילה ועל הפעולות של סיבוב בזווית כלשהי סביב הראשית או של שיקוף ביחס לציר העובר דרך הראשית. אינטואיטיבית ברור למדי שאם מסובבים שני וקטורים באותה זווית גם האורכים שלהם והזווית ביניהם נשמרת, וב-\(\mathbb{R}^{2}\) עם המכפלה הפנימית הרגילה, המכפלה הפנימית של זוג וקטורים היא מכפלת האורכים שלהם בקוסינוס הזווית ביניהם, כך שברור שהיא תשתמר. יש עוד הרבה דוגמאות אך לא אציג אותן כרגע. תחת זאת, בואו ננסה להבין אילו עוד תכונות טרנספורמציות אוניטריות מקיימות.

ראשית כל, מכפלה פנימית הייתה קשורה בקשר הדוק לפונקציה דומה שנקראה נורמה: \(\|v\|=\left\langle v,v\right\rangle \). בבירור אם \(T\) אוניטרית אז \(\|T\left(v\right)\|=\left\langle T\left(v\right),T\left(v\right)\right\rangle =\left\langle v,v\right\rangle =\|v\|\), כלומר \(T\) משמרת גם את הנורמה של איברים (פורמלית: את הנורמה הספציפית שמושרית על המרחבים מהמכפלה הפנימית שביחס אליהם \(T\) אוניטרית). גם ההפך נכון – אם \(T\) משמרת נורמה, אז היא אוניטרית; זה נובע מכך שאם נורמה מושרית ממכפלה פנימית כלשהי, אז אפשר לכתוב את המכפלה הפנימית בתור נוסחה כלשהי שמערבת את הנורמה – זהות הפולריזציה שהראיתי בפוסט קודם. מכאן שכדי להראות שטרנספורמציה היא אוניטרית יספיק לי לפעמים להראות שהיא משמרת נורמה.

עכשיו קופץ משהו אחר לעיניים: כזכור, \(\|v\|=0\) אם ורק אם \(v=0\) (וקטור האפס), ולכן אם \(T\left(v\right)=0\) עבור \(v\) כלשהו, הרי ש-\(\|v\|=\|T\left(v\right)\|=\|0\|=0\) ומכאן נובע שגם \(v=0\). במילים אחרות, \(T\) מעבירה לוקטור האפס רק את וקטור האפס; מכך נובע ש-\(T\) הפיכה ("לא סינגולרית"). אם כן, כל טרנספורמציה אוניטרית היא גם הפיכה; אם \(T:V\to W\) היא אוניטרית ו-\(V,W\) הם מאותו מימד סופי (כרגיל, מכאן ואילך נדבר רק על מרחבים ממימד סופי) אז נובע מכך ש-\(T\) היא איזומורפיזם של \(V,W\) שגם משמרת את המכפלה הפנימית שלהם. בלשון פחות פורמלית זה אומר ש-\(V,W\) "הם אותו מרחב עד כדי שינוי שמות האיברים" וש-\(T\) היא בדיוק מה שמבצע את השינוי של שמות האיברים הללו.

דבר אחד שהוכחנו בעבר הוא שאם \(V\) הוא מרחב מכפלה פנימית ממימד סופי, אז קיים לו בסיס אורתונורמלי \(\left\{ b_{1},\dots,b_{n}\right\} \). עכשיו, אם \(W\) הוא מרחב מאותו מימד כמו \(V\), מה נקבל כשנפעיל טרנספורמציה אוניטרית \(T:V\to W\) על אברי הבסיס? נקבל קבוצה \(\left\{ T\left(b_{1}\right),\dots,T\left(b_{n}\right)\right\} \) שהיא בבירור בסיס ל-\(W\) כי היא קבוצה בלתי תלויה לינארית ב-\(W\) עם מספר וקטורים ששווה למימד של \(W\) (למה היא בלתי תלויה? כי \(T\) הפיכה – נסו להוכיח!). כפי שאתם ודאי מנחשים, הבסיס שקיבלנו לא יהיה "סתם" בסיס, אלא בסיס אורתונורמלי, ובכך צצה לה תכונה נוספת של טרנספורמציות אוניטריות: הן מעבירות בסיסים אורתונורמליים לבסיסים אורתונורמליים.

העובדה שהבסיס החדש אורתונורמלי די מיידית. בסיס הוא אורתונורמלי אם לכל זוג איברים בו מתקיים \(\left\langle b_{i},b_{j}\right\rangle =\delta_{ij}\) (כאשר \(\delta_{ij}=\begin{cases}1 & i=j\\0 & i\ne j\end{cases}\) נקראת הדלתא של קרונקר), ובבירור \(\left\langle T\left(b_{i}\right),T\left(b_{j}\right)\right\rangle =\left\langle b_{i},b_{j}\right\rangle =\delta_{ij}\) כי \(T\) אוניטרית וה-\(b\)-ים שייכים לבסיס אורתונורמלי. מה שיותר מעניין הוא שהטענה הזו עובדת גם בכיוון השני, ואפילו בגרסה יותר חזקה: אם \(T:V\to W\) היא טרנספורמציה לינארית כלשהי כך שקיים בסיס אורתונורמלי אחד \(\left\{ b_{1},\dots,b_{n}\right\} \) של \(V\) בעל התכונה ש-\(\left\{ T\left(b_{1}\right),\dots,T\left(b_{n}\right)\right\} \) הוא בסיס אורתונורמלי של \(T\), אז \(T\) אוניטרית. ההוכחה, כרגיל במרחבי מכפלה פנימית, תעבור דרך העובדה שאנו בדיוק איך להציג כל איבר במרחב כצירוף לינארי של איברי הבסיס האורתונורמלי: אם \(v\in V\) אז \(v=\sum\left\langle v,b_{i}\right\rangle b_{i}\). זה גם מאפשר לנו לדעת איך \(T\left(v\right)\) ייראה: \(T\left(v\right)=\sum\left\langle v,b_{i}\right\rangle T\left(b_{i}\right)\).

בואו ניקח שני וקטורים \(v,u\in V\). אנו רוצים להראות ש-\(\left\langle v,u\right\rangle =\left\langle T\left(v\right),T\left(u\right)\right\rangle \). את החישוב של \(\left\langle v,u\right\rangle \) כבר עשיתי בפוסט קודם: מקבלים \(\left\langle v,u\right\rangle =\sum\left\langle v,b_{i}\right\rangle \overline{\left\langle u,b_{i}\right\rangle }\). עכשיו, אם נציב ב-\(\left\langle T\left(v\right),T\left(u\right)\right\rangle \) את הביטוי ל-\(T\left(v\right)\) ו-\(T\left(u\right)\) שמצאנו קודם, נקבל:

\(\left\langle T\left(v\right),T\left(u\right)\right\rangle =\left\langle \sum_{i}\left\langle v,b_{i}\right\rangle T\left(b_{i}\right),\sum_{j}\left\langle u,b_{j}\right\rangle T\left(b_{j}\right)\right\rangle =\sum_{i,j}\left\langle v,b_{i}\right\rangle \overline{\left\langle u,b_{j}\right\rangle }\left\langle T\left(b_{i}\right),T\left(b_{j}\right)\right\rangle \)

\(=\sum_{i,j}\left\langle v,b_{i}\right\rangle \overline{\left\langle u,b_{j}\right\rangle }\delta_{ij}=\sum_{i}\left\langle v,b_{i}\right\rangle \overline{\left\langle u,b_{i}\right\rangle }=\left\langle v,u\right\rangle \)

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

הבנו איך טרנספורמציה אוניטרית מתנהגת "ברמת הוקטורים". עכשיו בואו ננסה להבין מה המבנה של אוסף כל הטרנספורמציות האוניטריות. נניח ש-\(T,S\) הן שתי טרנספורמציות אוניטריות, מה בדבר ההרכבה, \(TS\)? די בבירור גם היא אוניטרית, כי \(\|TS\left(v\right)\|=\|T\left(S\left(v\right)\right)\|=\|S\left(v\right)\|=\|v\|\). כמו כן, אם \(T\) היא אוניטרית ראינו שהיא הפיכה; אני טוען שגם \(T^{-1}\) אוניטרית, כי \(\|T^{-1}\left(v\right)\|=\|T\left(T^{-1}\left(v\right)\right)\|=\|v\|\) (למי שלא ברור לו מה הלך פה, סמנו \(u=T^{-1}\left(v\right)\) ושימו לב לכך ש-\(\|u\|=\|T\left(u\right)\|\) כי \(T\) אוניטרית).

- בואו ננסה עכשיו להבין אותה לאור מה שדיברנו עליו בפוסט הקודם על טרנספורמציות מעל מרחבי מכפלה פנימית – פעולת ההצמדה. כזכור, אם \(T:V\to V\) הייתה אופרטור לינארי (המילה "אופרטור" כאן באה לתאר טרנספורמציות ממרחב כלשהו אל עצמו, להבדיל מ"סתם" טרנספורמציה שיכולה להיות בין שני מרחבים שונים), הוכחנו שקיים ויחיד אופרטור \(T^{*}\) – הצמוד של \(T\), כך שמתקיים \(\left\langle T\left(v\right),u\right\rangle =\left\langle v,T^{*}\left(u\right)\right\rangle \) לכל זוג וקטורים \(v,u\in V\). אם \(T\) אוניטרית, האם יש לצמוד עוד תכונות מעניינות?

ובכן, זכרו שכבר ראינו כי \(T\) הפיך, כלומר קיים אופרטור שהוא בעצמו אוניטרי \(T^{-1}\) כך ש-\(TT^{-1}=T^{-1}T=I\). אני טוען שההופכי הוא גם הצמוד של \(T\); בואו ונראה למה:

\(\left\langle T\left(v\right),u\right\rangle =\left\langle T^{-1}T\left(v\right),T^{-1}\left(u\right)\right\rangle =\left\langle v,T^{-1}\left(u\right)\right\rangle \)

זה היה פשוט, לא? (איפה השתמשתי בכך ש-\(T^{-1}\) אוניטרי?)

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

המשחק נים – הגרסה האינטראקטיבית!

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

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

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

בהצלחה!

הפנטגרמה והפיתגוראים

על מה אתם חושבים כשאתם רואים את הסמל הבא?

Pentagram1

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

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

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

ראשית כל יש להבין כיצד פנטגרמה נוצרת. אנחנו מתחילים מצורה פשוטה יותר – מחומש משוכלל:

Pentagram2

הרעיון במחומש משוכלל הוא שזהו מצולע בעל 5 צלעות שוות באורכן, שכל הזוויות בו שוות.

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

Basis

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

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

Pentagram3

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

Pentagram4

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

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

Pentagram5

זה בבירור משולש שווה שוקיים, שאורך כל שוק בו הוא אורך צלע הפנטגרמה – בואו נסמן אותה ב-\(A\), ואורך הבסיס שלו הוא אורך צלע המחומש – בואו נסמן אותה ב-\(B\). בכל מחומש-עם-פנטגרמה שנצייר, היחס \(\frac{A}{B}\) בין אורך צלע הפנטגרמה ואורך צלע המחומש יהיה זהה (זה נובע מדמיון משולשים על המשולש שציירתי למעלה). כעת יש שתי שאלות: מהו היחס הזה, והאם הוא מספר רציונלי? לשאלה מהו היחס הזה אחזור בסוף הפוסט; כרגע אני רוצה לשכנע אתכם שהוא מספר אי רציונלי, כלומר שלא ניתן לתאר אותו על ידי מנה של שני מספרים שלמים.

הצעד הראשון הוא לשים לב לאבחנה הפשוטה הבאה: הטענה שהיחס \(\frac{A}{B}\) הוא רציונלי שקולה לטענה שאפשר לצייר מחומש-עם-פנטגרמה באופן כזה שגם אורך צלע הפנטגרמה וגם אורך צלע המחומש שניהם מספרים טבעיים. כיוון אחד הוא ברור – אם נצליח לצייר מחומש-עם-פנטגרמה שכזה, אז \(A\) יהיה מספר טבעי וגם \(B\) יהיה מספר טבעי ולכן \(\frac{A}{B}\) יהיה מספר רציונלי. הכיוון השני פחות מיידי: אם \(\frac{A}{B}\) הוא רציונלי זה לא אומר ש-\(A,B\) הם שלמים בהכרח – הביטו למשל על \(\frac{1/4}{1/2}\) (רבע חלקי חצי) ששווה למספר הרציונלי \(\frac{1}{2}\). מה שנכון הוא שאם היחס הוא מספר רציונלי, למשל \(\frac{t}{s}\) עם \(t,s\) שלמים, אז אפשר לצייר מחומש-עם-פנטגרמה כך שאורך צלעו של המחומש היא \(s\) ואורך צלעה של הפנטגרמה הוא \(t\) ולקבל מחומש-עם-פנטגרמה שאורכי צלעותיהם הם טבעיים.

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

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

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

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

Pentagram6

בגלל הסימטריה של המחומש אנחנו יודעים שכל המשולשים זהים, ושהם כולם שווי שוקיים, ולכן גם זוויות הבסיס שלהם שוות. מהי זווית הראש? סכום זוויות הראש של כל המשולשים יחד מרכיב מעגל שלם, כלומר 360 מעלות, ולכן זווית הראש היא בת \(\frac{360}{5}=72\) מעלות. זה מותיר לשתי זוויות הבסיס \(180-72=108\) מעלות, ולכן כל זווית בסיס שכזו היא בת \(54\) מעלות. כעת, כל זווית במחומש היא סכום של שתי זוויות בסיס ולכן הזווית במחומש היא 108 מעלות.

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

Pentagram7

אז יש לנו את המשוואה \(2\alpha+\beta=108^{\circ}\). זה לכשעצמו לא מספיק כדי לדעת מהם \(\alpha,\beta\), אבל אפשר למצוא עוד משוואה אם מסתכלים על המשולש:

Pentagram8

זווית הראש במשולש היא \(\beta\), ואילו שתי זוויות הבסיס הן \(\alpha+\beta\). לכן נקבל את המשוואה \(\beta+2\left(\alpha+\beta\right)=180^{\circ}\), כלומר \(2\alpha+3\beta=180^{\circ}\). קיבלנו שתי משוואות בשתי נעלמים, ואת זה קל לפתור – מחסרים את המשוואה הראשונה מהשניה ומקבלים \(2\beta=72^{\circ}\), כלומר \(\beta=36^{\circ}\), ולכן גם \(\alpha=36^{\circ}\). כלומר, הפנטגרמה מחלקת את הזוויות של המחומש לשלושה חלקים שווים שכל אחד מהם הוא \(36^{\circ}\). הסימטריה המושלמת הזו היא המפתח להמשך.

עכשיו, בואו נסתכל לרגע על צלע הפנטגרמה:

Pentagram9

שימו לב לכך שהיא מחולקת לשלושה חלקים. אורך החלק האמצעי הוא בדיוק \(b\) – אורך צלע המחומש הקטן. מה אורך שני החלקים האחרים? מסימטריה ברור שהוא שווה; נסמן אותו \(x\). קיבלנו את המשוואה \(A=b+2x\). כמו קודם, משוואה אחת לא מספיקה לנו, אז בואו נביט במשולש הבא:

Pentagram10

זה נראה כמו משולש שווה שוקיים, ואכן, די קל להשתכנע ששתי זווית הבסיס הן בנות 72 מעלות, בעזרת מה שכבר ראינו על הזוויות במחומש-פנטגרמה (הוכיחו זאת לעצמכם!). אחת השוקיים היא באורך \(B\) ואילו השניה היא באורך \(b+x\), כך שקיבלנו את המשוואה \(B=b+x\). נכפול את המשוואה הזו ב-2 ונחסר ממנה את הראשונה, ונקבל \(b=2B-A\), כפי שהבטחתי למעלה.

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

Pentagram11

בציור הזה אנחנו רואים עוד משולש שווה שוקיים, שבו השוקיים הן בדיוק צלע הפנטגרמה הקטנה, והחלק של צלע הפנטגרמה הגדולה שסימנתי בתור \(x\). זוויות הבסיס של המשולש הן בנות 36 מעלות – שוב, זה נובע ממה שכבר ראינו עליהן – ולכן זה אכן משולש שווה שוקיים. המסקנה: \(A=2a+b\), אבל אנחנו כבר יודעים מהו \(b\) במונחים של \(A,B\): \(b=2B-A\). נציב ונקבל: \(2a+2B-A=A\), כלומר \(2a=2A-2B\), כלומר \(a=A-B\) – שוב, כמו שהבטחתי. זה מסיים את ההוכחה.

עכשיו אפשר לחזור לשאלה הנוספת. אנחנו יודעים ש-\(\frac{A}{B}\) הוא מספר אי רציונלי, אבל איזה מספר אי רציונלי? לשם כך אנסה למצוא דרך לחשב, אלגברית, את הערך של \(\frac{A}{B}\). אנחנו יודעים מדמיון משולשים שמתקיים \(\frac{A}{B}=\frac{a}{b}\) ואנחנו יודעים לבטא את \(a,b\) בעזרת \(A,B\) – זו נראית כמו נקודת פתיחה טובה. אם כן, נציב:

\(\frac{A}{B}=\frac{A-B}{2B-A}\)

עכשיו אשתמש בתעלול. באגף ימין \(A\) ו-\(B\) מופיעים לבדם וזה לא טוב לי, כי מי שמעניין אותי הוא היחס \(\frac{A}{B}\). לכן אחלק הן את המונה והן את המכנה של אגף ימין ב-\(B\), ואקבל:

\(\frac{A}{B}=\frac{\frac{A}{B}-1}{2-\frac{A}{B}}\)

כעת אסמן \(x=\frac{A}{B}\) ובואו ונראה איזו משוואה קיבלתי:

\(x=\frac{x-1}{2-x}\)

נכפול את שני האגפים ב-\(2-x\) ונקבל:

\(2x-x^{2}=x-1\)

נעביר אגפים:

\(x^{2}-x-1=0\)

למשוואה הזו יש שני פתרונות אלגבריים:

\(x_{1,2}=\frac{1\pm\sqrt{5}}{2}\)

פתרון אחד הוא שלילי ולכן חסר משמעות בשבילנו – בהכרח הפתרון האחר הוא היחס הנכון, \(\frac{1+\sqrt{5}}{2}\). זה מספר מפורסם מאוד – הוא נקרא יחס הזהב ועיקר פרסומו מגיע לו מכך שהוא צץ, לכאורה, בכל מני מקומות בטבע, באדריכלות, באסתטיקה ועוד כהנה וכהנה. התחושה שלי היא שבלא מעט מקרים שבהם "מוצאים" את יחס הזהב במקום כלשהו יש מידה לא קטנה של אילוץ ומשחק עם פרמטרים כדי שיתאימו; עם זאת, בפנטגרמה הוא מופיע באופן הכי טבעי שרק אפשר, ובתפקיד מרכזי. כמובן, אם הייתי יודע שהיחס שאני מחפש הוא יחס הזהב הייתי יכול לוותר על ההוכחה הגיאומטרית ולהסתפק בציון העובדה שהוא אי רציונלי (למשל, כי \(\sqrt{5}\) אי רציונלי), אבל שימו לב לכך שכדי לגלות שהיחס הוא יחס הזהב היה עלי לחשב אלגברית את \(a,b\) ובשלב הזה ההוכחה שלי ממילא נסתיימה. פרט לכך, אין מה לעשות – ההוכחה הגיאומטרית פשוט מגניבה יותר.

נוסחת טאפר – הנוסחה שמציירת את עצמה

בואו ניגש ללב העניין. התבוננו בנוסחה הבאה:

\(\frac{1}{2}<\left\lfloor \mbox{mod}\left(\left\lfloor \frac{y}{17}\right\rfloor 2^{-17\left\lfloor x\right\rfloor -\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)},2\right)\right\rfloor \)

בלי פאניקה! הכל יוסבר.

ראשית, סימנים: \(\left\lfloor a\right\rfloor \) מסמל את הערך השלם התחתון של המספר \(a\), שמוגדר להיות המספר השלם הגדול ביותר שקטן או שווה ל-\(a\). למשל, \(\left\lfloor \frac{5}{3}\right\rfloor =1\) ואילו \(\left\lfloor 2\right\rfloor =2\). בנוסף, \(\mbox{mod}\left(a,n\right)\) מסמל את הערך שמתקבל כאשר לוקחים את המספר \(a\), מחלקים אותו ב-\(n\) ולוקחים את השארית. למשל, \(\mbox{mod}\left(3.3,2\right)=1.3\). זה הכל.

המשוואה הזו מכילה שני משתנים – \(x,y\). שניהם יכולים לקבל כל ערך שהוא מספר ממשי. עכשיו משחקים את המשחק הבא: מסתכלים על המישור \(\mathbb{R}^{2}\) שהוא אוסף כל הנקודות \(\left(x,y\right)\) שהן מספרים ממשיים. לכל נקודה \(\left(x,y\right)\) כזו, אם כאשר מציבים את \(x,y\) בנוסחה אי השוויון שבה אכן מתקיים, צובעים את הנקודה \(\left(x,y\right)\) בצבע שחור; אם השוויון לא מתקיים, מותירים את הנקודה לבנה. כעת, אם נסתכל על התמונה שנקבל נראה שקיבלנו תמונה אינסופית שבה המוני נקודות פזורות פה ושם וקשה להבין מה קורה, אבל אם נצטמצם לריבוע קטן יחסית – באורך 17 וברוחב 105 – ונלך למקום המתאים, נראה את התמונה הבאה:

tupper

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

טוב, לא בדיוק.

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

ובכן, התמונה מתרחשת בנקודות עם קואורדינטת \(x\) בין 0 ל-105, דהיינו \(0\le x\le105\), וקואורדינטת \(y\) בין \(k\) ל-\(k+16\), כלומר \(k\le y\le k+16\). מיהו \(k\)? ובכן, מספר גדול לאין שיעור, שמתואר כאן עם רווחים כדי שיהיה קריא ולא יחרוג מגבולות השורה:

960 939 379 918 958 884 971 672 962 127 852 754 715 004 339 660 129 306 651 505 519 271 702 802 395 266 424 689 642 842 174 350 718 121 267 153 782 770 623 355 993 237 280 874 144 307 891 325 963 941 337 723 487 857 735 749 823 926 629 715 517 173 716 995 165 232 890 538 221 612 403 238 855 866 184 013 235 585 136 048 828 693 337 902 491 454 229 288 667 081 096 184 496 091 705 183 454 067 827 731 551 705 405 381 627 380 967 602 565 625 016 981 482 083 418 783 163 849 115 590 225 610 003 652 351 370 343 874 461 848 378 737 238 198 224 849 863 465 033 159 410 054 974 700 593 138 339 226 497 249 461 751 545 728 366 702 369 745 461 014 655 997 933 798 537 483 143 786 841 806 593 422 227 898 388 722 980 000 748 404 719

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

לפני התשובה, הנה לכם משחק אינטראקטיבי – הזינו פנימה ערך של \(k\) (אפשר עם רווחים) וקבלו את התמונה עבור \(0\le x\le105\) ו-\(k\le y\le k+16\):



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

485 848 307 199 443 192 292 484 775 523 195 446 750 165 771 267 770 474 169 193 207 700 51 005 067 907 907 541 020 178 059 194 196 266 956 625 065 918 178 608 930 545 615 357 634 623 847 182 313 037 176 237 950 246 743 833 022 219 851 353 244 464 297 196 422 052 599 618 366 926 759 595 937 669 170 337 031 986 392 318 882 323 798 450 346 890 393 645 210 909 095 498 636 458 859 695 483 157 512 356 430 020 530 323 399 745 167 547 408 250 078 493 473 637 808 923 733 333 196 160 087 525 223 963 972 079 179 702 470 428 441 062 803 798 996 831 022 016 431 226 755 561 007 151 709 067 404 979 608 249 899 531 206 486 163 294 240 248 539 016 274 762 746 088 450 590 994 298 169 153 574 985 192 777 454 048 087 559 586 719 989 59

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

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

\(\left\lfloor \mbox{mod}\left(\left\lfloor \frac{y}{17}\right\rfloor 2^{-17\left\lfloor x\right\rfloor -\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)},2\right)\right\rfloor \)

נתחיל עם \(\left\lfloor \frac{y}{17}\right\rfloor \). בהנחה ש-\(k\) מתחלק ב-17 (והוא מתחלק – בדקו זאת!) הרי שלכל ערך \(k\le y\le k+16\) נקבל ש-\(\left\lfloor \frac{y}{17}\right\rfloor =\frac{k}{17}\) (הסבירו לעצמכם למה). כלומר, ה-\(\left\lfloor \frac{y}{17}\right\rfloor \) הוא פשוט דרך מחוכמת להכניס את \(k\) לנוסחה בלי לכתוב אותו במפורש; ולמעשה, לא \(k\) הוא מה שמקודד את התמונה אלא \(\frac{k}{17}\) (מבחינה פילוסופית אפשר לטעון ששני המספרים הללו מקודדים את התמונה, אבל תכף נראה שיותר נכון לומר זאת על \(\frac{k}{17}\)). כדי לפשט לעצמי את החיים אסמן מעתה \(a=\frac{k}{17}\).

עכשיו אנחנו כופלים את \(a\) ב-2 בחזקת מינוס משהו מפלצתי. עזבו לבינתיים את המשהו המפלצתי – נסמן אותו ב-\(t\). מהו \(a2^{-t}\)? זה סימון אחר ל-\(\frac{a}{2^{t}}\), כלומר אנחנו מחלקים את \(a\) בחזקה גדולה של 2. הדבר הזה שקול להזזה של הספרות של \(a\) בייצוג בינארי, או בנקודת מבט אחרת – הזזה של מיקום הנקודה העשרונית בייצוג בינארי של \(a\).

הרבה יותר קל להבין את זה אם חושבים על מספרים בבסיס 10 כפי שאנחנו רגילים. הביטו לרגע במספר \(a=531\). מספר חביב וטוב לב ואהוב על הבריות. כעת נתעלל בו ונחלק אותו ב-10, וזה כואב, כי הוא לא מתחלק ב-10. מה שנקבל הוא את המספר \(53.1\), שזה כמו \(513.\), רק אחרי שהנקודה זזה צעד אחד שמאלה. ואם נחלק ב-\(10^{2}\) כלומר ב-100 נקבל \(5.31\), כלומר הנקודה זזה שני צעדים שמאלה. באופן כללי אם מחלקים מספר ב-\(10^{t}\) , מה שיקרה הוא שהנקודה בייצוג העשרוני שלו תזוז \(t\) צעדים שמאלה. כעת, אם נחלק מספר ב-\(2^{t}\), הנקודה תזוז \(t\) צעדים שמאלה בייצוג של המספר בבסיס 2. כך למשל המספר 13 מיוצג בבסיס 2 בתור \(1101\) (כי \(13=1\cdot2^{0}+0\cdot2^{1}+1\cdot2^{2}+1\cdot2^{3}\)). אם נחלק אותו ב-\(4=2^{2}\) נקבל את המספר "שלוש ורבע", שבבסיס בינארי הוא \(11.01\) (כי \(11\) בבינארי זה 3 ו-\(.01=0\cdot\frac{1}{2}+1\cdot\frac{1}{4}\)).

יפה, אם כן, הנוסחה מבצעת חישוב שאסמן את התוצאה שלו בתור \(b=a2^{-t}\), שבסך הכל לוקחת את \(a\) ומזיזה את הנקודה בייצוג הבינארי שלו \(t\) צעדים שמאלה. אז מבצעים את החישוב הבא: \(\left\lfloor \mbox{mod}\left(b,2\right)\right\rfloor \). כלומר, גם לוקחים את \(b\) מודולו 2, וגם לוקחים ערך שלם תחתון. גם על שתי הפעולות הללו כדאי לחשוב במונחים של הייצוג הבינארי של המספר. ביצוע הפעולה \(\mbox{mod}\left(b,2\right)\) לוקח את \(b\) ופשוט זורק לזבל את כל הספרות שמשמאל לנקודה העשרונית, חוץ מאשר את הספרה הראשונה שמשמאל לה. כלומר, \(\mbox{mod}\left(101101.1101,2\right)=1.1101\). למה זה נכון? ובכן, את \(101101.1101\) אפשר לכתוב גם כסכום שני מספרים: \(101101.1101=101100+1.1101\). המספר השמאלי מתחלק ב-2 והמספר הימני קטן מ-2. זה מספיק כדי לראות את נכונות הטענה גם באופן כללי, אבל אשאיר לכם להשלים את הפרטים.

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

במילים אחרות, \(\left\lfloor \mbox{mod}\left(b,2\right)\right\rfloor \) לוקחת את המספר \(b\) ומחזירה ספרה בודדת מתוך \(b\) – בדיוק את זו שנמצאת מייד משמאל לנקודה העשרונית בייצוג של \(b\) בבסיס בינארי. מסקנה: \(\left\lfloor \mbox{mod}\left(a2^{-t},2\right)\right\rfloor \) היא פונקציה שלוקחת את \(a\) ומחזירה בדיוק את הספרה במקום ה-\(t\)-י בייצוג הבינארי של \(a\) (כשמתחילים את הספירה של המקומות מ-0). עד כדי כך פשוט.

כעת נותר רק להבין מהו \(t\). ובכן, \(t=17\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)\). בואו ננסה להבין את זה.

ראשית \(\left\lfloor x\right\rfloor \) ו-\(\left\lfloor y\right\rfloor \) פירושם שלמרות שהנוסחה יכולה לקבל ערכים ממשיים כלשהם של \(x,y\), היא מתעניינת רק בערכים השלמים שלהם; הנקודות \(\left(3.5,2.7\right)\) ו-\(\left(3,2\right)\) יהיו צבועות באותו הצבע, ולמעשה אם \(\left(3,2\right)\) צבועה בשחור, כך גם כל נקודה אחרת מהצורה \(\left(3.a,2.b\right)\) עבור מספרים כלשהם \(a,b\). נשאר רק להבין את \(17\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)\).

הנוסחה הזו בוודאי מוכרת לכל מי שקצת תכנת בחייו והתעסק עם מערכים דו ממדיים. בקצרה, מערך הוא אוסף תאי זכרון רצופים במחשב, שלכל אחד יש אינדקס (שמתחיל במקרה שלנו מ-0). אם \(A\) הוא מערך, אז \(A\left[4\right]\) מסמן את התא החמישי במערך (מתחילים מאפס!) וכן הלאה. כעת, מערך דו ממדי הוא מערך שבו לכל תא יש שתי קואורדינטות, למשל \(A\left[3\right]\left[5\right]\) מסמן את התא בעמודה מס' 3 ושורה מס' 5 (למתמטיקאים שביניכם, זו פשוט מטריצה בעוד שמערך הוא וקטור, אם כי במטריצות נהוג לתת את אינדקס השורה קודם וכאן עשיתי ההפך כדי להתאים לנוסחה של טאפר).

כעת, מערכים דו ממדיים מאוחסנים בזכרון של המחשב בתור מערכים רגילים, חד ממדיים; כאשר התוכנית נתקלת בגישה למערך מהצורה \(A\left[3\right]\left[4\right]\) היא מתרגמת את הפניה הזו לכתובת במערך החד ממדי המקורי. איך עושים את זה? ובכן, הרעיון הוא לאחסן את המערך הדו-ממדי "עמודה עמודה". נניח שאורך כל עמודה במערך הדו-ממדי היא \(6\), אז עמודה מס' 0 אוחסנה בתאי הזכרון 0-5; עמודה מס' 1 בתאי הזכרון 6-11; עמודה 2 ב-12-17, ועמודה 3 ב-18-23, כאשר תא מס' 4 בעמודה (כלומר, התא בשורה 4) הוא התא הרביעי מביניהם, דהיינו 22. כעת, את החישוב שעשינו אפשר לתאר בתור \(22=3\cdot6+4\), ובאופן כללי אם אורך כל עמודה במערך הוא \(s\) ואנחנו רוצים לגשת לתא \(A\left[x\right]\left[y\right]\), אז ניגש אל התא \(x\cdot s+y\).

נחזור אל \(t=17\left\lfloor x\right\rfloor +\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)\). כאן הנוסחה היא אותו הדבר: ספציפית, \(s=17\), כלומר במערך שלנו אורך כל עמודה הוא 17 (זהו גובה התמונה). כמו כן \(\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)\) בעצם בא לנטרל את \(k\) מתוך \(y\): הרי אמרנו ש-\(k\le y\le k+16\), כלומר אפשר לכתוב \(y=k+y^{\prime}\) כאשר \(0\le y^{\prime}\le16\); אז \(y^{\prime}=\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)\).

כעת הכל ברור – אני מקווה! מה שקורה הוא ש-\(a\) (שהוא, כזכור \(\frac{k}{17}\)) הוא מערך דו ממדי של ביטים שמקודד כמערך חד ממדי. ה"קידוד" הוא בדיוק הייצוג הבינארי של \(a\), ומה שנוסחת טאפר עושה הוא לדגום אותו ביט-ביט. הביטים שנוסחת טאפר קוראת יהיו 0 או 1, ולכן השוואה לחצי תצליח רק כשהביט הוא 1.

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

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

tupper_shachar

מה הקשר בין מספרים ראשוניים וקריפטוגרפיה?

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

מהו מספר ראשוני קל מאוד להגדיר: זה מספר טבעי גדול מ-1 שמתחלק רק ב-1 ובעצמו. למשל 2, או 17, או 131. לעומת זאת 57 אינו ראשוני כי הוא המכפלה של 3 ו-19. למה הראשוניים אמורים לעניין מישהו? ובכן, יש מספר סיבות. המיידית מביניהן היא שכל מספר טבעי גדול מ-1 ניתן להציג בתור מכפלה של ראשוניים באופן שהוא פחות או יותר יחיד. כך למשל את 57 אפשר לתאר בתור 3 כפול 19 או בתור 19 כפול 3, אבל פרט להיפוך הסדר הזה אין שום דבר שאפשר לעשות. כדי להבין מה מיוחד כאן כדאי לחשוב על מספר כמו 60, שאפשר להציג בתור 2 כפול 30 וגם בתור 4 כפול 15 – כלומר, שתי מכפלות שונות – אבל עדיין, הפירוק של 60 למכפלה של ראשוניים בלבד הוא יחיד (2 כפול 2 כפול 3 כפול 5). בשל התכונה הזו נהוג לומר על הראשוניים שהם "אבני הבניין" של כל המספרים הטבעיים. נראה בהמשך עוד תכונות של הראשוניים שהן מעניינות.

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

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

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

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

"כפל מודולו \(p\)" הוא דרך לתאר פעולת כפל רגילה של שני מספרים, שאחריה מחלקים את התוצאה ב-\(p\) ונשארים עם השארית. למשל, אם \(p\) הוא 17, אז 8 כפול 5 מודולו \(p\)יחזיר 6, שכן 8 כפול 5 הוא 40, וכשמחלקים ב-17 מקבלים מנה 2 ושארית 6. כפל מודולרי שכזה קל מאוד לממש במחשב, ויתרונו בכך שהוא נותן מבנה יפה לקבוצת המספרים מ-0 ועד \(p-1\), שאסמן מעתה ואילך ב-\(\mathbb{Z}_{p}\). מבחינה מתמטית המבנה הזה נקרא שדה, וזוהי דרך אחרת לומר שאפשר להגדיר עליהם פעולות של כפל וחיבור (גם חיבור מוגדר מודולו \(p\)) כך שכל כללי החשבון שאנחנו מכירים ואוהבים יתקיימו: כלל החילוף, כלל הקיבוץ וכלל הפילוג, ובנוסף לכך לכל איבר יהיה נגדי ביחס לחיבור (מספר שאם מחברים אותו למספר המקורי מקבלים 0; הנגדיים של המספרים הטבעיים ביחס לפעולת החיבור הרגילה הם המספרים השליליים) וחשוב מכל – לכל איבר יהיה הופכי ביחס לכפל, כלומר אפשר "לחלק". הנה דוגמה: אם אנחנו עובדים מודולו 17, אז כאשר כופלים את 5 ב-7 מקבלים 35, ואחרי חלוקה ב-17 ולקיחת שארית מקבלים 1. זה אומר ש-7 הוא ההופכי הכפלי של 5, ובמקום "לחלק ב-5" (פעולה שלא באמת מוגדרת עבור מספרים שלמים) אפשר לכפול ב-7.

עוד תכונה רלוונטית היא שלכל מספר ראשוני \(p\) קיים מספר \(g\) ששייך ל-\(\mathbb{Z}_{p}\) בעל התכונה שהחזקות \(g^{0},g^{1},\dots,g^{p-1}\), כשמסתכלים עליהן מודולו \(p\), הן בדיוק כל האיברים של \(\mathbb{Z}_{p}\) (למעט 0). מספר \(g\) כזה נקרא יוצר של \(\mathbb{Z}_{p}\).

עכשיו אפשר להסביר איך שיטת החלפת המפתחות של דיפי-הלמן עובדת: שני הצדדים, שאקרא להם אליס ובוב, מסכימים ביניהם על \(p\) ועל \(g\) מתאים עבורו (אין צורך לשמור אותם בסוד). אז אליס מגרילה לעצמה \(x\) ובוב מגריל לעצמו \(y\) ששניהם מספרים בין \(1\) ו-\(p-1\). עכשיו אליס מחשבת ושולחת לבוב את \(g^{x}\) ואילו בוב מחשב ושולח לאליס את \(g^{y}\). כעת כל אחד מעלה את המספר שהוא קיבל מהשני בחזקת המספר שהוא הגריל. למשל, אליס קיבלה את \(g^{y}\), אז היא תעלה את זה בחזקת \(x\), ומחוקי החזקות הרגילים, שמתקיימים גם עבור הכפל של \(\mathbb{Z}_{p}\) יתקיים \(\left(g^{y}\right)^{x}=g^{xy}\). באופן דומה החישוב של בוב יניב את \(\left(g^{x}\right)^{y}=g^{xy}\).

כך קרה שאליס ובוב מחזיקים כעת שניהם במספר משותף – \(g^{xy}\), אבל האם מישהו שציתת לתקשורת ביניהם יודע מהו? הוא יודע מהו \(g^{x}\) ומהו \(g^{y}\), אבל לא ברור איך לגלות מכך מהו \(g^{xy}\). על פניו, אפשר אולי לחשוב שאם התוקף יודע מהו \(g\) (זה הרי מידע פומבי) ויודע מהו \(g^{x}\) הוא יוכל לגלות מכך את \(x\), אבל זו בעיה קשה מבחינה חישובית, ואפילו יש לה שם – בעיית הלוגריתם הדיסקרטי. אפשר, כמובן, לנסות את כל הערכים האפשריים של \(x\) עד שמגיעים לאחד הנכון (להעלות את \(g\) בחזקה שלהם ולראות אם קיבלנו את \(g^{x}\)) ולכן חשוב שיהיו המון ערכים אפשריים של \(x\); כמו כן צריך להתגונן בפני שיטות חיפוש מחוכמות יותר (ויש כאלו) ולכן כדי שהשיטה של דיפי-הלמן תהיה בטוחה חייבים לעבוד עם מספר ראשוני \(p\) שהוא גדול יחסית – בן מאות ספרות (מספרים כמו 2048 ביטים או 4096 ביטים הם סדרי הגודל הנפוצים בימינו בדיבורים על ראשוניים בקריפטוגרפיה).

דיפי-הלמן ממחיש יפה איך ראשוניים עוזרים לנו בקריפטוגרפיה. לב-לבו של האלגוריתם הוא בכך שיש פונקציה שקל לחשב אבל קשה להפוך – העלאת \(g\) בחזקה, במקרה שלנו. התכונה היפה הזו קיימת ב-\(\mathbb{Z}_{p}\) אבל היא לחלוטין לא קיימת במספרים שלמים או ממשיים "רגילים". זו בדיוק הסיבה שהקריפטוגרפים נדחפו להשתמש במשהו כמו \(\mathbb{Z}_{p}\) – זה התגלה בתור "שדה משחק" מתאים לצרכים של הקריפטוגרפיה.

שנה אחרי דיפי והלמן התפרסם מאמר של ריבסט, שמיר ואדלמן (RSA) שהציג מערכת הצפנה פומבית של ממש. הרעיון של RSA היה שימוש בפונקציה מסוג שנקרא Trapdoor Function: פונקציה שקל לחשב ובאופן כללי קשה להפוך, אבל אם יש לך מידע (סודי) נוסף, היפוך שלה הופך לקל. באופן די מעניין, RSA עובד מעל \(\mathbb{Z}_{n}\) עבור \(n\) שאינו ראשוני, מה שאומר ש-\(n\) אינו שדה – לא תמיד אפשר לבצע בו חלוקה – אבל דווקא בגלל שהוא קצת "שבור" יש בו פונקציית מלכודת.

אם כן, הרעיון הוא כזה: נניח שאני רוצה להקים מערכת מפתח פומבי שבה כל העולם יוכל לשלוח לי דברים מוצפנים אבל רק אני אוכל לפענח. מה שאני עושה ראשית כל הוא למצוא שני מספרים ראשוניים גדולים \(p,q\). כעת אני כופל אותם ומקבל \(n=pq\). אחר כך אני מוצא זוג מספרים \(e,d\) בעלי התכונה ש-\(ed-1\) מתחלק ב-\(\left(p-1\right)\left(q-1\right)\). לא אסביר כעת את המתמטיקה המדויקת שמאחורי העניין, אך התכונה הזו של \(e,d\) מבטיחה שיתקיים הדבר הבא: \(\left(M^{e}\right)^{d}=M\), כאשר החשבון מבוצע מודולו \(n\).

כעת, אני מפרסם לעולם כולו את \(n\) ואת \(e\), אבל מותיר את \(d\) סודי. אם מישהו רוצה להצפין ולשלוח לי הודעה \(M\), הוא מחשב את \(M^{e}\) מודולו \(n\) ושולח לי. כדי לפענח, אני מעלה בחזקת \(d\) את מה שקיבלתי. פשוט להחריד. כאן פונקציית ה-Trapdoor היא פשוט העלאה בחזקת \(e\), וה"מידע נוסף" שהופך אותה לקלה להיפוך הוא \(d\).

כעת אנו מגיעים לנקודה שלדעתי גורמת לבלבול הגדול ביותר בקרב הטוקבקיסטים שציטטתי לעיל. כדי לבנות את מערכת ה-RSA, אחרי שמחליטים על \(n\) ועל \(e\) אפשר לחשב את \(d\) מתוך \(e\) ומתוך \(\left(p-1\right)\left(q-1\right)\). במילים אחרות, מי שמכיר את \(\left(p-1\right)\left(q-1\right)\) ואת \(e\) יכול לפרוץ את ההצפנה. קרוב לודאי שאתם מקבלים תחושה ש-RSA מאוד פגיעה בשל כך, אבל כדאי לזכור שב-RSA משתמשים כל הזמן, בכל מקום. אז למה זה עובד? כי גם אם יש לי את \(n=pq\), זה לא אומר שאני יכול לחשב מתוכו בקלות את \(\left(p-1\right)\left(q-1\right)\); הדרך הברורה לעשות זאת היא קודם כל לפרק את \(n\) לגורמים, כלומר למצוא את \(p,q\), אבל בעיית הפירוק לגורמים היא בעיה קשה. שימו לב: בעיית הפירוק לגורמים, לא בעיית בדיקת הראשוניות אלו שתי בעיות שונות, ובעיית הפירוק לגורמים מאז ומעולם נחשבה לקשה יותר.

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

התכונה נקראת "המשפט הקטן של פרמה" וקובעת שאם \(p\) הוא ראשוני ו-\(a\) הוא מספר כלשהו ב-\(\mathbb{Z}_{p}\), אז \(a^{p-1}=1\) (כשהחשבון הוא מודולו \(p\)). אם נתונים לנו \(p,a\) אז קל ומהיר למדי לבצע את החישוב של \(a^{p-1}\) (איך? זה עניין לפעם אחרת). אם נקבל משהו ששונה מ-\(1\), אז מובטח לנו ש-\(p\) לא היה ראשוני, למרות שאין לנו שום מחלק שלו. וזו רק תכונה אחת מני רבות. אנחנו מסתמכים כאן בצורה חזקה על כך שראשוניים הופכים מבנים מתמטיים ל"יפים", במובן זה שיש תכונות נחמדות מסויימות שמתקיימות בהם, ואם משהו משתבש לעתים קרובות קל לגלות זאת.

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

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

אפשר אולי עוד היה לקוות שגילוי הראשוני החדש יעיד על שיפור משמעותי ביכולת שלנו למצוא מספרים ראשוניים, אבל אפילו זה לא נכון. הראשוני הזה, כמו פחות או יותר כל הראשוניים הגדולים שהתגלו בעשורים האחרונים, הוא מצורה מאוד מיוחדת – \(2^{n}-1\) עבור ערך ספציפי של \(n\). ראשוני כזה נקרא ראשוני מרסן, וידועים בדיוק 48 כאלו – כמעט כלום. אם כן, איך קרה ה"מזל" הזה שהראשוני שנתגלה היה דווקא מהצורה הזו? כמובן שלא במקרה: יש אלגוריתם יעיל מאוד לבדיקה האם מספר מהצורה \(2^{n}-1\) הוא ראשוני או לא – יעיל משמעותית יותר מאלגוריתמים שמטפלים במספרים "כלליים", ולכן מוצלח יותר במציאת ראשוניים גדולים משמעותית מאלו שהשיטות הכלליות יודעות למצוא. אם כן, כדי למצוא "סתם" ראשוניים אקראים למערכת ההצפנה שלנו אין בכלל טעם להשתמש בו – אם אנחנו רוצים ראשוני שהוא מספר מרסן אנחנו פשוט יכולים לבחור מתוך הרשימה של הראשוניים הידועים, ואם חשוב לנו מספר אקראי, נצטרך להשתמש באלגוריתמים הרגילים.

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

לוגיקה מסדר ראשון – כמה תוצאות של משפט השלמות

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

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

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

בואו נדבר על אקסיומות פיאנו. לא יהיה לי צורך בכך ולכן אני לא באמת אציג אותן כאן במפורש – זה ראוי לפוסט נפרד – אבל אסביר בקצרה מהן. אקסיומות פיאנו הן נסיון למדל את המספרים הטבעיים – כלומר, לתת תורה מסדר ראשון (אוסף של אקסיומות) כך שהמספרים הטבעיים הם מודל שלהם. המילון של אקסיומות פיאנו כולל את סימן הקבוע \(0\) ואת סימן הפונקציה \(S\), שבפרשנות הסטנדרטית של האקסיומות (כלומר, זו שנמצאת לנו בראש כשאנו מגדירים את האקסיומות) תתפרש להיות פונקציית העוקב, כלומר \(S\left(n\right)=n+1\). כמו כן יש לנו את סימן היחס \(<\) שבפרשנות הסטנדרטית יתפרש להיות יחס הסדר הרגיל. יש גם סימני חיבור וכפל אבל לא נזדקק להם אז לא אציג אותם. גם לא אציג את האקסיומות עצמן במפורש – אשמור את זה לפוסט ייעודי עליהן.

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

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

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

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

כאן משפט הקומפקטיות נחלץ לעזרתנו. כדי להוכיח שלמערכת המורחבת יש מודל, מספיק להראות שלכל תת קבוצה סופית שלה יש מודל. תת קבוצה סופית שכזו כוללת פסוקים אלו ואחרים מתוך אקסיומות פיאנו שלא מעניינים אותנו, ובנוסף לכך היא כוללת מספר סופי של פסוקים מהצורה \(c>n\). בואו נסמן ב-\(N\) את הערך המקסימלי של \(n\) שמופיע באחד מהפסוקים הללו; עכשיו אני יכול לתת מודל לתת-הקבוצה הסופית. המודל הזה יהיה פשוט המספרים הטבעיים, \(\mathbb{N}\), עם הפרשנות הרגילה לסימן הקבוע 0 ולסימני הפונקציות והיחסים השונים; הדבר היחיד שאני צריך לומר במפורש הוא איך יפורש סימן הקבוע \(c\); אני פשוט אתאים לו את המספר הטבעי \(N+1\). מכיוון שהמספר הזה גדול מכל \(n\) שמקיים \(n\le N\), הרי שכל פסוק מהצורה \(c>n\) ששייך לתת-הקבוצה הסופית של הפסוקים שלנו אכן מתקיים במודל שהצעתי. קיבלתי שלכל תת-קבוצה סופית של האקסיומות קיים מודל, ולכן קיים מודל לכולן (לא שברור למישהו איך הוא נראה…). סוף הסיפור.

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

בואו ונעשה תעלול דומה, אבל באופן קצת יותר חיובי, עבור המספרים הממשיים. בואו ניקח מילון פסיכי – לכל מספר ממשי \(r\in\mathbb{R}\) יהיה בו סימן קבוע \(c_{r}\), ולכל יחס אפשרי על הממשיים יהיה בו סימן עבור היחס הזה. בנוסף בואו ניקח בתור אקסיומות את כל הפסוקים מעל המילון הזה שנכונים בממשיים. במובן מסויים קיבלנו תורה ש"מתארת באופן מושלם" את הממשיים. אבל האם היא חומקת ממשפט הקומפקטיות? שוב, לא; נוסיף לה סימן קבוע חדש \(c\) ואת הפסוקים \(c_{r}<c\) לכל \(r\in\mathbb{R}\), ומשפט הקומפקטיות שוב יראה שיש לתורה הזו מודל שבו יש מספר שגדול מכל מספר ממשי.

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

הרעיון הזה הוא השלב הראשון בדרך אל מה שנקרא אנליזה לא סטנדרטית – תחום שבו בונים את החדו"א מחדש בעזרת אינפיניטסימלים שכאלה (הנה הגדרה אלטרנטיבית לגבול: \(\lim_{x\to x_{0}}f\left(x\right)=L\) אם כאשר \(\left|x-x_{0}\right|\) הוא אינפיניטסימלי, כך גם \(\left|f\left(x\right)-L\right|\)), אבל כשעושים את זה ברצינות צריך לגשת לנושא בצורה קונסטרוקטיבית יותר ואני לא הולך לעשות את זה כרגע. עצם העובדה שמשפט הקומפקטיות הופך את הוכחת ההיתכנות של אנליזה לא סטנדרטית לטריוויאלית זו תוצאה מספיק מלהיבה עבורי לפוסט הזה.

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

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

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

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

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

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

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

הקסם שבריבועי קסם

בואו נתחיל עם צפיה בקסם המרהיב שבסרטון בלינק הבא:

http://vimeo.com/60852161

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

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

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

על ריבועי קסם באופן כללי

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

\(\left[\begin{array}{ccc}2 & 7 & 6\\9 & 5 & 1\\4 & 3 & 8\end{array}\right]\)

והנה ריבוע הקסם של הקוסם בסרט:

\(\left[\begin{array}{cccc}8 & 11 & 22 & 1\\21 & 2 & 7 & 12\\3 & 24 & 9 & 6\\10 & 5 & 4 & 23\end{array}\right]\)

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

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

ובכן, פרמוטציה של המספרים מ-\(1\) ועד \(n\) היא פשוט ערבוב כלשהו של המספרים הללו. למשל, פרמוטציה לדוגמה של המספרים מ-1 עד 4 היא \(3,1,2,4\). תיאור מילולי של הפרמוטציה הזו יהיה "האיבר הראשון בפרמוטציה הוא 3, השני הוא 1; השלישי הוא 2; הרביעי הוא 4".

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

\(\left[\begin{array}{cccc}0 & 0 & 1 & 0\\1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 0 & 1\end{array}\right]\)

מה קורה פה? עברו על המטריצה הזו שורה שורה ובדקו מהו מספר העמודה שבה יש 1. בשורה הראשונה זוהי עמודה 3; בשניה זוהי 1; בשלישית זוהי 2; ברביעית זוהי 4. הנה הפרמוטציה!

המטריצה הזו היא יותר מאשר "סתם" דרך כתיבה משונה למשהו שכתבתי באופן פשוט יותר: אם כופלים אותה בוקטור \(\left(1,2,3,4\right)\) מקבלים:

\(\left[\begin{array}{cccc}0 & 0 & 1 & 0\\1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 0 & 1\end{array}\right]\left[\begin{array}{c}1\\2\\3\\4\end{array}\right]=\left[\begin{array}{c}3\\1\\2\\4\end{array}\right]\)

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

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

\(\left[\begin{array}{cccc}0 & 0 & 22 & 0\\21 & 0 & 0 & 0\\0 & 24 & 0 & 0\\0 & 0 & 0 & 23\end{array}\right]\)

אחרי שמבינים את זה, קל יותר לנחש מה ההמשך. אם הקוסם לקח רביעיה אחת של מספרים, 21,22,23,24 ופיזר אותה בתוך משבצות בריבוע שמהוות פרמוטציה, אולי הוא עשה את זה עם עוד רביעיות? אז כדאי לחפש מספרים בריבוע שערכיהם סמוכים. המספר הגדול ביותר בריבוע מלבד אלו של העשרים ומשהו הוא \(12\), אז אפשר לנחש שהרביעיה הבאה היא \(9,10,11,12\), ואכן, הם מפוזרים במקומות הבאים בריבוע:

\(\left[\begin{array}{cccc}0 & 11 & 0 & 0\\0 & 0 & 0 & 12\\0 & 0 & 9 & 0\\10 & 0 & 0 & 0\end{array}\right]\)

עכשיו כבר ברור שיהיו עוד שתי רביעיות, אחת של \(5,6,7,8\) ואחת של \(1,2,3,4\). בסופו של דבר נקבל "פירוק" של הריבוע לסכום של ארבעה ריבועים:

\(\left[\begin{array}{cccc}0 & 0 & 22 & 0\\21 & 0 & 0 & 0\\0 & 24 & 0 & 0\\0 & 0 & 0 & 23\end{array}\right]+\left[\begin{array}{cccc}0 & 11 & 0 & 0\\0 & 0 & 0 & 12\\0 & 0 & 9 & 0\\10 & 0 & 0 & 0\end{array}\right]+\left[\begin{array}{cccc}8 & 0 & 0 & 0\\0 & 0 & 7 & 0\\0 & 0 & 0 & 6\\0 & 5 & 0 & 0\end{array}\right]+\left[\begin{array}{cccc}0 & 0 & 0 & 1\\0 & 2 & 0 & 0\\3 & 0 & 0 & 0\\0 & 0 & 4 & 0\end{array}\right]\)

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

\(\left[\begin{array}{cccc}0 & 0 & 22 & 0\\21 & 0 & 0 & 0\\0 & 24 & 0 & 0\\0 & 0 & 0 & 23\end{array}\right]\)

בריבוע שבו החסרתי 20 מכל מספר, כלומר

\(\left[\begin{array}{cccc}0 & 0 & 2 & 0\\1 & 0 & 0 & 0\\0 & 4 & 0 & 0\\0 & 0 & 0 & 3\end{array}\right]\)

אקבל שסכום כל שורה ועמודה ואלכסון ורבע בריבוע הקסם החדש הוא 22.

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

\(\left[\begin{array}{cccc}0 & 0 & 2 & 0\\1 & 0 & 0 & 0\\0 & 4 & 0 & 0\\0 & 0 & 0 & 3\end{array}\right]+\left[\begin{array}{cccc}0 & 3 & 0 & 0\\0 & 0 & 0 & 4\\0 & 0 & 1 & 0\\2 & 0 & 0 & 0\end{array}\right]+\left[\begin{array}{cccc}4 & 0 & 0 & 0\\0 & 0 & 3 & 0\\0 & 0 & 0 & 2\\0 & 1 & 0 & 0\end{array}\right]+\left[\begin{array}{cccc}0 & 0 & 0 & 1\\0 & 2 & 0 & 0\\3 & 0 & 0 & 0\\0 & 0 & 4 & 0\end{array}\right]\)

והסכום של כל אלו נותן לי את הריבוע:

\(\left[\begin{array}{cccc}4 & 3 & 2 & 1\\1 & 2 & 3 & 4\\3 & 4 & 1 & 2\\2 & 1 & 4 & 3\end{array}\right]\)

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

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

magic_square

כאן צבעתי כל רביעייה בצבע שונה, ועכשיו אפשר לראות בעיניים את התכונות של הריבוע:

  1. לכל משבצת יש צבע מבין 4 צבעים אפשריים ויש בתוכה מספר בין 1 ל-4.
  2. בכל שורה ובכל עמודה כל המספרים שונים.
  3. בכל שורה ובכל עמודה כל הצבעים שונים.
  4. כל שילוב אפשרי של צבע ומספר מופיע בדיוק פעם אחת.

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

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

\(\left[\begin{array}{ccc}1 & 2 & 3\\2 & 3 & 1\\3 & 1 & 2\end{array}\right]\)

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

בבירור כל ריבוע לטיני הוא גם ריבוע קסם, במובן זה שסכום כל השורות וכל העמודות בו הוא זהה, ושווה לסכום קבוצת המספרים שמופיעים בריבוע. למשל, בריבוע שבניתי הסכום יהיה \(1+2+3=6\). מדוע זה עובד? ובכן, בכל שורה ובכל עמודה בריבוע הלטיני כל האיברים שונים זה מזה ולכן הם בדיוק כל \(n\) המספרים שבכלל יכולים להופיע בריבוע הלטיני ולכן סכום כל שורה וכל עמודה שווה לסכומם.

נניח שאני רוצה שסכום השורות והעמודות בריבוע שבניתי למעלה לא יהיה 6 אלא מספר אחר, נאמר 77, מה אעשה? ובכן, פתרון אחד הוא להחליף כל מופע של 1 ב-72:

\(\left[\begin{array}{ccc}72 & 2 & 3\\2 & 3 & 72\\3 & 72 & 2\end{array}\right]\)

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

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

\(\left[\begin{array}{ccc}1 & 2 & 3\\2 & 3 & 1\\3 & 1 & 2\end{array}\right]\)

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

ההיסטוריה של ריבועים לטיניים מעניינת למדי. קל להראות שאין זוג ריבועים לטיניים אורתוגונליים מסדר \(2\times2\) ואפשר בקלות רבה למצוא זוג מסדר \(3\times3\) (תכף נראה איך); במאה ה-18 נתגלו גם זוגות עבור \(4\times4\), ואז בא לאונרד אוילר ומצא בניות של זוגות ריבועים לטיניים אורתוגונליים עבור כל גודל \(n\times n\) כאשר \(n\) הוא אי זוגי או מתחלק ב-4. זו הייתה קפיצת דרך מרהיבה, אבל היא עדיין הותירה פתוחה את השאלה מה קורה כאשר \(n\) הוא מספר זוגי אשר משאיר שארית 2 בחלוקה ב-4. המספרים הראשונים מסוג זה הם 2 ו-6: אוילר ידע שאין פתרון עבור 2 ולא עלה בידו למצוא פתרון עבור 6 (אבל גם לא הוכחה שאין פתרון כזה), והוא העלה את ההשערה שבאופן כללי אין פתרון עבור \(n\) שמשאיר שארית 2 בחלוקה ב-4.

רק בשנת 1901 הוכח שאוילר צדק בכך שחשב שאין פתרון עבור 6, אבל 1959 הוכח כי עבור כל \(n\ne2,6\) אכן קיים פתרון! לי אין מושג איך בונים את הפתרונות הללו, אבל אולי אקדיש לכך פוסטים בעתיד אם הבניה פשוטה דיו להצגה כאן.

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

על כן, דרך הפעולה שלי היא כזו: אני אבחר צבע ואותיר את המספרים \(1,2,\dots,n\) שלו ללא שינוי. אחר כך אני אבחר צבע אחר ואוסיף לכל מספר בו \(n\) וכך אקבל את המספרים \(n+1,n+2,\dots,2n\). אחר כך אלך אל הצבע הבא ואוסיף למספרים שלו \(3n\) וכן הלאה.

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

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

\(\left[\begin{array}{ccc}1 & 2 & 3\\2 & 3 & 1\\3 & 1 & 2\end{array}\right]\)

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

\(\left[\begin{array}{ccc}a & b & c\\c & a & b\\b & c & a\end{array}\right]\)

ועכשיו כשנשלב את שני הריבועים שבנינו יחד נקבל:

\(\left[\begin{array}{ccc}\left(1,a\right) & \left(2,b\right) & \left(3,c\right)\\\left(2,c\right) & \left(3,a\right) & \left(1,b\right)\\\left(3,b\right) & \left(1,c\right) & \left(2,a\right)\end{array}\right]\)

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

עכשיו, איך נבנה ריבוע קסם מהדבר הזה? ובכן, את המספרים שהם שכנים של \(a\) נותיר כמות שהם; את המספרים שהם שכנים של \(b\) נגדיל ב-3, ואת המספרים שהם שכנים של \(c\) נגדיל ב-6. נקבל:

\(\left[\begin{array}{ccc}1 & 5 & 9\\8 & 3 & 4\\6 & 7 & 2\end{array}\right]\)

קיבלנו ריבוע של המספרים מ-1 עד 9 כאשר כל שורה וכל עמודה מסתכמת ל-15, אך לא האלכסונים. מה עשיתי לא נכון? אם תסתכלו על האלכסונים בריבוע האורתוגונלי שלמעלה, תראו שהם לא "נחמדים" – באחד מהם מופיע 3 בכל המשבצות, ובשני מופיע \(a\) בכל המשבצות. במקרה של האלכסון \(\left(3,c\right),\left(3,a\right),\left(3,b\right)\) זה אומר שהסכום שלו יהיה 9 (הסכום של שלושת ה-3-ים) ועוד הערכים שאני נותן ל-\(a,b,c\) שהם במקרה שלנו \(0,3,6\), כלומר הסכום הכולל יהיה 18 – לא מוצלח.

אז בואו נכתוב את הריבוע האורתוגונלי כמו שאוילר התכוון – עם אותיות לטיניות ויווניות ובלי מספרים כלל:

\(\left[\begin{array}{ccc}\left(\alpha,a\right) & \left(\beta,b\right) & \left(\gamma,c\right)\\\left(\beta,c\right) & \left(\gamma,a\right) & \left(\alpha,b\right)\\\left(\gamma,b\right) & \left(\alpha,c\right) & \left(\beta,a\right)\end{array}\right]\)

וכעת, כדי לקבל ריבוע קסם מהיצור הזה אנחנו צריכים לבחור ערכים מספריים לכל אות יוונית ולכל אות לטינית, ואז לכל משבצת בריבוע לחבר את המספרים שבחרו לאות היוונית והלטינית שמופיעות במשבצת. אנחנו יודעים שאוטומטית, הסכום של כל שורה ושל כל עמודה יהיה שווה ל-\(\left(a+b+c\right)+\left(\alpha+\beta+\gamma\right)\) ולכן כל שנותר לנו לדאוג לו הוא האלכסונים. הסכום של אחד האלכסונים הוא \(3\gamma+\left(a+b+c\right)\) והסכום של האלכסון השני הוא \(3a+\left(\alpha+\beta+\gamma\right)\). מה עוד מגביל אותנו? אם אנחנו רוצים שכל המספרים יהיו שונים זה מזה ושכולם יהיו בטווח מ-1 עד 9, אנחנו חייבים לבחור עבור \(a,b,c\) את הערכים 1,2,3 (לא בהכרח בהתאמה) ועבור \(\alpha,\beta,\gamma\) את הערכים \(0,3,6\) (לא בהכרח בהתאמה). כמובן, אפשר היה להגיד שדווקא האותיות הלטיניות צריכות לקבל 0,3,6 והיווניות 1,2,3 אבל זה לא היה משנה כלום.

אם האותיות היווניות קיבלו 0,3,6 אז \(\alpha+\beta+\gamma=9\) ולכן כדי שיתקיים \(\left(\alpha+\beta+\gamma\right)=15\)\(3a+\) בהכרח חייב להתקיים \(a=2\). בדומה, אם האותיות הלטיניות קיבלו את 1,2,3 אז \(\left(a+b+c\right)=9\) אז \(3\gamma+\left(a+b+c\right)=15\) גורר ש-\(\gamma=3\). את שאר המספרים אפשר לבחור בחופשיות (תחת המגבלות שכבר מצאנו). בואו נבחר \(\alpha=0,\beta=6,b=1,c=3\) ונקבל את הריבוע הבא:

\(\left[\begin{array}{ccc}2 & 7 & 6\\9 & 5 & 1\\4 & 3 & 8\end{array}\right]\)

וקיבלנו בדיוק את מה שרצינו – ריבוע קסם מסדר \(3\times3\) עם המספרים מ-1 עד 9 שבו כל השורות, העמודות והאלכסונים מסתכמים ל-15. כפי שאפשר לראות, בסופו של דבר לא נדרש הרבה יותר מהגיון בריא בסיסי כדי למצוא את הריבוע הזה, וגם ילדים יכולים לעשות זאת (וכנראה עם הרבה פחות קשקושים מסביב ממני).

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

איך הקסם עבד?

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

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

את התעלול הקוסם מתחיל כשהחבילה מונחת לידו, כשהיא כבר מסודרת באופן שנוח לקוסם. אף אחד לא מערבב אותה בשום שלב, וזה כמובן קריטי לחלוטין. בתחילת הקסם הקוסם מסיר מראש החבילה מספר קלפים עד שהוא מגיע לקלף 8 (כפי שכבר ראינו, 8 הוא מספר קטן מכדי להופיע בתור סכום של ריבוע קסם). אפשר להניח בשקט שהקלפים מעל 8 הם קלפים ספציפיים שהחבילה מהונדסת כדי שהתעלול יעבוד עבורם. אליו מספרים יש שם? 26 (פעמיים), 42, 22 (פעמיים), 34, 30, 50. כולם מספרים שאפשר לבנות ריבוע קסם עבורם (עבור 22 ו-30 הסיטואציה טיפה בעייתית כי בריבוע הקסם שיתקבל יהיו מספרים שמופיעים יותר מפעם אחת – אני משער שלקוסם אין בעיה עם זה).

אם נקפוץ קדימה לשלב שבו הקוסם מתחיל ליצור את ערימות הקלפים שירכיבו את ריבוע הקסם (1:22) נראה שהוא בונה ארבע ערימות באופן הדרגתי: בהתחלה מניח 8,7,9,10 (בסדר הזה), אחר כך מניח 11,1,6,3, אחר כך 2,12,4,5, ואז… הויסה, רגע. בואו ניזכר בפירוק לארבע פרמוטציות של ריבוע הקסם של הקוסם:

\(\left[\begin{array}{cccc}0 & 0 & 22 & 0\\21 & 0 & 0 & 0\\0 & 24 & 0 & 0\\0 & 0 & 0 & 23\end{array}\right]+\left[\begin{array}{cccc}0 & 11 & 0 & 0\\0 & 0 & 0 & 12\\0 & 0 & 9 & 0\\10 & 0 & 0 & 0\end{array}\right]+\left[\begin{array}{cccc}8 & 0 & 0 & 0\\0 & 0 & 7 & 0\\0 & 0 & 0 & 6\\0 & 5 & 0 & 0\end{array}\right]+\left[\begin{array}{cccc}0 & 0 & 0 & 1\\0 & 2 & 0 & 0\\3 & 0 & 0 & 0\\0 & 0 & 4 & 0\end{array}\right]\)

ברור לגמרי שהקלפים הונדסו כך שבכל שלב של החילוק יונח קלף אחד בדיוק עבור כל רבע. למשל, הקלפים שהונחו ראשונים בכל שלב היו 8,11,2, שנמצאים ברבע השמאלי-עליון של הפרמוטציות – מלבד זו השמאלית ביותר שטרם הופיעה. אם עבור הפרמוטציה השמאלית ביותר היינו בוחרים את המספרים 1,2,3,4 היינו מקבלים שסכום כל שורה-טור-אלכסון-רבע הוא 22, המספר הראשון שהיה עשוי להיבחר על ידי המשתתף; כך שאפשר להניח בשקט ש-12 הקלפים שחולקו בשלב הזה הם חלק קבוע מסידור החפיסה שאינו תלוי בבחירה של המשתתף.

מה כן משתנה? ארבעת הקלפים הבאים, שהם כמובן 21,22,23,24. מרגע שהם הונחו, כל שנותר לקוסם לעשות הוא לסדר את ריבוע הקסם בצורה נכונה (זה כמובן דורש שינון כלשהו) והופה! ריבוע הקסם התקבל. צריך גם להסביר איך קרה שעל גב הקלפים כתוב שהמשתתף הולך לבחור 42. ובכן, מה שכתוב על רוב הקלפים הוא חסר חשיבות כי הוא אינו תלוי במספר; הדבר היחיד שחשוב הוא הקלף האחרון, בפינה הימנית-תחתונה, שעליו כתוב "42". הקלף הזה הוא הקלף שמספרו 23, כלומר לא אחד מ-12 הקלפים ה"גנריים" אלא קלף שמתאים לפרמוטציה השמאלית ביותר, שנקבעת ספציפית על פי המספר שהמשתתף בחר.

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

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