Use a diagonalization argument to prove that P(N) - the power set of the natural

Question

Use a diagonalization argument to prove that P(N) - the power set of the natural numbers - is uncountable. A complete (undirected) graph on n vertices - commonly denoted by K_n - has an edge between every pair of vertices. Prove by mathematical induction that |E| = n(n-1)/2. Give a recursive definition for the reversal operator on words, W^R (the word in reverse order). Prove by mathematical induction that (uv)^R = (uv)^R where u and v are words over some alphabet, and R is the reversal operator from the previous problem. Let X = {ab, ba) and Y = {lambda, a, b}. List the strings of length 3 in the set X*Y*. Let L_1 {aaaa}*, L_2 = {a, b} {a, b} {a, b}, and L_3 = (L_2)*. Describe the strings that are in the languages L_2, L_3, and L_1 intersection L_3. A regular expression can be defined recursively as (a) Base Case: basic elements lambda and a sigma (i.e. symbols in the alphabet), (b) Recursive Step: the concatenation, union, or Kleene-star of regular expressions, (c) Closure: starting with basic elements, the application of the recursive step a finite number of times is also a regular expression. Give a regular expression for the set of strings over {a, b, c} in which the total number of b's and c's is three. Give a regular expression for the set of strings over {a, b} with an even number of a's or an odd number of b's.

Explanation / Answer

1) Cantor's Theorem also called the diagonalisation argument, the diagonal slash argument or the diagonal method, states that for any set A there is no surjective function AP(A). With A=Nthis implies that P(N) is not countable.

2) If n = 1, zero edges are required, and 1(1 0)/2 = 0. Assume that a complete graph with k vertices has k(k 1)/2. When we add the (k + 1)st vertex, we need to connect it to the k original vertices, requiring k additional edges. We will then have k(k 1)/2 + k = (k + 1)((k + 1) 1)/2 vertices. This is the proof.

5) L = {aba,abb,ab,baa,bab,ba,ababaa,ababa,babaa,babab,abab,baba, ...}

6) Strings in L1 = {epsilon,aaaa,aaaaaaaa,aaaaaaaaaaaa,...}

Strings in L2 = {aaa,abb,aab,bbb,baa,bba,aba,bab, ... }

Strings in L1 intersection L3 = {epsilon }

7) (a*(b+c)(b+c)(b+c))+((b+c)a*(b+c)(b+c))+((b+c)(b+c)(b+c)a*)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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