Author:
Amanda Hager
Subject:
Mathematics
Material Type:
Lesson
Level:
Academic Lower Division
Provider:
University of Texas at Austin
Tags:
  • D2S2
  • Mindset
  • License:
    Creative Commons Attribution
    Language:
    English
    Media Formats:
    Text/HTML, Video

    2.6 Multiple sizes of infinity

    2.6 Multiple sizes of infinity

    Overview

    TCCNS CourseMATH 1332: Contemporary Mathematics
    UT Austin CourseM 302: Introduction to Mathematics

    Introduction

    Suggested Resources and Preparation

    Materials and Technology

    • For the instructor: Handouts with sample tables save time. 

    Prerequisite Assumptions

    • Students should be able to construct one-to-one correspondences using tables in order to show two sets have the same cardinality. 

    Overview and Student Objectives

    Lesson Length

    50 minutes

    Lesson Objectives

    Students will understand that:

    • Not all infinite sets have the same cardinality.
    • We can prove that there are more reals than naturals by proving that every two-column table corresponding naturals to reals is missing some numbers.

    Students will be able to:

    • Use diagonalization to construct a decimal number that is missing from a column of decimal numbers in a table.

    Multiple sizes of infinity

    This page is all about a single theorem: there are literally more real numbers than natural numbers. Even though there are infinitely many of both. You can watch a proof in this video, and the proof is typed out below.

    Video: Real numbers and naturals do not have the same cardinality

    The theorem

    Claim: The set of real numbers and the set of natural numbers do not have the same cardinality.

    Proof: Pretend the opposite is true, that the reals and naturals have the same cardinality. That means that there has to be a one-to-one correspondence, which looks like a two row or two column table matching naturals to reals with no leftovers and no repeats. For example, the table could look like this:

    Natural numberReal number
    1
    3.19387265...
    2
    0.71927462...
    3
    9.17283005...
    4
    1.39277362...
    5
    0.00033827...
    6
    2.28928922...
    7
    1.27222263...
    Etc.Etc.

    Supposedly this table contains every real number that exists. We will prove that isn't true.

    Let's build a number using the real numbers from our table. We will start the number with a zero and a decimal point. Then we will follow these rules for the other decimal places:

    • For the first decimal place, choose anything other than the first decimal place of the first number.
    • For the second decimal place, choose anything other than the second decimal place of the second number.
    • For the nth decimal place, choose anything other than the nth decimal place of the nth number.

    For the example table above, I will choose 0.22057514... When I typed that I was thinking "Anything but 1, anything but 1, anything but 8, anything but 8, anything but 5, anything but 8, anything but 7, anything but 5." I must put a dot-dot-dot or ellipsis after the number to indicate that we do this infinitely many times. 

    Why isn't this number on the list?

    • My number is different from the first number (3.1938734729...) because the first decimal places are different.
    • My number is different from the second number (0.7138335403...) because the second decimal places are different.
    • My number is different from the nth decimal number because the nth decimal places will be different. Guaranteed.

    Okay, conclusion: We pretended there were the same amount of naturals and reals, which implies we can put both sets into a perfect two-column table. But then we showed that the table was not perfect, that it left a number out. That means that there cannot be the same amount. In other words, the set of natural numbers and the set of real numbers do not have the same cardinality!

    Extra Challenge

    This extra fancy section is optional, in case you are curious. In this module, you learned about two different sizes of infinity. There's the "natural-numbers-size" of infinity, and now you know about the "real-numbers-size" of infinity. There are infinitely many sizes of infinity.

    The secret was viewing every decimal number as an infinitely long list of digits. Like instead of looking at 0.354354354... as a single number, we think of it as 0, 3, 5, 4, 3, 5, 4, 3, 5, 4, ... In other words, we think of individual decimal numbers as sequences. Meaning we proved this statement:

    The set of all sequences of natural numbers is bigger than the set of all natural numbers.

    Well...here's the real truth:

    • The set of all sequences of sequences of natural numbers is bigger than the set of all sequences of all natural numbers.
    • The set of all sequences of sequences of sequences of natural numbers is bigger than the set of all sequences of sequences of all natural numbers.
    • The set of all sequences of sequences of sequences of sequences of natural numbers is bigger than the set of all sequences of sequences of sequences of all natural numbers.
    • Etc. Forever.

    Quiz Questions

    Question Answer
    13
    21
    34
    41
    51

     

    Question 1

    Your friend secretly writes down a five-digit number. She tells you that the first digit is 9. Are you able to write down a five-digit number that you know for sure won't be equal to her number?

    1. Yes. Just make the first digit equal to 9.
    2. No. She didn't show me the other four digits.
    3. Yes. Just make the first digit anything but 9.
    4. No. She showed me one of her digits, so it's impossible to do now.

    Question 2

    Your friend secretly writes down TWO five-digit numbers. She tells you the first digit of the first number is 9, and the first digit of the second number is 8. Are you able to write down a five-digit number that you know for sure won't be equal to her numbers?

    1. Yes. Just make the first digit anything but 9 or 8.
    2. Yes. Just make the first digit equal to 8 or 9.
    3. No. 8 and 9 contradict each other, so it's impossible to do.
    4. No. She didn't show me the other four digits of either number.

    Question 3

    Your friend secretly writes down two five-digit numbers. She tells you the first digit of the first number is 7, and the second digit of the second number is 2. Are you able to write down a five-digit number that you know for sure won't be equal to either of her numbers?

    1. No. She gave me different digits of different numbers, which makes it too hard to do.
    2. Yes. Just make sure the first digit is equal to 7 and the second digit is equal to 2.
    3. No. Again, she did not give me enough information to make sure my number is not the same.
    4. Yes. Just make sure the first digit is not 7 and the second digit is not 2.

    Question 4

    Your friend gives you a list of three five-digit numbers, but she only reveals one digit in each:

    3????

    ?8???

    ??2??

    Which number do we know for sure will not be on her list?

    1. 42100
    2. 38297
    3. 31111
    4. 18200
    5. 38212

    Question 5

    Let's play Dodgeball! Given the beginning of this sequence from Player 1 (meaning these are Players 1's first five moves out of infinitely many moves), if you use the "winning strategy" discussed in the videos, what would you write for the first 5 places as Player 2 to ensure a win?

    X0X0X...

    00X0X...

    X0000...

    0XX00...

    X0X00...

    1. 0XXXX...
    2. X0X00...
    3. XXXXX...
    4. 0XX00...

    Homework Questions

    Question 2.6.1

    Any number where the first digit is not 6, the second digit is not 2, and the third digit is not 4 will do. We know it will be different because we've been given at least one digit of each number, so we can prove that it's different in at least one place.

    Question 2.6.2

    Any number where the third digit is not 8, the fifth digit is not 0, and the first digit is not 1 will do. We know it will be different because we've been given at least one digit of each number, so we can prove that it's different in at least one place.

    Question 2.6.3

    You are not able to this time. The third five digit number could be anything. You have no guarantees that you will have a different number from that third mystery number.

    Question 2.6.4

    As long as the tenths place of my number is not 1, I know my number will not match the first decimal number. Therefore I will make sure my tenths place is not 1. Likewise, the second digit of the second number is 7, the third digit of the third number is 0, and the fouth digit of the fourth number is 0. Therefore, I need to ensure that my second digit is not 7 and my third/fourth digits are not 0.

    Question 2.6.5

    Suppose that A and the naturals have the same cardinality. Then the two sets have a 1-1 correspondence. This correspondence takes the form of a two-column table that contains every single natural and every single number in A

    But there's a catch. We can build a number by starting with 0. and then going down the diagonal of the numbers in the A column, changing the nth digit of the nth number. If you see a 0, then you choose a 1, and if you see a 1, then you choose a 0. You build a number that is between 0 and 1 and has only 0's and 1's in its decimal expansion. This means that the number that you just built is in A. And yet the number is not anywhere on the table. We have a contradiction. We have to back all the way up to the beginning and conclude that the two sets do not have the same cardinality.

    Question 2.6.6

    Many answers here, but they are all along the line of "Imagine a set of people so big that there is a person for each and every person in this uncountably infinite set." We already know the set cannot have a 1-1 correspondence with the naturals, so this means that the people cannot possibly fit. 

    Question 2.6.7

    Mindset question. Responses vary.

    Question 2.6.1

    Your friend secretly writes three different five-digit numbers down on a piece of paper. They then give you clues: the first digit of the first number is 6, the second digit of the second number is 2, and the third digit of the third number is 4. Give a five-digit number that you know your friend didn't write down and explain how you know it will be different.

    Question 2.6.2

    Your friend secretly writes three different five-digit numbers down on a piece of paper. They then give you clues: the third digit of the first number is 8, the fifth digit of the second number is 0, and the first digit of the third number is 1. Are you able to write down a five-digit number that you know won't be on their list of numbers? Why or why not?

    Question 2.6.3

    Your friend shows you a new list of three five-digit numbers, again with only a few digits revealed:

    6????

    ?5???

    ?????

    Is it possible for you to write a number you know for certain won't be on her list? Why or why not?

    Question 2.6.4

    Here are the first four numbers in an infinitely long list of numbers:

    .123456...

    .374950...

    .780943...

    .582091...

    According to the diagonalization strategy for Dodgeball shown in the videos, give the first four digits of any decimal number that is between 0 and 1 and is definitely not on this infinitely long list. Explain your answer.

    Question 2.6.5

    Let \(A\) be the set of all real numbers between 0 and 1 that have only 0's and 1's in their decimal expansions. This means that 0.100100100... is in \(A\) but 0.100200100... is not. Prove that \(A\) and the set of natural numbers do not have the same cardinality.

    Question 2.6.6

    Create a collection of people so that it would be impossible for the night manager to give each person a room in Hilbert's Hotel (the magical hotel with one room for every natural number).

    Question 2.6.7

    1. In this homework assignment, describe one error in thinking that you made while solving one of the problems. 
    2. Write a paragraph about how you felt when you made that error, and what your knee-jerk reaction was.
    3. Write a paragraph about how you recovered from that error in order to answer the question. If you couldn't answer the question, then describe one or two things that you could do to pick yourself up and try again, with support perhaps.