3
$\begingroup$

I'm trying to understand why the set of finite languages over a finite alphabet is countable but the set of languages over a finite alphabet is uncountable. I'm guessing its because the sentences represented by the finite alphabet is infinitely countable and corresponds to a natural number. Thus the set of finite languages over a finite alphabet can be counted by listing them in increasing size (similar to the proof of how the sentences over a finite alphabet are countable). However, if the languages are NOT finite, then I'm assuming Cantor's Diagonalization argument should be used to prove by contradiction that it is uncountable. Am I on the right track? Also, could someone please clear up why Cantor's Diagonalization will not work to contradict the first one but will work to contradict the second one? Is it because in the first one, the languages are finite thus they can be represented by natural numbers so nothing is missed but when they are infinite you can always find a diagonal (flipping the bits) that is not in the list?

Thanks in advance, I thought I understood it completely but I seem to keep fighting the idea of it in my head.

1 Answers 1

10

Let $\Sigma$ be a finite, non-empty alphabet. $\Sigma^*$, the set of words over $\Sigma$, is then countably infinite. The languages over $\Sigma$ are by definition simply the subsets of $\Sigma^*$.

  1. A countably infinite set has countably infinitely many finite subsets, so there are countably infinitely many finite languages over $\Sigma$.

  2. A countably infinite set has uncountably many subsets, so there are uncountably many languages over $\Sigma$.

You really don’t have to look at languages per se at all. There is a bijection between $\Sigma^*$ and $\Bbb N$, so just prove that $\Bbb N$, the prototypical countably infinite set, has $\omega$ (or if you prefer $\aleph_0$) finite subsets and uncountably many subsets altogether.

That $\Bbb N$ has uncountably many subsets if easily shown by a form of Cantor’s argument. Suppose that $\{A_0,A_1,\dots\}$ is any countable family of subsets of $\Bbb N$. Now let $S=\{n\in\Bbb N:n\notin A_n\}$. Then for each $n\in\Bbb N$ we have $n\in A_n$ iff $n\notin S$, so $S\ne A_n$. Thus, $\{A_0,A_1,\dots\}$ is not a complete list of the subsets of $\Bbb N$, and $\wp(\Bbb N)$ must be uncountable.

No diagonalization is possible in the case of the finite subsets because we demonstrably can list them all:

$\begin{array}{c|cc} \text{Row}&\text{Sets}\\ \hline -1&\varnothing\\ &\color{red}{0}\\ 0&\{0\}\\ &\color{red}{1}\\ 1&\{1\}&\{0,1\}\\ &\color{red}{2}&\color{red}{3}\\ 2&\{2\}&\{0,2\}&\{1,2\}&\{0,1,2\}\\ &\color{red}{4}&\color{red}{5}&\color{red}{6}&\color{red}{7}\\ 3&\{3\}&\{0,3\}&\{1,3\}&\{0,1,3\}&\{2,3\}&\{0,2,3\}&\{1,2,3\}&\{0,1,2,3\}\\ &\color{red}{8}&\color{red}{9}&\color{red}{10}&\color{red}{11}&\color{red}{12}&\color{red}{13}&\color{red}{14}&\color{red}{15} \end{array}$

The organizing principle here is that Row $n$ is obtained by adding the element $n$ to each of the sets in the earlier rows. Thus, all subsets of $\{0,\dots,n\}$ appear in rows $-1,\dots,n$. We can clearly enumerate all of these finite subsets using the numbers in red immediately below them.

  • 0
    @BrianM.Scott:Since a coin has two faces and it's certain that you can't lie an head and tail together.Is it possible to find an uncounted one while considering both the faces of a paper where one denotes the head and other denotes the tail?2015-05-27