CMSC 250 Fall 2001 Homework 11 solutions
    1. Domain $\{1,2,10\}$ Codomain $\{1,4,16\}$

    2. Domain $\{1,2,5\}$ Codomain $\{1,4,9,16\}$

    3. Domain $\{1,2,3,5\}$ Codomain $\{1,4,9\}$

    4. Domain $\{1,2,3\}$ Codomain $\{1,4,9\}$

  2. We have to pick 8 numbers to find two that sum up to 14. The reason is that we can partition the numbers into 5 subsets: $\{3,11\}$, $\{4,10\}$, $\{5,9\}$, $\{6,8\}$, $\{1,2,7\}$. If both numbers are picked from any of the first 4 subsets, then we get a sum equal to 14. The last three numbers cannot ever be used to sum up to 14. Hence, the maximum number of picks we can make without obtaining a sum equal to 14 is seven by picking 1 from each of the first 4 subsets plus the last three elements. After we pick these 7 elements, the next pick must give us a sum of 14, so the number of picks needed to guarantee a sum equal to 14 is 8.

  3. $f(a)=t$, $f(b)=u$, $f(c)=v$, $f(d)=w$, $f(e)=x$, $f(f)=y$, $f(g)=z$.

    The inverse function is defined by: $f^{-1}(t)=a$, $f^{-1}(u)=b$, $f^{-1}(v)=c$, $f^{-1}(w)=d$, $f^{-1}(x)=e$, $f^{-1}(y)=f$, $f^{-1}(z)=g$.

  4. Given f: $ X \rightarrow Y$, g: $ Y \rightarrow Z$ are bijections, prove that $h=g\circ f(x)$ is bijection (1-1,onto).

    To show $g\circ f$ is well-defined, suppose that $g\circ f(x)=z_{1}$ and $g\circ f(x)=z_{2}$. Then, $g(f(x))=z_{1}$ and $g(f(x))=z_{2}$. Because $f$ is well-defined, $f(x)=y$ has only one value. Hence, $g(y)=z_{1}$ and $g(y)=z_{2}$. Because $g$ is well-defined, $g(y)$ has only one value, so $z_{1}=z_{2}$, which shows that $g\circ f$ is well-defined.

    To show that $g\circ f$ is 1-1, suppose that $ g(f(x_1))=g(f(x_2))$.

    Since g is 1-1, $f(x_1) = f(x_2).$

    Since f is 1-1, $x_1 = x_2 $, which implies that $g\circ f$ is 1-1.

    To show that $g\circ f$ is onto, let $z_{1}$ be a element of Z.

    Since g is onto, $\exists y_{1} \in Y,$ such that $g(y_{1})=z_{1}$

    Since f is onto, $\exists x_{1} \in X,$ such that $f(x_{1})=y_{1}$

    Hence $\exists x \in X $ such that $(g\circ f)(x)=g(f(x))=g(y)=z$, which means that $g\circ f$ is onto.

  5. Assume that $\forall n\geq 1$, $f_{n}:A_{n-1}\rightarrow A_{n}$ is a bijection from $A_{n-1}$ to $A_{n}$.

    Base Case:
      From the previous problem, $f_2\circ f_1$ is a bijection from $A_{0}$ to $A_{2}$.
    Inductive Hypothesis:
      Assume that $f_{k-1}\circ f_{k-2}\circ...\circ f_1$ is a bijection from $A_{0}$ to $A_{k-1}$ for some $k\in{\bf {Z}}^{+}$.
    Inductive Step:
    Show:
      $f_k\circ f_{k-1}\circ...\circ f_1$ is a bijection from $A_{0}$ to $A_{k}$.
    Proof:
      The function $f_{k}\circ f_{k-1}\circ f_{k-2}\circ...\circ f_{1}$ can be written as
      $f_{k}\circ(f_{k-1}\circ f_{k-2}\circ...\circ f_{1}).$
      By the inductive hypothesis, $f_{k-1}\circ f_{k-2}\circ...\circ f_{1}$ is a bijection from $A_{0}$ to $A_{k-1}$. Call this bijection $g_{k-1}$.
      Hence, $f_{k}\circ(f_{k-1}\circ f_{k-2}\circ...\circ f_{1}) = f_{k}\circ g_{k-1}$, By the previous problem, this composition of two bijections is a bijection from $A_{0}$ to $A_{k}$.
      QED

  6. We must show that $h$ is well-defined, 1-1, and onto.

    To show $h$ is well-defined, consider that given any $(a,b)\in A\times B$, $h(a,b) = (f(a),g(b))$ exists because $f$ is defined at all points of $A$, and $g$ is defined at all points of $B$. Also, if $h(a,b)$ equals $(c_{1},d_{1})$ and $(c_{2},d_{2})$ simultaneously, then $f(a)=c_{1}$ and $c_{2}$ simultaneously, which implies that $c_{1}=c_{2}$, since $f$ is well-defined, and if $g(b)=d_{1}$ and $d_{2}$ simultaneously, then $d_{1}=d_{2}$ because $g$ is well-defined. Hence, $h$ is well-defined.

    To show $h$ is onto, let $(c,d)\in C\times D$. Because $f$ is onto, $\exists a\in A$ such that $f(a) = c$. Because $g$ is onto, $\exists b\in B$ such that $g(b) = d$. Hence, $h(a,b)=(f(a),g(b))=(c,d)$, which means that $h$ is onto.

    To show that $h$ is 1-1, Suppose that $(c,d)=h(a_{1},b_{1})=h(a_{2},b_{2})$.

    By the definition of $h$, $c=f(a_{1})$ and $c=f(a_{2})$. Because $f$ is 1-1, $a_{1}=a_{2}$.

    By the definition of $h$, $d=g(b_{1})$ and $d=g(b_{2})$. Because $g$ is 1-1, $b_{1}=b_{2}$.

    Hence, since $a_{1}=a_{2}$ and $b_{1}=b_{2}$, $(a_{1},b_{1})=(a_{2},b_{2})$, which means that $h$ is 1-1.

    1. Yes, Proof by contradiction.

      Suppose that $f$ is not 1-1. Then $\exists x_{1},x_{2}\in X$ such that $y =f(x_{1}) = f(x_{2})$.

      $g\circ f(x_{1}) =g(f(x_{1}))= g(y)$ and $g\circ f(x_{2})= g(f(x_{2}))=g(y)$, which implies that $g\circ f$ is not 1-1. This is a contradiction, so $f$ must be 1-1.

    2. No, Let $X = \{x\}$, $Y=\{y_{1},y_{2}\}$, $Z =\{z\}$. Let $f:X\rightarrow Y$ be defined by $f(x)=y_{1}$. Let $g:Y\rightarrow Z$ be defined by $g(y_{1})=g(y_{2})=z.$ Then, $g\circ f$ is 1-1, but $g$ is not 1-1.

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode h11ans

The translation was initiated by John Arras on 2001-11-14

John Arras
2001-11-14