Problem 21
(a) Let \(F: A \rightarrow B\) be a function. Prove that \(F\) is onto if and only if \(F^{-1}\left(B_{1}\right) \neq B\) for each nonempty subset \(B_{1}\) of \(B\). (b) Let \(F: A \rightarrow B\) be a function. Prove that \(F\) is onto if and only if \(F\left(F^{-1}\left(B_{1}\right)\right)=\) \(B_{1}\) for all \(B_{1} \subseteq B\).
Problem 21
For each of the following functions, prove that the function is \(1-1\) or find an appropriate pair of points to show that the function is not \(1-1:\) (a) \(F: \mathbb{Z} \rightarrow \mathbb{Z}\) $$F(n)=\left\\{\begin{array}{ll}n^{2} & \text { for } n \geq 0 \\ -n^{2} & \text { for } n \leq 0\end{array}\right.$$ (b) \(F: \mathbb{R} \rightarrow \mathbb{R}\) $$F(x)=\left\\{\begin{array}{ll}x+1 & \text { for } x \in \mathbb{Q} \\ 2 x & \text { for } x \notin \mathbb{Q}\end{array}\right.$$ (c) \(F: \mathbb{R} \rightarrow \mathbb{R}\) $$F(x)=\left\\{\begin{array}{ll}3 x+2 & \text { for } x \in \mathbb{Q} \\ x^{3} & \text { for } x \notin \mathbb{Q}\end{array}\right.$$ (d) \(F: Z \rightarrow \mathbb{Z}\) $$F(n)=\left\\{\begin{array}{ll}n+1 & \text { for } n \text { odd } \\ n^{3} & \text { for } n \text { even }\end{array}\right.$$
Problem 22
(a) Find functions from \(\mathbb{R}\) to \(\mathbb{R}\) that are: i. strictly decreasing ii. decreasing but not strictly decreasing iii. neither increasing nor decreasing iv. both increasing and decreasing (b) Show that no \(F: \mathbb{R} \rightarrow \mathbb{R}\) is both increasing and strictly decreasing. (c) Find a subset \(X \subseteq \mathbb{R}\) and a function \(F: X \rightarrow X\) where \(F\) is both strictly increasing and strictly decreasing.
Problem 22
Let \(X\) be a set, and let \(\mathcal{F}_{X}\) be the set of all \(I-I\) functions from \(X\) onto \(X\). We have two operations on functions in \(\mathcal{F}_{X}: \circ\) and -1 . Prove the following statements called group axioms. (If the results are already proved in the book, note where to find the proofs.) (a) For all \(F, G \in \mathcal{F}_{X}, F \circ G \in \mathcal{F}\). (b) For all \(F, G, H \in \mathcal{F}_{X},(F \circ G) \circ H=F \circ(G \circ H)\) (Associative Law). (c) For all \(F \in \mathcal{F}_{X}, F \circ I d_{X}=I d_{X} \circ F=F\). (Identity Axiom). (d) For all \(F \in \mathcal{F}_{X}\), there exists an \(F^{-1}\) such that \(F \circ F^{-1}=F^{-1} \circ F=I d_{X}\) (Inverse Axiom).
Problem 23
Infinite Pigeon-Hole Principle: Suppose \(X\) is an infinite set and \(Y\) is a finite set. Now, suppose \(F: X \rightarrow Y\). Show there is a \(y \in Y\) such that for infinitely many \(x \in X\) such that \(F(x)=y\).
Problem 23
Construct functions with the following properties: (a) \(F: \mathbb{N} \rightarrow\) N such that range \((F)=\mathbb{N}\) and, for each \(n \in \mathbb{N},\) there exist exactly two solutions for the equation \(F(x)=n\). (b) \(F: \mathrm{N} \rightarrow \mathbb{N}\) such that, for each \(n \in \mathrm{N}\), there are exactly \(n\) solutions for the equation \(F(x)=n\).
Problem 28
Define a function \(F: \mathbb{N} \rightarrow \mathbb{N}\) such that \(F(n)=n-10\) if \(n>100\) and \(F(n)=\) \(F(F(n+11))\) if \(n \leq 100\) (a) Show that \(F(99)=91\). (b) Prove that \(F(n)=91\) for all \(n\) such that \(0 \leq n \leq 100\).
Problem 29
Let \(A, B,\) and \(C\) be sets, and let \(F: A \rightarrow C\) and \(G: B \rightarrow C\) be functions. (a) What condition must \(F\) and \(G\) satisfy for \(F \cup G\) to be a function from \(A \cup B\) to \(C ?\) (b) Give conditions on \(A\) and \(B\) such that \(F \cup G\) is a function for every \(F: A \rightarrow C\) and \(G: B \rightarrow C\)
Problem 30
Let \(F\) be a function, and let \(C, D \subseteq \operatorname{domain}(F)\). a.Prove that range \((F|C\cap D)\) \(\subseteq\) range \((F \mid c) \cap\) range \((F \mid D)\). (b) Show by example that equality need not hold in part (a).
Problem 31
If looked at appropriately, the definition of a function as a set of ordered pairs and the intuitive notion that a function is something given by a rule are equivalent. Develop that equivalence here. Assume that \(F\) has a finite domain \(\\{0,1,2, \ldots, n-1\\}\) and a finite codomain \(\\{0,1,2, \ldots, m-1]\). (a) Suppose \(F\) is a function given as a set of ordered pairs. For an input \(x_{1}\), give a rule for calculating \(F\left(x_{1}\right)\). Use \(F\) (or its graph) in your rule. (b) Suppose the function \(F\) is given by a rule. Express \(F\) as a set of ordered pairs.
