5.1.3. Enumeration of subsets Π(i)

Try these first

1. 1.

   What does it mean for a set to be countable?

   Hint

   Think about how we list numbers.

2. 2.

   List the strings in Π(1) if the alphabet is {x, y, z}.

   Hint

   What length are we considering?

3. 3.

   What is the definition of countable?

   • A set with infinite elements
   • A set that can be enumerated
   • Any standard set

   Hint

   Think about whether you can write down the elements.

4. 4.

   True or False: Every programming language has an infinite number of possible valid programs.

   • True
   • False

   Hint

   Consider the flexibility of adding more code.

5. 5.

   If we have an alphabet with wild-card symbols that can represent multiple characters, how does this affect the countability of the set of strings?

   Hint

   Think about how those wildcards change the strings.

6. 6.

   Consider the implications if we allowed strings of infinite length. How would that affect the concept of countability?

   Hint

   What is the difference between finite and infinite sequences?