Homework 3

Due Monday, 10/16:

  1. Let A = \{ 0, 1, 2, 3 \} and B = \{ 0, 1 \}^2 (the set of all ordered pairs of 0s and 1s). Find a bijection between A and B.
  2. Let A, B, and C be sets. if f : A \to B and g : B \to C are functions, the composition g \circ f : A \to C is defined as (g \circ f)(x) = g(f(x)). Show the following:
    • If f : A \to B and g : B \to C are injections, then g \circ f : A \to C is an injection.
    • If f : A \to B and g : B \to C are surjections, then g \circ f : A \to C is a surjection.
    • If f : A \to B is a bijection, then g : B \to A defined by g(f(x)) = x is a bijection (g is called the inverse of f).
  3. Suppose our universe is \mathbb{N}, P(x, y) is x < y (note it’s not less than or equal to), and Q(x, y, z) is x + y = z. Determine if the following statements are true or false, and explain why:
    • \exists x P(x, x)
    • \exists x \forall y P(x, y)
    • \forall x \forall y \exists z Q(x, y, z)
    • \forall x \exists y \lnot P(x, y)
  4. Find the negation of the following statement: \forall x \forall y (\lnot P(x, y) \vee P(y, x)). (Hint: use the law of double negation: \lnot \lnot P(x, y) \equiv P(x, y).) Determine which statement (the original or its negation) is true if the universe is \mathbb{Z} and P(x, y) is “x – y is an even integer”.

Suggested (practice) problems (do not turn these in, but you should do them for practice):

Section 1.4 (page 53) #1-3, 8, 11-16, 50, 51

Section 1.5 (page 64) #1-2, 9, 26-32, 39-42

Challenge: Suppose our universe is \mathbb{Q} and P(x, y) is x < y. Write a statement that is true in this universe that is not true in the universe \mathbb{Z}. (Hint: in the integers, there is no number between 0 and 1. But this is not true in \mathbb{Q}).