# 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}$).