Chapter 10

Chapter 9

Chapter 8

Chapter 7

Chapter 6

Chapter 5

Chapter 4

Chapter 3

Chapter 2

Chapter 1

Chapter 0

1. Write a short informal description of each set.
    a. {1, 3, 5, 7,...} The odd natural numbers.
    b. {...,-4, -2, 0, 2, 4} The even integers.
    c. {n | n = 2m for some m in N} The even natural numbers.
    d. {n | n = 2m for some m in N, and n = 3k for some k in N} All positive multiples of 6
    e. {w | w is a string of 0s and 1s and w equals the reverse of w} All binary palindromes
    f. {n | n is an integer and n = n + 1} The empty set.

2. Write formal descriptions of the following sets

    a. The set containing the numbers 1, 10, 100: {1, 10, 100}

    b. The set containing all integers greater than 5: {n ∈ Z | n > 5}

    c. The set containing all natural numbers that are less than 5: {n ∈ N |n < 5}

    d. The set containing the string aba: {aba}

    e. The set containing the empty string: {ε}

    f. The set containing nothing: ∅

3. Let A be the set {x, y, z} and B be the set {x, y}.

    a. Is A a subset of B?
          No.

    b. Is B a subset of A?
          Yes.

    c. What is A ∪ B?
        A ∪ B = {x, y, z}

    d. What is A ∩ B?
        A ∩ B = {x, y}

    e. What is A x B?
        A x B = {(x, x), (x, y), (y, x), (y, y), (z, x), (z, y)}

    f. What is the power set of B?
        P(B) = {∅, {x}, {y}, {x, y}}

4. If A has a elements and B has b elements, how many elements are in A x B?
    For each element in A there will be b ordered pairs, so there will be a x b elements.

5. If C is a set with c elements, how many elements are in the power set of C? Explain your answer.
    If |C| = c then |P(C)| = 2^c. Although there are many proofs or explanations of this result, including Pascal’s Triangle and the binomial expansion, my favorite (and potentially the simplest) is to compare the elements of P(C) to the binary strings of length c. First, order each of the elements of C so that each has an ordinal position in the set. We can then describe each element of P(C) uniquely by a binary string of length c where each bit corresponds to the element with the same ordinal position. A value of 1 indicates that the corresponding element is in the subset while 0 indicates that it is not. Since there is a one-to-one correspondence between the elements of P(C) and all binary strings of length c, there must be 2c elements in P(C).

6. Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function f : X → Y and the binary function g : X × Y → Y are described in the following tables.

n	f(n)
1	6
2	7
3	6
4	7
5	6

g	6	7	8	9	10
1	10	10	10	10	10
2	7	8	9	10	6
3	7	7	8	8	9
4	9	8	7	6	10
5	6	6	6	6	6

  
    a. What is the value of f(2)?
        7
    b. What are the range and domain of f?
        As given in the definition of f, the domain is X and the range is Y.
    c. What is the value of g(2, 10)?
        6
    d. What are the range and domain of g?
        Per the definition, the domain is X x Y, and the range is Y.
    e. What is the value of g(4, f(4))?
        g(4, 7) = 8

7. For each part, give a relation that satisfies the condition.
    a. Reflexive and symmetric but not transitive
        Non empty intersection on the collection of all non-empty sets. Mathematically, define R : S × S → {true, false} where S is the collection of all non-empty sets by R(A, B) ≡ A ∩ B ≠ ∅ where A, B ∈ S.
    b. Reflexive and transitive but not symmetric
        The well-known relation ≤ on the real numbers satisfies the condition.
    c. Symmetric and transitive but not reflexive
        On any set A, define R by R ≡ false. Since the relation does not have to be reflexive, the relation can always be false and will vacuously be symmetric and transitive.

About the blog

This page will hold extended sets of answers to the book Introduction to the Theory of Computation, 2E, by Michael Sipser. This book is commonly used in Computational Theory classes on a university level. The text is a good one, but many of the problems are challenging and time consuming if you don't first know how to approach the problem. My goal is to provide you with an extended answer set that can be used as a reference as you work through problems.
The set will be incomplete to start but I hope eventually to have a complete reference to the second edition of the book.
If you have any answers that are not here, please feel free to contribute.