CMSC 250 Homework 11 Fall 2001

Due Wed Nov 14 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Let $f$ be a function that given a positive integer $n$ returns the smallest perfect square greater than or equal to $n$. For each part of this problem, specify a domain and a co-domain that give $f$ the following properties.
   1. $f$ is 1-1 and onto.

   2. $f$ is 1-1, but not onto.

   3. $f$ is not 1-1, but it is onto.

   4. $f$ is not 1-1 and not onto.

2. How many numbers do you have to pick (randomly and without replacement) from $\{1,2,3,4,5,6,7,8,9,10,11\}$ before you can guarantee that you have picked two that add up to 14?

3. Give an explicit example of a 1-1, onto function from $A=\{a,b,c,d,e,f, g\}$ to $B=\{t,u,v,w,x,y,z\}$ and write down its inverse. You can use ordered pair or arrow notation to define the function.

4. Prove that the composition of two bijections (where the range of the first function is the domain of the second function) is a bijection.

5. Use the result of the previous problem, along with mathematical induction, to show that the composition of $n$ bijections (where the range of the $k$th function is the domain of the $k+1$st function in all cases) is a bijection for all $n\geq 2$.

6. Let $f:A\rightarrow C$ and $g:B\rightarrow D$ be bijections. Let $h:A\times C\rightarrow B\times D$ be defined by $h(a,b) = (f(a),g(b))$. Prove that $h$ is a bijection from $A\times C$ to $B\times D$.

7. Let $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ be functions such that $g\circ f$ is 1-1. For each of the following parts, either prove or give a counterexample for the following statements:
   1. $f$ is 1-1.

   2. $g$ is 1-1.

   You may use different functions for each part.

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 h11.tex

The translation was initiated by Deep Saraf on 2001-11-08