5.2.2. Countability of set P

Try these first

1. 1.

   What is a finite alphabet?

   Hint

   Think about letters in the English alphabet or symbols in a programming language.

2. 2.

   How many strings can you form of length 1 from an alphabet of 4 characters?

   Hint

   Count each character as one string.

3. 3.

   What does it mean for a set to be countable?

   • It can only contain finite elements.
   • It can be placed in one-to-one correspondence with the natural numbers.
   • It contains no duplicates.

   Hint

   Think about how we can organize elements.

4. 4.

   True or False: All infinite sets are uncountable.

   • True
   • False

   Hint

   Consider the definition of countability.

5. 5.

   Create a finite alphabet with four characters and list all possible strings of length 2. How many total strings can you form?

   Hint

   Use every character in combinations regardless of order.

6. 6.

   If you have a set of infinite valid programs, how can you prove that this set is countable?

   Hint

   Think about organizing programs just like you'd list books by title.