0’s and 1’s has important implications. But before we explore these implications,
we need to review some results from set theory.
Some sets are finite, but most of the interesting sets (and languages) are
infinite. For infinite sets, we distinguish between sets that are countable and sets
that are uncountable. A set is said to be countable if its elements can be put into
a one-to-one correspondence with the positive integers. By this we mean that the
elements of the set can be written in some order, say, x 1 , x 2 , x 3 ,…, so that every
element of the set has some finite index. For example, the set of all even integers
can be written in the order 0, 2, 4,…. Since any positive integer 2n occurs in
position n +1, the set is countable. This should not be too surprising, but there
are more complicated examples, some of which may seem counterintuitive. Take
the set of all quotients of the form p/q, where p and q are positive integers. How
should we order this set to show that it is countable? We cannot use the sequence
because then would never appear. This does not imply that the set is
uncountable; in this case, there is a clever way of ordering the set to show that it
is in fact countable. Look at the scheme depicted in Figure 10.17, and write
down the element in the order encountered following the arrows. This gives us
Here the element occurs in the seventh place, and every element has some
position in the sequence. The set is therefore countable.
Figure 10.17
We see from this example that we can prove that a set is countable if we can