91Ó°ÊÓ

Give an example of finite sets \(A\) and \(B\) with \(|A|,|B| \geq 4\) and a function \(f: A \rightarrow B\) such that (a) \(f\) is neither one-to-one nor onto; (b) \(f\) is one-to-one but not onto; (c) \(f\) is onto but not one-to-one; (d) \(f\) is onto and one-to-one.

Show that if eight people are in a room, at least two of them have birthdays that occur on the same day of the week.

Determine whether each of the following statements is true or false. For each false statement give a counterexample. a) If \(f: A \rightarrow B\) and \((a, b),(a, c) \in f\), then \(b=c\). b) If \(f: A \rightarrow B\) is a one-to-one correspondence and \(A, B\) are finite, then \(A=B\). c) If \(f: A \rightarrow B\) is one-to-one, then \(f\) is invertible. d) If \(f: A \rightarrow B\) is invertible, then \(f\) is one-to-one. e) If \(f: A \rightarrow B\) is one-to-one and \(g, h: B \rightarrow C\) with \(g \circ f=h \circ f\), then \(g=h\). f) If \(f: A \rightarrow B\) and \(A_{1}, A_{2} \subseteq A\), then \(f\left(A_{1} \cap A_{2}\right)=\) \(f\left(A_{1}\right) \cap f\left(A_{2}\right)\). g) If \(f: A \rightarrow B\) and \(B_{1}, B_{2} \subseteq B\), then \(f^{-1}\left(B_{1} \cap B_{2}\right)=\) \(f^{-1}\left(B_{1}\right) \cap f^{-1}\left(B_{2}\right)\).

How many times must we roll a single die in order to get the same score (a) at least twice? (b) at least three times? (c) at least \(n\) times, for \(n \geq 4\) ?

For each of the following functions \(g: \mathbf{R} \rightarrow \mathbf{R}\), determine whether the function is one-toone and whether it is onto. If the function is not onto, determine the range \(g(R)\). a) \(g(x)=x+7\) b) \(g(x)=2 x-3\) c) \(g(x)=-x+5\) d) \(g(x)=x^{2}\) e) \(g(x)=x^{2}+x\) f) \(g(x)=x^{3}\)

Each of the following functions \(f: \mathbf{Z} \times \mathbf{Z} \rightarrow \mathbf{Z}\) is a closed binary operation on \(\mathbf{Z}\). Determine in each case whether \(f\) is commutative and/or associative. a) \(f(x, y)=x+y-x y\) b) \(f(x, y)=\max \\{x, y\\}\), the maximum (or larger) of \(x, y\) c) \(f(x, y)=x^{y}\) d) \(f(x, y)=x+y-3\)

Let \(A=\\{1,2,3,4\\}\) and \(B=\\{1,2,3,4,5,6\\}\). a) How many functions are there from \(A\) to \(B\) ? How many of these are one- to-one? How many are onto? b) How many functions are there from \(B\) to \(A\) ? How many of these are onto? How many are one-to-one?

Let \(A=\\{2,4,8,16,32\\}\), and consider the closed binary operation \(f: A \times A \rightarrow A\) where \(f(a, b)=\operatorname{gcd}(a, b)\). Does \(f\) have an identity element?

Prove that if we select 101 integers from the set \(S=\\{1,2,3, \ldots, 200\\}\), there exist \(m, n\) in the selection where \(\operatorname{gcd}(m, n)=1\).

a) Show that if any 14 integers are selected from the set \(S=\\{1,2,3, \ldots, 25\\}\), there are at least two whose sum is 26 . b) Write a statement that generalizes the results of part (a) and Example 5.45.