Use a diagonalization argument to prove that PN the power s

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.

Solution

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*)