Chapter 7

Let \(A=\\{1,2,3,4,5\\}, B=\\{a, b, c, d, e, f\\},\) and \(C=\\{+,-\\} .\) Define \(f: A \rightarrow B\) by \(f(k)\) equal to the \(k^{t h}\) letter in the alphabet, and define \(g: B \rightarrow C\) by \(g(\alpha)=+\) if \(\alpha\) is a vowel and \(g(\alpha)=-\) if \(\alpha\) is a consonant. (a) Find \(g \circ f\). (b) Does it make sense to discuss \(f \circ g ?\) If not, why not? (c) Does \(f^{-1}\) exist? Why? (d) Does \(g^{-1}\) exist? Why?

Let \(A=\\{1,2,3,4\\}\) and \(B=\\{a, b, c, d\\} .\) Determine which of the following are functions. Explain. (a) \(f \subseteq A \times B,\) where \(f=\\{(1, a),(2, b),(3, c),(4, d)\\}\). (b) \(g \subseteq A \times B,\) where \(g=\\{(1, a),(2, a),(3, b),(4, d)\\}\). (c) \(h \subseteq A \times B,\) where \(h=\\{(1, a),(2, b),(3, c)\\}\). (d) \(k \subseteq A \times B,\) where \(k=\\{(1, a),(2, b),(2, c),(3, a),(4, a)\\}\). (e) \(L \subseteq A \times A,\) where \(L=\\{(1,1),(2,1),(3,1),(4,1)\\}\).

Let \(A=\\{1,2,3\\} .\) Define \(f: A \rightarrow A\) by \(f(1)=2, f(2)=1,\) and \(f(3)=3\). Find \(f^{2}, f^{3}, f^{4}\) and \(f^{-1}\).

Find the ranges of the following functions on \(\mathbb{Z}\) : (a) \(g=\\{(x, 4 x+1) \mid x \in \mathbb{Z}\\}\). (b) \(h(x)=\) the least integer that is greater than or equal to \(\sqrt{|x|}\). (c) \(P(x)=x+10\).

Let \(A=\\{1,2,3\\}\). (a) List all permutations of \(A\). (b) Find the inverse and square of each of the permutations of part a, where the square of a permutation, \(f,\) is the composition \(f \circ f\). (c) Show that the composition of any two permutations of \(A\) is a permutation of \(A\). (d) Prove that if \(A\) is any set where \(|A|=n,\) then the number of permutations of \(A\) is \(n !\)

Which of the following are one-to-one, onto, or both? (a) \(f_{1}: \mathbb{R} \rightarrow \mathbb{R}\) defined by \(f_{1}(x)=x^{3}-x .\) (b) \(f_{2}: \mathbb{Z} \rightarrow \mathbb{Z}\) defined by \(f_{2}(x)=-x+2\). (c) \(f_{3}: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) defined by \(f_{3}(j, k)=2^{j} 3^{k}\) (d) \(f_{4}: \mathbb{P} \rightarrow \mathbb{P}\) defined by \(f_{4}(n)=\lceil n / 2],\) where \([x]\) is the ceiling of \(x\), the smallest integer greater than or equal to \(x\). (e) \(f_{5}: \mathbb{N} \rightarrow \mathrm{N}\) defined by \(f_{5}(n)=n^{2}+n\) (f) \(f_{6}: \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}\) defined by \(f_{6}(n)=(2 n, 2 n+1)\).

Define \(s, u,\) and \(d,\) all functions on the integers, by \(s(n)=n^{2}, u(n)=n+1,\) and \(d(n)=n-1 .\) Determine: (a) \(u \circ s \circ d\) (b) \(s \circ u \circ d\) (c) \(d \circ s \circ u\)

Which of the following are injections, surjections, or bijections on \(\mathbb{R}\), the set of real numbers? (a) \(f(x)=-2 x\) (b) \(g(x)=x^{2}-1\). (c) \(h(x)=\left\\{\begin{array}{cc}x & x<0 \\ x^{2} & x \geq 0\end{array}\right.\) (d) \(q(x)=2^{x}\) (e) \(r(x)=x^{3}\) (f) \(s(x)=x^{3}-x\)

Let \(A\) be a set and let \(S\) be any subset of \(A\). Let \(\chi_{S}: A \rightarrow\\{0,1\\}\) be defined by $$ \chi_{S}(x)=\left\\{\begin{array}{ll} 1 & \text { if } x \in S \\ 0 & \text { if } x \notin S \end{array}\right. $$ The function \(\chi_{S}\) is called the characteristic function of \(S\). (a) If \(A=\\{a, b, c\\}\) and \(S=\\{a, b\\}\), list the elements of \(\chi_{S}\). (b) If \(A=\\{a, b, c, d, e\\}\) and \(S=\\{a, c, e\\},\) list the elements of \(\chi_{S}\). (c) If \(A=\\{a, b, c\\},\) what are \(\chi_{\emptyset}\) and \(\chi_{A} ?\)

Consider the following functions on the set of bit strings of length \(4 .\) In these definitions, addition is done modulo \(2,\) so that \(1+1=0 .\) Which of these functions has an inverse? For those that have an inverse, what is it? For those that don't explain why. (a) \(f_{1}\left(b_{1} b_{2} b_{3} b_{4}\right)=b_{2} b_{3} b_{4} b_{1}\) (b) \(f_{2}\left(b_{1} b_{2} b_{3} b_{4}\right)=b_{4} b_{3} b_{2} b_{1}\) (c) \(f_{3}\left(b_{1} b_{2} b_{3} b_{4}\right)=\left(b_{1}+b_{2}\right)\left(b_{2}+b_{3}\right)\left(b_{3}+b_{4}\right)\left(b_{4}+b_{1}\right)\) (d) \(f_{4}\left(b_{1} b_{2} b_{3} b_{4}\right)=b_{1}\left(b_{1}+b_{2}\right)\left(b_{1}+b_{2}+b_{3}\right)\left(b_{1}+b_{2}+b_{3}+b_{4}\right)\)

Suppose that \(m\) pairs of socks are mixed up in your sock drawer, Use the Pigeonhole Principle to explain why, if you pick \(m+1\) socks at random, at least two will make up a matching pair.

If \(A\) and \(B\) are finite sets, how many different functions are there from \(A\) into \(B ?\)

Inverse images. If \(f\) is any function from \(A\) into \(B,\) we can describe the inverse image as a function from \(B\) into \(\mathcal{P}(A)\), which is also commonly denoted \(f^{-1}\). If \(b \in B, f^{-1}(b)=\\{a \in A \mid f(a)=b\\}\). If \(f\) does have an inverse, the inverse image of \(b\) is \(\left\\{f^{-1}(b)\right\\}\). (a) Let \(g: \mathbb{R} \rightarrow \mathbb{R}\) be defined by \(g(x)=x^{2} .\) What are \(g^{-1}(4), g^{-1}(0)\) and \(g^{-1}(-1) ?\) (b) If \(r: \mathbb{R} \rightarrow \mathbb{Z},\) where \(r(x)=\lceil x\rceil,\) what is \(r^{-1}(1) ?\)

In your own words explain the statement "The sets of integers and even integers have the same cardinality."

Let \(f, g,\) and \(h\) all be functions from \(\mathbb{Z}\) into \(\mathbb{Z}\) defined by \(f(n)=n+5\), \(g(n)=n-2,\) and \(h(n)=n^{2} .\) Define: (a) \(f \circ g\) (b) \(f^{3}\) (c) \(f \circ h\)

Let \(A=\\{1,2,3,4,5\\}\). Find functions, if they exist that have the properties specified below. (a) A function that is one-to-one and onto. (b) A function that is neither one-to-one nor onto. (c) A function that is one-to-one but not onto. (d) A function that is onto but not one-to-one.

Let \(f\) be a function with domain \(A\) and codomain \(B\). Consider the relation \(K \subseteq A \times A\) defined on the domain of \(f\) by \((x, y) \in K\) if and only if \(f(x)=f(y) .\) The relation \(K\) is called the kernel of \(f\). (a) Prove that \(K\) is an equivalence relation. (b) For the specific case of \(A=\mathbb{Z},\) where \(\mathbb{Z}\) is the set of integers, let \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) be defined by \(f(x)=x^{2} .\) Describe the equivalence classes of the kernel for this specific function.

Define the following functions on the integers by \(f(k)=k+1, g(k)=2 k\), and \(h(k)=\lceil k / 2]\) (a) Which of these functions are one-to-one? (b) Which of these functions are onto? (c) Express in simplest terms the compositions \(f \circ g, g \circ f, g \circ h, h \circ g\), and \(h^{2}\).

Let \(f: \mathbb{P} \rightarrow \mathbb{P}\), where \(f(a)\) is the largest power of two that evenly divides \(a\); for example, \(f(12)=4, f(9)=1,\) and \(f(8)=8\). Describe the equivalence classes of the kernel of \(f\).

Let \(A\) be a nonempty set. Prove that if \(f\) is a bijection on \(A\) and \(f \circ f=f\), then \(f\) is the identity function, \(i\) Hint. You have seen a similar proof in matrix algebra.

(a) Prove that the set of natural numbers is countable. (b) Prove that the set of integers is countable. (c) Prove that the set of rational numbers is countable.

For the real matrix \(A=\left(\begin{array}{cc}a & b \\ c & d\end{array}\right), \operatorname{det}(A)=a d-b c\) Recall that a bijection from a set to itself is also referred to as a permutation of the set. Let \(\pi\) be a permutation of \(\\{a, b, c, d\\}\) such that \(a\) becomes \(\pi(a), b\) becomes \(\pi(b),\) etc. Let \(B=\left(\begin{array}{cc}\pi(a) & \pi(b) \\ \pi(c) & \pi(d)\end{array}\right)\). How many permutations of \(\pi\) leave the determinant of \(A\) invariant, that is, \(\operatorname{det} A=\operatorname{det} B ?\)

(a) Prove that the set of finite strings of 0 's and 1 's is countable. (b) Prove that the set of odd integers is countable. (c) Prove that the set \(\mathbb{N} \times \mathbb{N}\) is countable.

State and prove a theorem on inverse functions analogous to the one that says that if a matrix has an inverse, that inverse is unique.

Use the Pigeonhole Principle to prove that an injection camot exist between a finite set \(A\) and a finite set \(B\) if the cardinality of \(A\) is greater than the cardinality of \(B\).

Let \(f\) and \(g\) be functions whose inverses exist. Prove that \((f \circ g)^{-1}=\) \(g^{-1} \circ f^{-1}\)

The important properties of relations are not generally of interest for functions. Most functions are not reflexive, symmetric, antisymmetric, or transitive. Can you give examples of functions that do have these properties?

Prove that the set of all functions on the integers is an uncountable set.

Given five points on the unit square, \(\\{(x, y) \mid 0 \leq x, y \leq 1\\},\) prove that there are two of the points a distance of no more than \(\frac{\sqrt{2}}{2}\) from one another.

Prove by induction that if \(n \geq 2\) and \(f_{1}, f_{2}, \ldots, f_{n}\) are invertible functions on some nonempty set \(A,\) then \(\left(f_{1} \circ f_{2} \circ \ldots \circ f_{n}\right)^{-1}=f_{n}^{-1} \circ \ldots \circ f_{2}^{-1} \circ f_{1}^{-1}\). The basis has been taken care of in Exercise 7.3 .4 .12 .

(a) Our definition of cardinality states that two sets, \(A\) and \(B\), have the same cardinality if there exists a bijection between the two sets. Why does it not matter whether the bijection is from \(A\) into \(B\) or \(B\) into \(A ?\) (b) Prove that "has the same cardinality as" is an equivalence relation on sets.

Based on the definition of the identity function, show that for all functions \(f: A \rightarrow A, f \circ i=i \circ f=f\)