6.1. Lecture No # 29: Cantor’s Diagonalization Argument

Try these first

1. 1.

   What is a countably infinite set?

   Hint

   Think about how we can list numbers.

2. 2.

   Give an example of an uncountable set.

   Hint

   Consider the type of list that can't be completed.

3. 3.

   What is the main implication of Cantor's Diagonal Argument?

   • It proves all sets are countable.
   • It shows some sets are uncountable.
   • It only applies to finite sets.

   Hint

   Think about the consequences of constructing new strings.

4. 4.

   True or False: The set of integers is countably infinite.

   • True
   • False

   Hint

   Reflect on how integers can be arranged in order.

5. 5.

   Using Cantor’s diagonalization argument, prove that the set of sequences of rational numbers is countable.

   Hint

   Think about listing each rational number as a fraction.

6. 6.

   Discuss why Cantor’s argument fails when applied to finite strings.

   Hint

   Consider the essential property of length in finite strings.