משפט ארבעת הריבועים של לגראנז'

אני רוצה לדבר על אחת מהתוצאות הנחמדות ביותר (לטעמי) בתורת המספרים האלמנטרית – משפט ארבעת הריבועים של לגראנז'. בפשטות, המשפט אומר שאפשר להציג כל מספר טבעי בתור סכום של ארבעה ריבועים של מספרים טבעיים (כש-0 נחשב למספר טבעי). הנה דוגמאות עבור המספרים הטבעיים מ-1 עד 7: $latex 1=1^{2}+0^{2}+0^{2}+0^{2}$ $latex 2=1^{2}+1^{2}+0^{2}+0^{2}$ $latex 3=1^{2}+1^{2}+1^{2}+0^{2}$ $latex 4=2^{2}+0^{2}+0^{2}+0^{2}$ $latex …

משפט זקנדורף

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

אקסיומת הבחירה, עקרון הסדר הטוב, הלמה של צורן – מי יודע?

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

משפט קנטור-שרדר-ברנשטיין

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

תורת המספרים האלגברית על קצה המזלג, חלק ג' – שובו של הפירוק היחיד

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

גם אני לא מאמין באינדוקציה (כי לאמונה אין קשר לזה)

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

כלל ה-0-1 של גרפים – ההוכחה

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. למשל, הפסוק $latex \exists v_{1},v_{2},v_{3}\left(E\left(v_{1},v_{2}\right)\wedge E\left(v_{2},v_{3}\right)\wedge E\left(v_{3},v_{1}\right)\right)$ שמתאר את "בגרף קיים משולש" שראינו בפוסט הקודם …

המשפט היסודי של האלגברה – הוכחה אלגברית

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

המתמטיקה של RSA

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

על הבעייה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית

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