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

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

משפט זקנדורף

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

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

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

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

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

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

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

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

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

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

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. … להמשיך לקרוא

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

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

המתמטיקה של RSA

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

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

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