When I was in fourth grade, my teacher said to us one day: "There are as many even numbers as there are numbers." "Really?", I thought. Well, yeah, there are infinitely many of both, so I suppose there are the same number of them. But even numbers are only part of the whole numbers, all the odd numbers are left over, so there's got to be more whole numbers than even numbers, right? To see what my teacher was getting at, let's first think about what it means for two sets to be the same size. What do I mean when I say I have the same number of fingers on my right hand as I do on left hand? Of course, I have five fingers on each, but it's actually simpler than that. I don't have to count, I only need to see that I can match them up, one to one. In fact, we think that some ancient people who spoke languages that didn't have words for numbers greater than three used this sort of magic. For instance, if you let your sheep out of a pen to graze, you can keep track of how many went out by setting aside a stone for each one, and putting those stones back one by one when the sheep return, so you know if any are missing without really counting. As another example of matching being more fundamental than counting, if I'm speaking to a packed auditorium, where every seat is taken and no one is standing, I know that there are the same number of chairs as people in the audience, even though I don't know how many there are of either. So, what we really mean when we say that two sets are the same size is that the elements in those sets can be matched up one by one in some way. My fourth grade teacher showed us the whole numbers laid out in a row, and below each we have its double. As you can see, the bottom row contains all the even numbers, and we have a one-to-one match. That is, there are as many even numbers as there are numbers. But what still bothers us is our distress over the fact that even numbers seem to be only part of the whole numbers. But does this convince you that I don't have the same number of fingers on my right hand as I do on my left? Of course not. It doesn't matter if you try to match the elements in some way and it doesn't work, that doesn't convince us of anything. If you can find one way in which the elements of two sets do match up, then we say those two sets have the same number of elements. Can you make a list of all the fractions? This might be hard, there are a lot of fractions! And it's not obvious what to put first, or how to be sure all of them are on the list. Nevertheless, there is a very clever way that we can make a list of all the fractions. This was first done by Georg Cantor, in the late eighteen hundreds. First, we put all the fractions into a grid. They're all there. For instance, you can find, say, 117/243, in the 117th row and 243rd column. Now we make a list out of this by starting at the upper left and sweeping back and forth diagonally, skipping over any fraction, like 2/2, that represents the same number as one the we've already picked. We get a list of all the fractions, which means we've created a one-to-one match between the whole numbers and the fractions, despite the fact that we thought maybe there ought to be more fractions. OK, here's where it gets really interesting. You may know that not all real numbers -- that is, not all the numbers on a number line -- are fractions. The square root of two and pi, for instance. Any number like this is called irrational. Not because it's crazy, or anything, but because the fractions are ratios of whole numbers, and so are called rationals; meaning the rest are non-rational, that is, irrational. Irrationals are represented by infinite, non-repeating decimals. So, can we make a one-to-one match between the whole numbers and the set of all the decimals, both the rationals and the irrationals? That is, can we make a list of all the decimal numbers? Cantor showed that you can't. Not merely that we don't know how, but that it can't be done. Look, suppose you claim you have made a list of all the decimals. I'm going to show you that you didn't succeed, by producing a decimal that is not on your list. I'll construct my decimal one place at a time. For the first decimal place of my number, I'll look at the first decimal place of your first number. If it's a one, I'll make mine a two; otherwise I'll make mine a one. For the second place of my number, I'll look at the second place of your second number. Again, if yours is a one, I'll make mine a two, and otherwise I'll make mine a one. See how this is going? The decimal I've produced can't be on your list. Why? Could it be, say, your 143rd number? No, because the 143rd place of my decimal is different from the 143rd place of your 143rd number. I made it that way. Your list is incomplete. It doesn't contain my decimal number. And, no matter what list you give me, I can do the same thing, and produce a decimal that's not on that list. So we're faced with this astounding conclusion: The decimal numbers cannot be put on a list. They represent a bigger infinity that the infinity of whole numbers. So, even though we're familiar with only a few irrationals, like square root of two and pi, the infinity of irrationals is actually greater than the infinity of fractions. Someone once said that the rationals -- the fractions -- are like the stars in the night sky. The irrationals are like the blackness. Cantor also showed that, for any infinite set, forming a new set made of all the subsets of the original set represents a bigger infinity than that original set. This means that, once you have one infinity, you can always make a bigger one by making the set of all subsets of that first set. And then an even bigger one by making the set of all the subsets of that one. And so on. And so, there are an infinite number of infinities of different sizes. If these ideas make you uncomfortable, you are not alone. Some of the greatest mathematicians of Cantor's day were very upset with this stuff. They tried to make these different infinities irrelevant, to make mathematics work without them somehow. Cantor was even vilified personally, and it got so bad for him that he suffered severe depression, and spent the last half of his life in and out of mental institutions. But eventually, his ideas won out. Today, they're considered fundamental and magnificent. All research mathematicians accept these ideas, every college math major learns them, and I've explained them to you in a few minutes. Some day, perhaps, they'll be common knowledge. There's more. We just pointed out that the set of decimal numbers -- that is, the real numbers -- is a bigger infinity than the set of whole numbers. Cantor wondered whether there are infinities of different sizes between these two infinities. He didn't believe there were, but couldn't prove it. Cantor's conjecture became known as the continuum hypothesis. In 1900, the great mathematician David Hilbert listed the continuum hypothesis as the most important unsolved problem in mathematics. The 20th century saw a resolution of this problem, but in a completely unexpected, paradigm-shattering way. In the 1920s, Kurt Gödel showed that you can never prove that the continuum hypothesis is false. Then, in the 1960s, Paul J. Cohen showed that you can never prove that the continuum hypothesis is true. Taken together, these results mean that there are unanswerable questions in mathematics. A very stunning conclusion. Mathematics is rightly considered the pinnacle of human reasoning, but we now know that even mathematics has its limitations. Still, mathematics has some truly amazing things for us to think about.
כשהייתי בכיתה ד', המורה אמר לנו: "מספר המספרים הזוגיים זהה למספר המספרים הטבעיים." "באמת?" חשבתי. ובכן, שניהם אינסופיים, אז אני מניח שמספרם זהה. אבל מצד שני, המספרים הזוגיים הם רק חלק מהמספרים הטבעיים. יש גם מספרים אי זוגיים, אז חייבים להיות יותר מספרים טבעיים. לא? כדי לראות למה התכוון המורה שלי, נחשוב מה המשמעות של שתי קבוצות באותו גודל. כשאני אומר "יש לי אותו מספר אצבעות ביד ימין וביד שמאל", למה אני מתכוון? כמובן, יש לי 5 אצבעות בכל יד, אך העניין עוד יותר פשוט. אני לא צריך לספור. אני רק צריך לוודא שאני יכול להתאים ביניהן, אחת לאחת. למעשה, אנחנו חושבים שבעת העתיקה חלק מהשפות שלא כללו מילים עבור מספרים גדולים מ-3 השתמשו בקסם הזה. לדוגמא, אם הוצאתם כבשה מהדיר למרעה תוכלו לעקוב אחר מספר הכבשים שיצאו אם תניחו בצד אבן עבור כל כבשה שיצאה, ואז תחזירו אחת אחת את האבנים כשהכבשים יחזרו מהמרעה. וכך תדעו אם חסרה כבשה ללא צורך בספירה. דוגמא נוספת לכך שהתאמה בסיסית יותר מספירה, אם אני מרצה לפני אולם מלא, שבו כל הכסאות תפוסים, ואף אחד לא עומד, אני יודע שמספר הכסאות זהה למספר האנשים בקהל, למרות שאני לא יודע כמה כסאות או אנשים ישנם. וכך, כשאנחנו אומרים ששתי קבוצות הן באותו גודל, אנחנו מתכוונים שיש דרך לבצע התאמה חד חד ערכית בין האיברים של שתי הקבוצות . וכך המורה הראה לנו את המספרים הטבעיים ערוכים בשורה, ומתחת לכל מספר הוא כתב את המספר מוכפל ב-2. השורה התחתונה מכילה את כל המספרים הזוגיים, ויש לנו התאמה חד חד ערכית בין השורות. כלומר, מספר המספרים הזוגיים זהה למספר המספרים הטבעיים. אבל איך זה יכול להיות? המספרים הזוגיים הם קבוצה חלקית של קבוצת המספרים הטבעיים. אבל האם זה משכנע אתכם שמספר האצבעות בידי הימנית שונה ממספר האצבעות בידי השמאלית? כמובן שלא. אם התאמה בדרך מסויימת נכשלת, זה לא מוכיח לנו שום דבר. אם מוצאים דרך אחת שבה יש התאמה חד חד ערכית בין איברי שתי הקבוצות אז אנחנו אומרים שמספר האיברים בשתי הקבוצות זהה. האם אתם יכולים להכין רשימה של כל השברים? זאת משימה קשה, יש המון שברים! ולא ברור מי מהם יהיה ראשון, או איך מוודאים שכל השברים מופיעים ברשימה. עם זאת, ישנה דרך מתוחכמת להכין רשימה של כל השברים. הראשון שביצע זאת היה גאורג קנטור, בסוף המאה ה-19. ראשית, נכניס את כל השברים לטבלה. כולם נמצאים שם. לדוגמא, תוכלו למצוא את 117/243, במשבצת שבשורה 117 ועמודה 243. כעת נהפוך את הטבלה לרשימה. נתחיל בפינה השמאלית העליונה ונתקדם הלוך ושוב באלכסונים, ונדלג על שברים, כמו 2/2, שמייצגים מספר שכבר בחרנו. וכך קיבלנו רשימה של כל השברים. ומשמעות הדבר היא שיצרנו התאמה חד חד ערכית בין המספרים הטבעיים והשברים, למרות שחשבנו שאולי אמורים להיות יותר שברים. אוקי, נעבור כעת לחלק המעניין באמת. יתכן שידוע לכם שלא כל המספרים הממשיים, כלומר, לא כל המספרים על ציר המספרים, הם שברים. שורש ריבועי של 2, והמספר פאי, הם דוגמאות לכך. המספרים האלו נקראים מספרים אי רציונליים. לא בגלל שהם משוגעים אלא מכיוון שהשברים הם יחס (ratio) בין מספרים טבעיים, ולכן הם נקראים מספרים רציונליים. ושאר המספרים הם אי רציונליים. המספרים האי רציונליים מיוצגים ע"י מספרים עשרוניים אינסופיים שאינם מחזוריים. האם נוכל לבצע התאמה חד חד ערכית בין המספרים הטבעיים לקבוצת כל המספרים העשרוניים, הרציונליים והאי רציונליים? כלומר, האם נוכל להכין רשימה של כל המספרים העשרוניים? קנטור הוכיח שלא ניתן להכין רשימה כזו, לא רק שאנחנו לא יודעים איך, אלא שזה בלתי אפשרי. נניח שאתם טוענים שהצלחתם להכין רשימה של כל המספרים העשרוניים. אראה לכם שלא הצלחתם. אציג בפניכם מספר עשרוני שלא נמצא ברשימה שלכם. אני אבנה את המספר העשרוני שלי ספרה אחר ספרה. עבור הספרה הראשונה שלי, אבדוק מהי הספרה הראשונה במספר הראשון ברשימה שלכם. אם היא 1, הספרה שלי תהיה 2. אחרת - הספרה שלי תהיה 1. עבור הספרה השניה במספר שלי, אבדוק את הספרה השניה במספר השני ברשימה שלכם. ושוב, אם הספרה שלכם היא 1, הספרה שלי תהיה 2. אחרת - הספרה שלי תהיה 1. מבינים איך זה הולך? המספר העשרוני שבניתי לא יכול להופיע ברשימה שלכם. למה? האם הוא יכול להופיע, למשל, במקום ה-143 ברשימה שלכם? לא, מכיוון שהמקום ה-143 במספר שלי שונה מהמקום ה-143 במספר ה-143 ברשימה שלכם. ככה בניתי אותו. ולכן, הרשימה שלכם לא שלמה. היא לא כוללת את המספר העשרוני שלי. ולכל רשימה שתציגו בפני, אני יכול לבצע את אותו טריק, ולבנות מספר עשרוני שלא מופיע ברשימה שלכם. וכך הגענו למסקנה המפתיעה הבאה: לא ניתן להכין רשימה של המספרים העשרוניים. הם מייצגים אינסוף גדול יותר מהאינסוף של המספרים הטבעיים. וכך, למרות שאנחנו מכירים רק מספר קטן של מספרים אי רציונליים, כמו שורש ריבועי של 2 או פאי, האינסוף של כל המספרים האי רציונליים הוא למעשה יותר גדול מהאינסוף של השברים. מישהו אמר פעם שהמספרים הרציונליים - השברים - הם כמו הכוכבים בשמי הלילה, המספרים האי רציונליים הם כמו החשיכה. קנטור הראה גם שעבור כל קבוצה אינסופית, קבוצה הכוללת את כל תתי הקבוצות של הקבוצה המקורית מייצגת אינסוף גדול יותר מהאינסוף של הקבוצה המקורית. פירוש הדבר הוא, שברגע שיש אינסוף אחד, ניתן תמיד ליצור אינסוף גדול יותר אם נבנה את כל תתי הקבוצות של הקבוצה הקודמת. ואז אינסוף עוד יותר גדול אם ניצור קבוצה של כל תתי הקבוצות של הקבוצה הבאה בתור. וכן הלאה. וכך, יש מספר אינסופי של אינסופים. אם זה נשמע לכם מוזר, אתם אינכם לבדכם. חלק מהמתמטיקאים הגדולים ביותר בתקופתו של קנטור מצאו את הרעיונות האלה מטרידים ביותר. הם ניסו להפוך את האינסופים השונים ללא רלוונטיים, ולגרום למתמטיקה להסתדר איכשהו בלעדיהם. קנטור עצמו הוכפש באופן אישי, והוא סבל מדיכאון קשה, ובילה את המחצית השניה של חייו כשהוא נכנס ויוצא מבתי חולים לחולי נפש. אבל בסופו של דבר הרעיונות שלו זכו להצלחה. וכיום, הם נחשבים לרעיונות יסודיים ומופלאים. כל המתמטיקאים העוסקים במחקר מקבלים את הרעיונות האלה, וכל תלמיד קולג' למתמטיקה לומד אותם, ואני הסברתי לכם אותם בכמה דקות. ויום אחד, אולי, כל אדם יכיר אותם. ויש עוד. הרגע ראינו שקבוצת המספרים העשרוניים - כלומר, המספרים הממשיים - היא אינסוף גדול יותר מקבוצת המספרים הטבעיים. קנטור תהה האם יש אינסופים מגדלים שונים בין שני האינסופים האלה. הוא לא האמין שהם קיימים אך לא הצליח להוכיח את הדבר. ההשערה של קנטור ידועה כהשערת הרצף. בשנת 1900, המתמטיקאי הגדול דייוויד הילברט החשיב את השערת הרצף לבעיה המתמטית הלא פתורה החשובה ביותר. במאה ה-20 נמצא פתרון לבעיה, בצורה לגמרי בלתי צפויה ומהפכנית. בשנות ה-20 של המאה ה-20, קורט גדל הראה שלא ניתן להפריך את השערת הרצף. ואז, בשנות ה-60 של המאה ה-20, פול ג'. כהן הראה שלא ניתן להוכיח שהשערת הרצף נכונה. משמעות הדברים היא שהמתמטיקה כוללת שאלות שלא ניתן למצוא להן מענה. מסקנה מדהימה ביותר. מתמטיקה נחשבת כחוד החנית של החשיבה האנושית. אבל כעת אנו יודעים שאפילו למתמטיקה יש מגבלות. ועדיין, המתמטיקה כוללת חומר למחשבה מרתק עבורנו.