6.1.6. Proof by Contradiction

Try these first

1. 1.

   What is a countable set?

   Hint

   Think about how you could list its elements.

2. 2.

   Give an example of an uncountable set.

   Hint

   Recall Cantor's diagonalization argument.

3. 3.

   What does Cantor's diagonal argument demonstrate?

   • That certain sets are countable
   • That certain sets are uncountable
   • That all sets are finite

   Hint

   Focus on the distinction between listing and counting.

4. 4.

   Is the set of all finite binary strings countable?

   • True
   • False

   Hint

   Consider how you can list finite strings.

5. 5.

   If you had a list of all binary strings ranging up to a certain length, how might Cantor's argument show that there are still strings missing?

   Hint

   Consider how flipping bits reveals unseen elements.

6. 6.

   Why can’t we use Cantor’s diagonalization for rational numbers?

   Hint

   Reflect on the definitions of rational and irrational.