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.