Skip to main content

Section 1.2 Sets and Functions

Subsection 1.2.1 Set Theory

A set is a well-defined collection of objects; that is, it is defined in such a manner that we can determine for any given object \(x\) whether or not \(x\) belongs to the set. The objects that belong to a set are called its elements or members. We will denote sets by capital letters, such as \(A\) or \(X\text{;}\) if \(a\) is an element of the set \(A\text{,}\) we write \(a \in A\text{.}\)

A set is usually specified either by listing all of its elements inside a pair of braces or by stating the property that determines whether or not an object \(x\) belongs to the set. We might write

\begin{equation*} X = \{ x_1, x_2, \ldots, x_n \} \end{equation*}

for a set containing elements \(x_1, x_2, \ldots, x_n\) or

\begin{equation*} X = \{ x :x \text{ satisfies }{\mathcal P}\} \end{equation*}

if each \(x\) in \(X\) satisfies a certain property \({\mathcal P}\text{.}\) For example, if \(E\) is the set of even positive integers, we can describe \(E\) by writing either

\begin{equation*} E = \{2, 4, 6, \ldots \} \quad \text{or} \quad E = \{ x : x \text{ is an even integer and } x \gt 0 \}\text{.} \end{equation*}

We write \(2 \in E\) when we want to say that 2 is in the set \(E\text{,}\) and \(-3 \notin E\) to say that \(-3\) is not in the set \(E\text{.}\)

Some of the more important sets that we will consider are the following:

\begin{gather*} {\mathbb N} = \{n: n \text{ is a natural number}\} = \{1, 2, 3, \ldots \};\\ {\mathbb Z} = \{n : n \text{ is an integer} \} = \{\ldots, -1, 0, 1, 2, \ldots \};\\ {\mathbb Q} = \{r : r \text{ is a rational number}\} = \{p/q : p, q \in {\mathbb Z} \text{ where } q \neq 0\};\\ {\mathbb R} = \{ x : x \text{ is a real number} \};\\ {\mathbb C} = \{z : z \text{ is a complex number}\}\text{.} \end{gather*}

We can find various relations between sets as well as perform operations on sets. A set \(A\) is a subset of \(B\text{,}\) written \(A \subset B\) or \(B \supset A\text{,}\) if every element of \(A\) is also an element of \(B\text{.}\) For example,

\begin{equation*} \{4,5,8\} \subset \{2, 3, 4, 5, 6, 7, 8, 9 \} \end{equation*}

and

\begin{equation*} {\mathbb N} \subset {\mathbb Z} \subset {\mathbb Q} \subset {\mathbb R} \subset {\mathbb C}\text{.} \end{equation*}

Trivially, every set is a subset of itself. A set \(B\) is a proper subset of a set \(A\) if \(B \subset A\) but \(B \neq A\text{.}\) If \(A\) is not a subset of \(B\text{,}\) we write \(A \notsubset B\text{;}\) for example, \(\{4, 7, 9\} \notsubset \{2, 4, 5, 8, 9 \}\text{.}\) Two sets are equal, written \(A = B\text{,}\) if we can show that \(A \subset B\) and \(B \subset A\text{.}\)

It is convenient to have a set with no elements in it. This set is called the empty set and is denoted by \(\emptyset\text{.}\) Note that the empty set is a subset of every set.

To construct new sets out of old sets, we can perform certain operations: the union \(A \cup B\) of two sets \(A\) and \(B\) is defined as

\begin{equation*} A \cup B = \{x : x \in A \text{ or } x \in B \}; \end{equation*}

the intersection of \(A\) and \(B\) is defined by

\begin{equation*} A \cap B = \{x : x \in A \text{ and } x \in B \}\text{.} \end{equation*}

If \(A = \{1, 3, 5\}\) and \(B = \{ 1, 2, 3, 9 \}\text{,}\) then

\begin{equation*} A \cup B = \{1, 2, 3, 5, 9 \} \quad \text{and} \quad A \cap B = \{ 1, 3 \}\text{.} \end{equation*}

We can consider the union and the intersection of more than two sets. In this case we write

\begin{equation*} \bigcup_{i = 1}^{n} A_{i} = A_{1} \cup \ldots \cup A_n \end{equation*}

and

\begin{equation*} \bigcap_{i = 1}^{n} A_{i} = A_{1} \cap \ldots \cap A_n \end{equation*}

for the union and intersection, respectively, of the sets \(A_1, \ldots, A_n\text{.}\)

When two sets have no elements in common, they are said to be disjoint; for example, if \(E\) is the set of even integers and \(O\) is the set of odd integers, then \(E\) and \(O\) are disjoint. Two sets \(A\) and \(B\) are disjoint exactly when \(A \cap B = \emptyset\text{.}\)

Sometimes we will work within one fixed set \(U\text{,}\) called the universal set. For any set \(A \subset U\text{,}\) we define the complement of \(A\text{,}\) denoted by \(A'\text{,}\) to be the set

\begin{equation*} A' = \{ x : x \in U \text{ and } x \notin A \}\text{.} \end{equation*}

We define the difference of two sets \(A\) and \(B\) to be

\begin{equation*} A \setminus B = A \cap B' = \{ x : x \in A \text{ and } x \notin B \}\text{.} \end{equation*}
Example 1.1.

Let \({\mathbb R}\) be the universal set and suppose that

\begin{equation*} A = \{ x \in {\mathbb R} : 0 \lt x \leq 3 \} \quad \text{and} \quad B = \{ x \in {\mathbb R} : 2 \leq x \lt 4 \}\text{.} \end{equation*}

Then

\begin{align*} A \cap B & = \{ x \in {\mathbb R} : 2 \leq x \leq 3 \}\\ A \cup B & = \{ x \in {\mathbb R} : 0 \lt x \lt 4 \}\\ A \setminus B & = \{ x \in {\mathbb R} : 0 \lt x \lt 2 \}\\ A' & = \{ x \in {\mathbb R} : x \leq 0 \text{ or } x \gt 3 \}\text{.} \end{align*}
Proof.

We will prove (1) and (3) and leave the remaining results to be proven in the exercises.

(1) Observe that

\begin{align*} A \cup A & = \{ x : x \in A \text{ or } x \in A \}\\ & = \{ x : x \in A \}\\ & = A \end{align*}

and

\begin{align*} A \cap A & = \{ x : x \in A \text{ and } x \in A \}\\ & = \{ x : x \in A \}\\ & = A\text{.} \end{align*}

Also, \(A \setminus A = A \cap A' = \emptyset\text{.}\)

(3) For sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\)

\begin{align*} A \cup (B \cup C) & = A \cup \{ x : x \in B \text{ or } x \in C \}\\ & = \{ x : x \in A \text{ or } x \in B, \text{ or } x \in C \}\\ & = \{ x : x \in A \text{ or } x \in B \} \cup C\\ & = (A \cup B) \cup C\text{.} \end{align*}

A similar argument proves that \(A \cap (B \cap C) = (A \cap B) \cap C\text{.}\)

Proof.

(1) If \(A \cup B = \emptyset\text{,}\) then the theorem follows immediately since both \(A\) and \(B\) are the empty set. Otherwise, we must show that \((A \cup B)' \subset A' \cap B'\) and \((A \cup B)' \supset A' \cap B'\text{.}\) Let \(x \in (A \cup B)'\text{.}\) Then \(x \notin A \cup B\text{.}\) So \(x\) is neither in \(A\) nor in \(B\text{,}\) by the definition of the union of sets. By the definition of the complement, \(x \in A'\) and \(x \in B'\text{.}\) Therefore, \(x \in A' \cap B'\) and we have \((A \cup B)' \subset A' \cap B'\text{.}\)

To show the reverse inclusion, suppose that \(x \in A' \cap B'\text{.}\) Then \(x \in A'\) and \(x \in B'\text{,}\) and so \(x \notin A\) and \(x \notin B\text{.}\) Thus \(x \notin A \cup B\) and so \(x \in (A \cup B)'\text{.}\) Hence, \((A \cup B)' \supset A' \cap B'\) and so \((A \cup B)' = A' \cap B'\text{.}\)

The proof of (2) is left as an exercise.

Example 1.4.

Other relations between sets often hold true. For example,

\begin{equation*} ( A \setminus B) \cap (B \setminus A) = \emptyset\text{.} \end{equation*}

To see that this is true, observe that

\begin{align*} ( A \setminus B) \cap (B \setminus A) & = ( A \cap B') \cap (B \cap A')\\ & = A \cap A' \cap B \cap B'\\ & = \emptyset\text{.} \end{align*}

Subsection 1.2.2 Cartesian Products and Mappings

Given sets \(A\) and \(B\text{,}\) we can define a new set \(A \times B\text{,}\) called the Cartesian product of \(A\) and \(B\text{,}\) as a set of ordered pairs. That is,

\begin{equation*} A \times B = \{ (a,b) : a \in A \text{ and } b \in B \}\text{.} \end{equation*}
Example 1.5.

If \(A = \{ x, y \}\text{,}\) \(B = \{ 1, 2, 3 \}\text{,}\) and \(C = \emptyset\text{,}\) then \(A \times B\) is the set

\begin{equation*} \{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3) \} \end{equation*}

and

\begin{equation*} A \times C = \emptyset\text{.} \end{equation*}

We define the Cartesian product of \(n\) sets to be

\begin{equation*} A_1 \times \cdots \times A_n = \{ (a_1, \ldots, a_n): a_i \in A_i \text{ for } i = 1, \ldots, n \}\text{.} \end{equation*}

If \(A = A_1 = A_2 = \cdots = A_n\text{,}\) we often write \(A^n\) for \(A \times \cdots \times A\) (where \(A\) would be written \(n\) times). For example, the set \({\mathbb R}^3\) consists of all of 3-tuples of real numbers.

Subsets of \(A \times B\) are called relations. We will define a mapping or function \(f \subset A \times B\) from a set \(A\) to a set \(B\) to be the special type of relation where each element \(a \in A\) has a unique element \(b \in B\) such that \((a, b) \in f\text{.}\) Another way of saying this is that for every element in \(A\text{,}\) \(f\) assigns a unique element in \(B\text{.}\) We usually write \(f:A \rightarrow B\) or \(A \stackrel{f}{\rightarrow} B\text{.}\) Instead of writing down ordered pairs \((a,b) \in A \times B\text{,}\) we write \(f(a) = b\) or \(f : a \mapsto b\text{.}\) The set \(A\) is called the domain of \(f\) and

\begin{equation*} f(A) = \{ f(a) : a \in A \} \subset B \end{equation*}

is called the range or image of \(f\text{.}\) We can think of the elements in the function's domain as input values and the elements in the function's range as output values.

Example 1.6.

Suppose \(A = \{1, 2, 3 \}\) and \(B = \{a, b, c \}\text{.}\) In Figure 1.7 we define relations \(f\) and \(g\) from \(A\) to \(B\text{.}\) The relation \(f\) is a mapping, but \(g\) is not because \(1 \in A\) is not assigned to a unique element in \(B\text{;}\) that is, \(g(1) = a\) and \(g(1) = b\text{.}\)

Two sets of ovals, A and B, relating 1, 2, 3 to a, b, c. The first mapping, f, sends 1 to b and 2 and 3 to c. The second relation, g, sends 1 to a and b, 2 to c, and 3 to a
Figure 1.7. Mappings and relations

Given a function \(f : A \rightarrow B\text{,}\) it is often possible to write a list describing what the function does to each specific element in the domain. However, not all functions can be described in this manner. For example, the function \(f: {\mathbb R} \rightarrow {\mathbb R}\) that sends each real number to its cube is a mapping that must be described by writing \(f(x) = x^3\) or \(f:x \mapsto x^3\text{.}\)

Consider the relation \(f : {\mathbb Q} \rightarrow {\mathbb Z}\) given by \(f(p/q) = p\text{.}\) We know that \(1/2 = 2/4\text{,}\) but is \(f(1/2) = 1\) or \(2\text{?}\) This relation cannot be a mapping because it is not well-defined. A relation is well-defined if each element in the domain is assigned to a unique element in the range.

If \(f:A \rightarrow B\) is a map and the image of \(f\) is \(B\text{,}\) i.e., \(f(A) = B\text{,}\) then \(f\) is said to be onto or surjective. In other words, if there exists an \(a \in A\) for each \(b \in B\) such that \(f(a) = b\text{,}\) then \(f\) is onto. A map is one-to-one or injective if \(a_1 \neq a_2\) implies \(f(a_1) \neq f(a_2)\text{.}\) Equivalently, a function is one-to-one if \(f(a_1) = f(a_2)\) implies \(a_1 = a_2\text{.}\) A map that is both one-to-one and onto is called bijective.

Example 1.8.

Let \(f:{\mathbb Z} \rightarrow {\mathbb Q}\) be defined by \(f(n) = n/1\text{.}\) Then \(f\) is one-to-one but not onto. Define \(g : {\mathbb Q} \rightarrow {\mathbb Z}\) by \(g(p/q) = p\) where \(p/q\) is a rational number expressed in its lowest terms with a positive denominator. The function \(g\) is onto but not one-to-one.

Given two functions, we can construct a new function by using the range of the first function as the domain of the second function. Let \(f : A \rightarrow B\) and \(g : B \rightarrow C\) be mappings. Define a new map, the composition of \(f\) and \(g\) from \(A\) to \(C\text{,}\) by \((g \circ f)(x) = g(f(x))\text{.}\)

Two sets of ovals, A and B, relating 1, 2, 3 to a, b, c and a, b, c to X, Y, Z. The first mapping, f, sends 1 to b, 2 2 to c, and 3 to a. The second relation, g, sends a and b to Z and c to X. The bottom map, g circle f, sends 1 and 3 to Z and 2 to X.
Figure 1.9. Composition of maps
Example 1.10.

Consider the functions \(f: A \rightarrow B\) and \(g: B \rightarrow C\) that are defined in Figure 1.9 (top). The composition of these functions, \(g \circ f: A \rightarrow C\text{,}\) is defined in Figure 1.9 (bottom).

Example 1.11.

Let \(f(x) = x^2\) and \(g(x) = 2x + 5\text{.}\) Then

\begin{equation*} (f \circ g)(x) = f(g(x)) = (2x + 5)^2 = 4x^2 + 20x + 25 \end{equation*}

and

\begin{equation*} (g \circ f)(x) = g(f(x)) = 2x^2 + 5\text{.} \end{equation*}

In general, order makes a difference; that is, in most cases \(f \circ g \neq g \circ f\text{.}\)

Example 1.12.

Sometimes it is the case that \(f \circ g= g \circ f\text{.}\) Let \(f(x) = x^3\) and \(g(x) = \sqrt[3]{x}\text{.}\) Then

\begin{equation*} (f \circ g )(x) = f(g(x)) = f( \sqrt[3]{x}\, ) = (\sqrt[3]{x}\, )^3 = x \end{equation*}

and

\begin{equation*} (g \circ f )(x) = g(f(x)) = g( x^3) = \sqrt[3]{ x^3} = x\text{.} \end{equation*}
Example 1.13.

Given a \(2 \times 2\) matrix

\begin{equation*} A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\text{,} \end{equation*}

we can define a map \(T_A : {\mathbb R}^2 \rightarrow {\mathbb R}^2\) by

\begin{equation*} T_A (x,y) = (ax + by, cx +dy) \end{equation*}

for \((x,y)\) in \({\mathbb R}^2\text{.}\) This is actually matrix multiplication; that is,

\begin{equation*} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} ax + by \\ cx +dy \end{pmatrix}\text{.} \end{equation*}

Maps from \({\mathbb R}^n\) to \({\mathbb R}^m\) given by matrices are called linear maps or linear transformations.

Example 1.14.

Suppose that \(S = \{ 1,2,3 \}\text{.}\) Define a map \(\pi :S\rightarrow S\) by

\begin{equation*} \pi( 1 ) = 2, \qquad \pi( 2 ) = 1, \qquad \pi( 3 ) = 3\text{.} \end{equation*}

This is a bijective map. An alternative way to write \(\pi\) is

\begin{equation*} \begin{pmatrix} 1 & 2 & 3 \\ \pi(1) & \pi(2) & \pi(3) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}\text{.} \end{equation*}

For any set \(S\text{,}\) a one-to-one and onto mapping \(\pi : S \rightarrow S\) is called a permutation of \(S\text{.}\)

Proof.

We will prove (1) and (3). Part (2) is left as an exercise. Part (4) follows directly from (2) and (3).

(1) We must show that

\begin{equation*} h \circ (g \circ f) = (h \circ g) \circ f\text{.} \end{equation*}

For \(a \in A\) we have

\begin{align*} (h \circ (g \circ f))(a) & = h((g \circ f)(a))\\ & = h(g(f(a)))\\ & = (h \circ g)(f(a))\\ & = ((h \circ g) \circ f)(a)\text{.} \end{align*}

(3) Assume that \(f\) and \(g\) are both onto functions. Given \(c \in C\text{,}\) we must show that there exists an \(a \in A\) such that \((g \circ f)(a) = g(f(a)) = c\text{.}\) However, since \(g\) is onto, there is an element \(b \in B\) such that \(g(b) = c\text{.}\) Similarly, there is an \(a \in A\) such that \(f(a) = b\text{.}\) Accordingly,

\begin{equation*} (g \circ f)(a) = g(f(a)) = g(b) = c\text{.} \end{equation*}

If \(S\) is any set, we will use \(id_S\) or \(id\) to denote the identity mapping from \(S\) to itself. Define this map by \(id(s) = s\) for all \(s \in S\text{.}\) A map \(g: B \rightarrow A\) is an inverse mapping of \(f: A \rightarrow B\) if \(g \circ f = id_A\) and \(f \circ g = id_B\text{;}\) in other words, the inverse function of a function simply “undoes” the function. A map is said to be invertible if it has an inverse. We usually write \(f^{-1}\) for the inverse of \(f\text{.}\)

Example 1.16.

The function \(f(x) = x^3\) has inverse \(f^{-1}(x) = \sqrt[3]{x}\) by Example 1.12.

Example 1.17.

The natural logarithm and the exponential functions, \(f(x) = \ln x\) and \(f^{-1}(x) = e^x\text{,}\) are inverses of each other provided that we are careful about choosing domains. Observe that

\begin{equation*} f(f^{-1}(x)) = f(e^x) = \ln e^x = x \end{equation*}

and

\begin{equation*} f^{-1}(f(x)) = f^{-1}(\ln x) = e^{\ln x} = x \end{equation*}

whenever composition makes sense.

Example 1.18.

Suppose that

\begin{equation*} A = \begin{pmatrix} 3 & 1 \\ 5 & 2 \end{pmatrix}\text{.} \end{equation*}

Then \(A\) defines a map from \({\mathbb R}^2\) to \({\mathbb R}^2\) by

\begin{equation*} T_A (x,y) = (3x + y, 5x + 2y)\text{.} \end{equation*}

We can find an inverse map of \(T_A\) by simply inverting the matrix \(A\text{;}\) that is, \(T_A^{-1} = T_{A^{-1}}\text{.}\) In this example,

\begin{equation*} A^{-1} = \begin{pmatrix} 2 & -1 \\ -5 & 3 \end{pmatrix}; \end{equation*}

hence, the inverse map is given by

\begin{equation*} T_A^{-1} (x,y) = (2x - y, -5x + 3y)\text{.} \end{equation*}

It is easy to check that

\begin{equation*} T^{-1}_A \circ T_A (x,y) = T_A \circ T_A^{-1} (x,y) = (x,y)\text{.} \end{equation*}

Not every map has an inverse. If we consider the map

\begin{equation*} T_B (x,y) = (3x , 0 ) \end{equation*}

given by the matrix

\begin{equation*} B = \begin{pmatrix} 3 & 0 \\ 0 & 0 \end{pmatrix}\text{,} \end{equation*}

then an inverse map would have to be of the form

\begin{equation*} T_B^{-1} (x,y) = (ax + by, cx +dy) \end{equation*}

and

\begin{equation*} (x,y) = T_B \circ T_B^{-1} (x,y) = (3ax + 3by, 0) \end{equation*}

for all \(x\) and \(y\text{.}\) Clearly this is impossible because \(y\) might not be \(0\text{.}\)

Example 1.19.

Given the permutation

\begin{equation*} \pi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \end{equation*}

on \(S = \{ 1,2,3 \}\text{,}\) it is easy to see that the permutation defined by

\begin{equation*} \pi^{-1} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \end{equation*}

is the inverse of \(\pi\text{.}\) In fact, any bijective mapping possesses an inverse, as we will see in the next theorem.

Proof.

Suppose first that \(f:A \rightarrow B\) is invertible with inverse \(g: B \rightarrow A\text{.}\) Then \(g \circ f = id_A\) is the identity map; that is, \(g(f(a)) = a\text{.}\) If \(a_1, a_2 \in A\) with \(f(a_1) = f(a_2)\text{,}\) then \(a_1 = g(f(a_1)) = g(f(a_2)) = a_2\text{.}\) Consequently, \(f\) is one-to-one. Now suppose that \(b \in B\text{.}\) To show that \(f\) is onto, it is necessary to find an \(a \in A\) such that \(f(a) = b\text{,}\) but \(f(g(b)) = b\) with \(g(b) \in A\text{.}\) Let \(a = g(b)\text{.}\)

Conversely, let \(f\) be bijective and let \(b \in B\text{.}\) Since \(f\) is onto, there exists an \(a \in A\) such that \(f(a) = b\text{.}\) Because \(f\) is one-to-one, \(a\) must be unique. Define \(g\) by letting \(g(b) = a\text{.}\) We have now constructed the inverse of \(f\text{.}\)

Reading Questions 1.2.3 Reading Questions

1.

Consider the sets \(A = \{x \st x-3 \in \N\}\) and \(B = \{x \st \frac{x}{2} \in \N\}\text{.}\) Find (describe) the sets \(A \cap B\) and \(A \cup B\text{.}\)

Note that you can type such as $A \cap B = \{1,2,3\}$(although this is not the right answer). If you right-click on any math in this book and select “Show math as -> TeX commands”, you can see the commands that produce that math.

2.

What does it mean for two sets to be disjoint? Describe in words and in symbols, and give an example and non-example.

3.

What is the difference between a function being one-to-one (injective) and being onto (surjective)?

4.

After reading the section, what questions do you still have? Write at least one well formulated question (even if you think you understand everything).

Exercises 1.2.4 Practice Problems

1.

Same or different: \(\{2^n \in \N \st n \in \N\}\) and \(\{n \in \N \st 2^n \in \N\}\text{.}\)

Answer

Different. The first set only has elements that are powers of 2, while the second set is all natural numbers.

2.

Same or different: \(\{2^n \st n \in \N\}\) and \(\{n \st n = 2^x \text{ for some } x \in \N\}\text{.}\)

Answer

Same.

3.

Suppose that

\begin{align*} A & = \{ x : x \in \mathbb N \text{ and } x \text{ is even} \},\\ B & = \{x : x \in \mathbb N \text{ and } x \text{ is prime}\},\\ C & = \{ x : x \in \mathbb N \text{ and } x \text{ is a multiple of } 5\}\text{.} \end{align*}

Describe each of the following sets.

  1. \(\displaystyle A \cap B\)

  2. \(\displaystyle B \cap C\)

  3. \(\displaystyle A \cup B\)

  4. \(\displaystyle A \cap (B \cup C)\)

Hint

(a) \(A \cap B = \{ 2 \}\text{;}\) (b) \(B \cap C = \{ 5 \}\text{.}\)

4.

I'm trying to invent a function \(f: \{1,2,3\} \to \{1,2,3,4\}\text{.}\) So far, I've decided \(f(1) = 4\) and \(f(2) = 1\text{.}\) What should \(f(3)\) be ...

  1. ... if I want \(f\) to be one-to-one?

  2. ... if I want \(f\) to be onto?

Answer

To be one to one, I could take \(f(3) = 2\) or \(f(3) = 3\text{,}\) but the other two options would not work. There is no choice I can make to make \(f\) onto.

5.

I'm trying to invent a function \(f: \{1,2,3\} \to \{1,2\}\text{.}\) So far, I've decided \(f(1) = 2\text{.}\) What should \(f(2)\) and \(f(3)\) be ...

  1. ... if I want \(f\) to be one-to-one?

  2. ... if I want \(f\) to be onto?

Answer

There is no way to make \(f\) one-to-one. To make it onto, I just need one of \(f(2)\) or \(f(3)\) to be 1, so every element in the codomain is the image of at least one element of the domain.

6.

Consider the function \(f:\Z \to \Z\) given by \(f(n) = \begin{cases}n+1 \amp \text{ if }n\text{ is even} \\ n-3 \amp \text{ if }n\text{ is odd} . \end{cases}\)

  1. Is \(f\) injective? Prove your answer.

  2. Is \(f\) surjective? Prove your answer.

Exercises 1.2.5 Collected Homework

1.

Consider the sets below.

\begin{equation*} A = \{2n \st n \in \Z\} \qquad \text{ and } \qquad B = \{x \in \Z \st x^2 \in A\}\text{.} \end{equation*}

  1. Describe the sets \(A\) and \(B\) in words or by listing enough elements to see what is going on.

  2. If \(a \in A\) and \(b \in A\text{,}\) must \(a+b \in A\text{?}\) Explain.

  3. If \(a \in B\) and \(b \in B\text{,}\) must \(a+b \in B\text{?}\) Explain.

2.

Let \(f : A \rightarrow B\) and \(g : B \rightarrow C\) be maps.

  1. If \(f\) and \(g\) are both one-to-one functions, show that \(g \circ f\) is one-to-one.

  2. If \(g \circ f\) is onto, show that \(g\) is onto.

Hint

To show a function \(h\) is one-to-one, you show that if \(h(x) = h(y)\) then \(x=y\text{.}\)

To show a function \(h\) is onto, show that for every element \(c\) in the codomain, there is some element \(a\) in the domain such that \(h(a) = c\text{.}\)