6.1.2. Countably Infinite Sets

Try these first

1. 1.

   What is a countably infinite set?

   Hint

   Think of how integers relate to naturals.

2. 2.

   Can you list an example of a countably infinite set?

   Hint

   What can be matched with 1, 2, 3, etc.?

3. 3.

   What defines a countably infinite set?

   • It can't be listed
   • It has one-to-one correspondence with naturals
   • It includes irrationals

   Hint

   Consider counting the elements.

4. 4.

   True or False: The set of binary strings of infinite length is countable.

   • True
   • False

   Hint

   Remember Cantor's argument.

5. 5.

   Using Cantor's argument, prove that the decimal representation of any irrational number is infinite and does not repeat.

   Hint

   Focus on how equating with rationals fails.

6. 6.

   Suppose you are asked to list the set of all real numbers. Describe why this is impossible.

   Hint

   Connect to the earlier discussions about the diagonal.