Chapter 5

Question 1

Domain, image

Answer 1

Let f be a function. The set of all possible first elements of the ordered pairs in f is called the domain of f and is denoted dom f . The set of all possible second elements of the ordered pairs in f is called the image of f and is denoted im f .

Question 2

(f: A → B)

Answer 2

Let f be a function and let A and B be sets. We say that f is a function from A to B provided dom f = A and im f ⊆ B. In this case, we write f: A → B. We also say that f is a mapping from A to B.

Question 3

To show (f: A → B)

Answer 3

To prove that f is a function from a set A to a set B:

1. Prove that f is a function.
2. Prove that dom f = A.
3. Prove that im f ⊆ B.

Question 4

Proposition 24.10

Answer 4

Let A and B be finite sets with |A| = a and |B| = b. The number of functions from A to B is b^a.

Question 5

(One-to-one)

Answer 5

A function f is called one-to-one provided that, whenever (x, b), (y, b) ⋲ f. we must have x = y. In other words, if x ≠ y, then f(x) ≠ f(y).

Question 6

Proving a function is one-to-one

Answer 6

To show that f is one-to-one:

1. Direct method: Suppose f(x) = f(y)…. Therefore x = y. Therefore f is one-to-one.
2. Contrapositive method: Suppose x ≠ y…. Therefore f (x) ≠ f(y). Therefore f is one-to-one.
3. Contradiction method: Suppose f(x) = f(y) but x ≠ y…. →← Therefore f is one-to-one.

Question 7

Onto

Answer 7

Let f: A → B. We say that f is onto B provided that for every b ⋲ B there is an a ⋲ A so that f(a) = b. In other words, im f = B.

Question 8

Proving a function is onto

Answer 8

To show f: A → B is onto:

1. Direct method: Let b be an arbitrary element of B. Explain how to find/construct an element a ⋲ A such that f(a) = b. Therefore f is onto.
2. Set method: Show that the sets B and im f are equal.

Question 9

Theorem 24.21

Answer 9

Let A and B be sets and let f: A → B. The inverse relation f^-1 is a function from B to A if and only if f is one-to-one and onto B.

Question 10

Bijection

Answer 10

Let f: A → B. We call f a bijection provided it is both one-to-one and onto.

Question 11

Pigeonhole Principle

Answer 11

Let A and B be finite sets and let f: A → B. If |A| > |B|, then f is not one-to-one. If |A|< |B|, then f is not onto

Question 12

Proposition 24.25

Answer 12

Let A and B be finite sets and let f: A → B. If f is a bijection, then |A| = |B|.

Question 13

Composition of functions

Answer 13

Let A, B, and C be sets and let f: A → B and g: B → C. Then the function g ℴ f is a function from A to C defined by (g ℴ f)(a) = g[f(a)] where a ⋲ A. The function g ℴ f is called the composition of g and f.

Question 14

Proof Template 22

Answer 14

Proving two functions are equal.
Let f and g be functions. To prove f = g, do the following:
1. Prove that dom f = dom g.
2. Prove that for every x in their common domain, f(x) = g(x).

Question 15

Permutation

Answer 15

Let A be a set. A permutation on A is a bijection from A to itself.