Question
If the languages A and B are countable, what can you say about (AB)^R and (A ? B)^R ?
Explanation / Answer
7. Countable Sets Definition. A set S is countable if |S| = |Num|. A set S is at most countable if |S| = |Num|. Thus a set S is countable if there is a one-to-one mapping of Num onto S, that is, if S is the range of an infinite one-to-one sequence. Theorem. An infinite subset of a countable set is countable. Proof. Let A be a countable set, and let B ? A be infinite. There is an infinite one-to-one sequence n0-inf, whose range is A. We let b0 = ak0, where k0 is the least k such that ak ? B. Having constructed bn, we let bn + 1 = akn + 1, where kn + 1 is the least k such that ak ? B and ak ? bi for every i = n. Such k exists since it is easily seen that B = {bn | n ? Num} and that n0-inf is one-to-one. Thus B is countable. ? Corollary. A set is at most countable if and only if it is either finite or countable. The range of an infinite one-to-one sequence is countable. If n0-inf is an infinite sequence which is not one-to-one, then the set {an}n0-inf may be finite (e.g., this happens if it is a constant sequence). However, if the range is infinite, then it is countable. Theorem. The range of an infinite sequence n0-inf is at most countable, i.e., either finite or countable. (In other words, the image of a countable set under any mapping is at most countable.) Proof. By recursion, we construct a sequence (with either finite or infinite domain) which is one-to-one and has the same range as n0-inf. We let b0 = a0, and, having constructed bn, we let bn + 1 = akn + 1, where kn + 1 is the least k such that ak ? bi for all i = n. (If no such k exists, then we consider the finite sequence .) The sequence thus constructed is one-to-one and its range is {an}n0-inf. ? One should realize that not all properties of size carry over from finite sets to the infinite case. For instance, a countable set S can be decomposed into two disjoint parts, A and B, such that |A| = |B| = |S|; that is inconceivable if S is finite (unless S = Ø). Namely, consider the set E = {2k | k ? Num} of all even numbers, and the set O = {2k + 1 | k ? Num} of all odd numbers. Both E and O are infinite, hence countable; thus we have |Num| = |E| = |O| while Num = E ? O and E n O = Ø. We can do even better. Let pn denote the nth prime number (i.e., p0 = 2, p1 = 3, etc.). Let S0 = {2k | k ? Num}, S1 = {3k | k ? Num}, …, Sn = {pnk | k ? Num}, …. The sets Sn (n ? Num) are mutually disjoint countable subsets of Num. Thus we have Num ? ?n=0 to infinity Sn, where |Sn| = |Num| and the Sns are mutually disjoint. The following two theorems show that simple operations applied to countable sets yield countable sets. Theorem. The union of two countable sets is a countable set. Proof. Let A = {an | n ? Num} and B = {bn | n ? Num} be countable. We construct a sequence n0-inf as follows: c2k = akand c2k + 1 = bk for all k ? Num. Then A ? B = {cn | n ? Num} and since it is infinite, it is countable. ? Corollary. The union of a finite system of countable sets is countable. Proof. By induction (on the size of the system). ? Theorem. If A and B are countable, then A × B is countable. Proof. It suffices to show that |Num × Num| = |Num|, i.e., to construct either a one-to-one mapping of Num × Num onto Num or a one-to-one sequence with range Num × Num. Consider the function f(k, n) = 2k · (2n + 1) - 1. It is easy to verify that f is one-to-one and that the range of f is Num. ? Corollary. The cartesian product of a finite number of countable sets is countable. Consequently, Numm is countable, for every m > 0. Theorem. Let be a countable system of at most countable sets, and let be a system of enumerations of An; i.e., for each n ? Num, an = is an infinite sequence, and An = {an(k) | k ?Num}. Then ?n=0 to infinity An is at most countable. Proof. Define f : Num × Num mapsto ?n=0 to infinity An by f(n, k) = an(k). f maps Num × Num onto ?n=0 to infinity An, so the latter is at most countable. ? As a corollary of this result we can now prove Theorem. If A is countable, then the set Seq (A) of all finite sequences of elements of A is countable. Proof. It is enough to prove the theorem for A = Num. As Seq (Num) = ?n=0 to infinity Numn, the theorem follows if we can produce a sequence of enumerations of Numn. We do that by recursion. Let g be a one-to-one mapping of Num onto Num × Num. Define recursively a1(i) = for all i ? Num; an + 1(i) = where g(i)=(i1, i2) and = an(i1),for all i ? Num. The idea is to let an + 1(i) be the (n + 1)-tuple resulting from the concatenation of the (i1)th n-tuple (in the previously constructed enumeration of n-tuples, an) with i2. An easy proof by induction shows that an is onto Numn, for all n = 1, and therefore ?n=1 to infinity Numn is countable. Since Num0 = {}, ?n=0 to infinity Numn is also countable. ? Corollary. The set of all finite subsets of a countable set is countable. Proof. The function F defined by F() = {a0, …, an - 1} maps the countable set Seq (A) onto the set of all finite subsets of A. ? Other useful results about countable sets are the following. Theorem. The set of all integers Z and the set of all rational numbers Q are countable. Proof. Z is countable because it is the union of two countable sets: Z = {0, 1, 2, 3, …} ? {-1, -2, -3, …}. Q is countable because the function f : Z × (Z - {0}) mapsto Q defined by f(p, q) = p / q maps a countable set