6.1.5. Cantor’s Diagonalization Argument

Try these first

1. 1.

   Define a countably infinite set. Give an example.

   Hint

   Remember what it means to list elements in a sequence.

2. 2.

   What distinguishes uncountable sets from countable sets?

   Hint

   Think about the definitions of countability.

3. 3.

   What is the main purpose of Cantor's diagonalization argument?

   • To show that all infinities are equal.
   • To demonstrate the uncountability of certain sets.
   • To establish the finiteness of binary strings.

   Hint

   Think about what Cantor aimed to show with his argument.

4. 4.

   True or False: The set of all integers is uncountably infinite.

   • True
   • False

   Hint

   Consider how integers can be listed.

5. 5.

   What would happen if you tried to apply Cantor's diagonal argument to the set of rational numbers? Explain why it would fail.

   Hint

   Think about the characteristics of rational versus irrational numbers.

6. 6.

   Create a new string using Cantor's diagonalization method based on the binary strings: 000, 111, 010, 110. What are the implications?

   Hint

   Focus on the method of flipping bits along the diagonal.