משפט קנטור-שרדר-ברנשטיין – ועכשיו בגרסת המלון של הילברט!

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

על גבולות עליונים ותחתונים של קבוצות וממשיים

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

על על-מסננים ועל-מכפלות

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

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

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

איור: המלון של הילברט

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

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

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

סודרים – התיאור הפורמלי

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

סודרים – מה זה בכלל? (הסבר אינטואיטיבי תוך כדי משחק)

בפוסט הקודם דיברתי על האופן שבו קנטור "המציא" את הסודרים, אך כפי שיתברר בפוסט הזה, כנראה שהמילה "תגלית" יותר הולמת. קנטור הגיע אל הסודרים על ידי כך שהוא הגדיר סדרת קבוצות $latex P^{\left(1\right)},P^{\left(2\right)},\dots$ ושם לב שיש משמעות גם לקבוצה $latex P^{\left(\infty\right)}$ שמתקבלת כמעין "גבול" של הקבוצות עד אליה, ושאחרי שיש לנו אותה, יש משמעות גם …

איך קנטור המציא את הסודרים?

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

הפרדוקס של ראסל ומשפט קנטור

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

המלון של הילברט, או – מדוע יש גדלים שונים של אינסוף

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

קבוצת קנטור, ואיך לכל הרוחות המימד שלה הוא בערך 0.63?

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

על טרחני-קנטור וטרחני-טרחני-קנטור

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

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

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

האלכסון – אסון

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

הגודל כן קובע

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

איזה גודל (?)

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

בסיס מוצק מי ימצא

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

לבחור או לא לבחור – זו השאלה

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