Problem 3. Let us say that a nonempty set B is countable if you can list (possib

Question

Problem 3. Let us say that a nonempty set B is countable if you can list (possibly with repetitions) its elements B (a1, a2, a3, more formally, there is a surjective function f from N to B. We'll say that the empty set is also countable. A set is uncountable if it is not countable. 3.1 Prove that any subset A of a countable set B is countable. 3.2 Fix an alphabet SC. Prove that there are countably many finite languages over E. 3.3 Fix an alphabet E. Prove that there are uncountably man infinite languages over

Explanation / Answer

3.1 - Proof of subset of countable set is countable-

Without loss of generality we may assume that A is an infinite subset of N. We define h : N ? A as follows. Let h(1) = min A. Since A is infinite, A is nonempty and so h() is well-defined. Having defined h(n ? 1), we define h(n) = min(A {h(1),... ,h(n?1)}). Again since A is infinite the set (A {h(1),... ,h(n ? 1)}) is nonempty, h(n) is well-defined. We claim that h is a bijection. We first show that h is an injection. To see this we prove that h(n + k) > h(n) for all n,k ? N. By construction h(n + 1) > h(n) 11 for all n ? N. Then setting B = {k ? N| h(n + k) > h(n)} we see that 1 ? B and if h(n + (k ? 1)) > h(n), then h(n + k) > h(n + (k ? 1)) > h(n). Consequently, B = N. Since n was arbitrary, h(n + k) > h(n) for all n,k ? N. Now taking distinct n,m ? N we may assume that m > n so that m = n + k. By the above h(m) = h(n + k) > h(n) proving that h is an injection. Next we show that h is a surjection. To do this we first show that h(n) ? n. Let C = {n ? N| h(n) ? n}. Clearly, 1 ? C. If k ? C, then h(k + 1) > h(k) ? n so that h(k + 1) ? k + 1. Hence k + 1 ? C and by the principle of mathematical induction C = N. Now take n0 ? A. We have to show that h(m0) = n0 for some m0 ? N. If n0 = 1, then m0 = 1. So assume that n0 ? 2. Consider the set D = {n ? A| h(n) ? n0}. Since h(n0) ? n0, the set D is nonempty and by the well-ordering principle D has a minimum. Let m0 = min D. If m0 = 1, then h(m0) = min A ? n0 ? h(m0) and hence h(m0) = n0. So we may also assume that n> min A. Then h(m0) ? n0 > h(m0 ? 1) > ... > h(1) in view of definitions of m0 and h. Since h(m0) = min(A {h(1),... ,h(m0 ? 1)}) and n0 ? A {h(1),... ,h(m0 ? 1)} and h(m0) ? n0, it follows that h(m0) = n0. This proves that h is also a surjection.

Hence Proved.

3.2- countably finite

A finite language can be written down. That is, you can just concatenate all the words in the language into one string (with a special separator symbol $). So there is a one-to-one map from finite languages over {a, b} to strings over {a, b, $}. There are only countably many strings, so there are countably many finite languages

3.3 uncountably infinite -

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

A countably infinite set has countably infinitely many finite subsets, so there are countably infinitely many finite languages over ?.

A countably infinite set has uncountably many subsets, so there are uncountably many languages over ?

That N has uncountably many subsets if easily shown by a form of Cantor

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.