Infinity: Hilbert's Infinite Grand Hotel PDF

Infinity Hilbert’s Infinite Grand Hotel Prof. Dr. Deniz Karlı Department of Mathematics IŞIK UNIVERSITY Version #: 28–11–2023 IŞIK UNIVERSITY Georg Cantor Some infinities are bigger than other infinities. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 2 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infini...

Infinity Hilbert’s Infinite Grand Hotel Prof. Dr. Deniz Karlı Department of Mathematics IŞIK UNIVERSITY Version #: 28–11–2023 IŞIK UNIVERSITY Georg Cantor Some infinities are bigger than other infinities. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 2 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı Part I: Hilbert’s Hotel 3 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 4 Part I: Hilbert’s Hotel “Hilbert’s hotel” is a story of an imaginary hotel with infinitely many rooms that illustrates the bizarre consequences of assuming an actual infinity of objects or events. Since the 1970s it has been used in a variety of arguments, some of them relating to cosmology and others to philosophy and theology. For a long time it has remained unknown whether David Hilbert actually proposed the thought experiment named after him, or whether it was merely a piece of mathematical folklore. It turns out that Hilbert introduced his hotel in a lecture of January 1924, but without publishing it. IŞIK UNIVERSITY Once, a tired driver was traveling on the road. He was tired of long travel and started seeking for a hotel to stay over night. However, it was the high season and hotels were all booked. He kept driving and driving with the hope of finding an available hotel. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 5 IŞIK UNIVERSITY One hotel after another passed by; there were no available rooms left. He was about to lose hope. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 6 IŞIK UNIVERSITY All of the sudden, he ran into a sign. It was saying: ”No Vacancy, But Come on in...” How come ???? ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 7 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı This was the Hilbert’s Infinite Grand Hotel. It has infinitely many rooms numbered as 1, 2, 3,.. The sign was not lying. All the rooms were occupied. But Hilbert was a very welcoming hotel-owner and said ”Don’t worry. We always have rooms for customers just like you.” But how is he going to do that? And what did he mean by ”customers just like you”? 8 IŞIK UNIVERSITY Hilbert made an announcement in the hotel: ”Dear guests, please move out of your rooms.” ”Now, please check in to the room with a number that is 1 greater than the number of your room. Thank you.” All guests followed the instructions. And all moved to next rooms. Suddenly, the room number 1 became available. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 9 IŞIK UNIVERSITY Hilbert asked the new guest to check-in to the room number 1. All guests are checked-in. The hotel was full before, and it is full now, too. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 10 IŞIK UNIVERSITY Question 1 What if another customer arrives? Can Hilbert find a room for this new arriving customer, too? ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 11 IŞIK UNIVERSITY Question 2 What if 100 customers arrives? Can Hilbert find rooms for these customers, too? ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 12 IŞIK UNIVERSITY Question 3 What if a bus of ” infinitely many” customers arrive? ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 13 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı Part II: Sets & Functions 14 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 15 Part II: Sets & Functions The main objects of mathematics are ”sets” and ”functions”. Set: A collection of well-defined objects. The following collections are sets: * ”All chairs in the room DK201.” * ”Names of days of a week.” * ”Integers from 1 to 10.” Recall that these proper definitions were imposed with the introduction of Axiomatic Set Theory. However the following collections are NOT sets: * ”Some chairs in the room DK201.” * ”Some of days of a week.” * ”Everything.” (Recall: Russell’s Paradox.) Recall that these ambiguous collections was one of the problems arose after Cantor’s and Frege’s definitions of sets. IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 16 Set Notation A set (a properly defined collection of objects) can be represented by either its description, by set notation or by Venn diagram. One can name sets with capital letters such as A, B, C, · · · The following sets are denoted by description: * A={First 3 lowercase letters of alphabet.} * B={Names of weekend days.} * C={Integers from 1 to 10.} The following sets are denoted by set notation (by their elements): * A={a,b,c} * B={Saturday, Sunday} * C={1,2,3,...,8,9,10} IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı Set Notation The following sets are denoted by Venn diagrams B A · a · b · c · Saturday · Sunday · 1 · 2 · 3... · 9 · 10 C 17 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 18 Functions A function is an unintelligent machine which has an input collection and an output collection. This machine has no intelligence. It performs its duty following a precise set of rules, and has no ability to choose between various outputs in case more than 1 output is associated with a single input. The machine breaks down in such a case. IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 19 Functions Function: A map that associates each element of the first set to exactly one element of the second set. Which of the following maps are functions? ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 20 Function Notation A function can be represented by either its description or by its rule. One can name functions with lowercase letters such as f, g, h, · · · The input collection is called the domain and the output collection is called the range of the function. * Here, A is the domain, * B is the range. Function’s rule is denoted by: * f(a) = 5 * f(b) = 6 * f(c) = z A a b c f B 5 6 z Ettion Etütten f(input) = output IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 21 Function Notation: General Form If the domain (collection of inputs) is large then it is not possible to represent the rule of a function by its effect on each input. Hence rule of a function is represented in its general form. This form is a description of the process using a variable for the input. f(input) = description of output in terms of input. For example, f(x) = 2x is a function’s general rule. For any input x, this function multiplies x with 2 and it returns the result. Some examples of functions: f(x) = 3x + 1 , f(x) = x2 − 1 , f(x) = x+1 x2 + 1 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 22 Part III: Special Functions & Counting IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 23 One-to-One (1-1) Functions A function is called a one-to-one (1-1) function if * every element of the first set (domain) is matched with only one element of the second set (range). Which of the following maps are 1-1 functions? This is Not ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c a a 1 A function This is afore 1 fone but not 1 1 ·▹ ·◦ ·⋆ ·∗ ·φ B ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A Not even a function ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 24 Onto Functions A function is called an onto function if * every element of the second set (range) is matched with at least one element of the first set (domain). Which of the following maps are onto functions? ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 25 Bijective Functions A function is called a bijective function (or bijection) if * it is both one-to-one and onto. Which of the following maps are bijective functions? This is a bijection · · · · · a b c d e ·▹ ·◦ ·⋆ ·∗ ·φ B This is a bijection · · · · · a b c d e ·▹ ·◦ ·⋆ ·∗ ·φ IFII.EE B not bijection B ·▹ ·a ·◦ ·⋆ ·b ·∗ ·φ · c tEEhEY It A en bijection ·▹ ·◦ ·⋆ ·∗ ·φ B ·a ·b · c A IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı One-to-One & Onto Matching If every element of the first set is matched with only one element of the second set, then it is a one-to-one (1-1) matching. If every element of the second set is matched with at least one element of the first set, then it is an onto matching. A One-to-one Match A B ·a ·▹ ·◦ ·b ·⋆ ·∗ · c ·φ Not a one-to-one match A B ·a ·▹ ·◦ ·b ·⋆ ·∗ · c ·φ 1-1 & onto match B A ·▹ ·a ·◦ ·⋆ ·b i J· c An onto match B A ·▹ ·a ·◦ ·⋆ ·b ·∗ ·φ · c 26 1-1 & onto match A A ·1 ·x ·2 ·y ·3 · z Not an onto match B A ·▹ ·a ·◦ ·⋆ ·b ·∗ ·φ · c IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 27 Counting Georg Cantor defined sets as collection of objects. Then he discussed what ”size of a set” means. ”The size of a set” is determined by means of bijective (one-to-one and onto) functions. Question: How do we ”count” the number of elements in a set using functions? What is ”counting”? IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 28 Finite Sets If there exists a bijective (one-to-one and onto) matching between a set A and the subset {1, 2,... , n} of natural numbers N for some n, then A is called a finite set and its size is equal to the number n. We denote the size by |A| = n. A · a · b · c N 1 2 3 4 5 6... B · · · · · ▹ ◦ ⋆ ∗ φ N 1 2 3 4 5 6... IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı What is an infinite set? 29 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı There is a clever answer. 30 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı An infinite set is a set which is NOT finite. 31 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 32 Infinite Sets If there exists NO one-to-one and onto matching between a set A and any subset of natural numbers N of the form {1, 2,..., n}, then A is called of an infinite set. Even Numbers 2 4 6 8 10 12... N 1 2 3 4 5 6... Negative Integers −1 −2 −3 −4 −5 −6... N 1 2 3 4 5 6... IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı Countably Infinite Sets Counting, in the basic sense, is a process using integers since the early ages. Counting finite sets is as basic as primary school algebra. We note that we can label (put into 1-1 and onto matching) elements of some sets (even if they are not finite) using integers. Such sets are called ”countable sets”. Even Numbers 2 4 6 8 10 12... N 1 2 3 4 5 6... 33 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı A set is countably infinite if there exists a bijection between this set and the set of integers N. 34 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 35 The Set of Positive Even Numbers is Countable N 1 2 3 4 5 6... Even Numbers 2 4 6 8 10 12... One bijection is the function f(n) = 2n IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 36 The Set of Positive Odd Numbers is Countable N 1 2 3 4 5 6... Odd Numbers 1 3 5 7 9 11... One bijection is the function f(n) = 2n − 1 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 37 The Set of All Integers, Z, is Countable N 2 4 6... 1 3 5... Z 0 1 2... −1 −2 −3... Tflelation One bijection is the function ⎧ n ⎪ ⎨ 2 − 1 , if n is even, f(n) = ⎪ ⎩ n+1 − 2 , if n is odd. IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 38 The Set of All Positive Rational Numbers, Q+ , is Countable 1 1 1 2 1 3 1 4 1 5 1 6 1 7 ··· 2 1 2 2 2 3 2 4 2 5 2 7 2 7 ··· 3 1 3 2 3 3 3 4 3 5 3 6 3 7 ··· 4 1 4 2 4 3 4 4 4 5 4 7 4 7 ··· 5 1 5 2 5 3 5 4 5 5 5 6 5 7 ··· 6 1 6 2 6 3 6 4 6 5 6 7 6 7 ···........................ * Recall: A number is rational number if it is ratio of two integer with no common multiple. That is, rational numbers are numbers of the form a b where both a and b are integers, b ̸= 0 and a and b has no common divisor other than 1. * One bijection is... IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 39 What about the set of all real numbers between zero and one? i 1 siz IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı In other words, can we find a bijective map between all real numbers in the interval [0, 1] and natural numbers N? 40 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 41 If this were possible, then we could write all real numbers in the interval [0, 1] by labeling them as 1, 2, 3,.... N [0, 1] 1 → 0.a11 a12 a13 a14 a15 · · · 2 → 0.a21 a22 a23 a24 a25 · · · 3 → 0.a31 a32 a33 a34 a35 · · · 4 → 0.a41 a42 a43 a44 a45 · · ·... →... Every number between 0 and 1 can be written as a decimal. For example, √ 1 2 = 0.333333... or = 0.707106... 3 2 Assume all such decimal representations are here in this list, which means they were matched 1-1 and onto with natural numbers. IŞIK UNIVERSITY N ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı [0, 1] 1 → 0.a11 a12 a13 a14 a15 · · · 2 → 0.a21 a22 a23 a24 a25 · · · 3 → 0.a31 a32 a33 a34 a35 · · · 4 → 0.a41 a42 a43 a44 a45 · · ·... → 42 Now define a number as follows: * If a11 = 9, set b1 = 0, if a11 < 9, then set b1 = a11 + 1, * If a22 = 9, set b2 = 0, if a22 < 9, then set b2 = a22 + 1, * If a33 = 9, set b3 = 0, if a33 < 9, then set b3 = a33 + 1, and so on. The number 0.b1 b2 b3 · · · is between 0 and 1.... Question: Is it in our list (list on the left)? IŞIK UNIVERSITY N ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı [0, 1] 1 → 0.a11 a12 a13 a14 a15 · · · 2 → 0.a21 a22 a23 a24 a25 · · · 3 → 0.a31 a32 a33 a34 a35 · · · → 0.a41 a42 a43 a44 a45 · · · 4... → 43 The number 0.b1 b2 b3 · · · * is not the first number, since b1 ̸= a11 , * is not the second number, since b2 ̸= a22 , * is not the third number, since b3 ̸= a33 , and so on. The number 0.b1 b2 b3 · · · is not in our list.... Conclusion: No matter how one tries to list the numbers in [0, 1], there will be some unlisted numbers left. IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 44 The size of the interval [0, 1] is greater than the size of natural numbers N. Although they are infinite in size, they are different infinities. This is called UNCOUNTABLY INFINITE. IŞIK UNIVERSITY Georg Cantor As Cantor said: Some infinities are bigger than other infinities. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 45 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 46 Part IV: Back to the Hilbert’s Grand Hotel IŞIK UNIVERSITY Question 3 What if a bus of ” infinitely many” customers arrive? Answer: It depends on INFINITY of the size of new arriving passengers. ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 47 IŞIK UNIVERSITY If the bus brings as many guests as integers, then they are welcome at Hilbert’s Hotel. How? YEL ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 48 IŞIK UNIVERSITY If the bus brings as many guests as the numbers in [0, 1], then are not enough rooms. Why? ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı 49 IŞIK UNIVERSITY ”Infinity: Hilbert’s Infinite Grand Hotel” by Deniz Karlı Challenging Question at the End of This Lecture: Can you find another set which has even larger infinity as size than the infinity of [0, 1]? 50