MATH/EECS 1028 Final Exam
Take-Home Portion
Due 11:59PM April 27th, 2021
INSTRUCTIONS
Provide answers to the following questions. For all questions that ask for a proof, be sure to carefully justify
all steps of your proof and clearly reference any definitions, corollaries or theorems you use from the textbook.
Your submitted solutions must be entirely your work, you may not work with other students in any way
on the solution to these problems. Doing so is a violation of the academic honesty policy and violations of
that policy is a serious academic offence and will be punished accordingly. See the course syllabus for more
on this.
Your submitted solutions must be in PDF format. It is strongly encouraged that your submitted solution
be typeset using Microsoft Word, Google Docs, LATEX or similar packages. However, hand written submissions
will be accepted so long as they are in PDF file format (openable by Adobe Acrobat or similar) and are
readable. Submissions which are unreadable for any reason (e.g., wrong file format, poor handwriting, poor
image capture/scanning, etc) will be given zero marks.
Also note that, for all questions that ask you to prove or show something, your proofs must be detailed,
thoroughly explained and rigourously argued. If you use results from the textbook you must clearly state
what is being used and where it came from.
PROBLEMS
Question 1
Let gi : Ai−1 → Ai be a sequence of functions for i = 0, . . . , n and some positive integer n. Further, let
fi = gi ◦ gi−1 ◦ · · · ◦ g0 . That is, fi is a composition of the functions g0 , g1 , . . . , gi .
a. Prove that, if fi is onto, then gi is onto.
b. Prove that, for all integers n ≥ 0, fn is one-to-one if and only if gi is one-to-one for all 0 ≤ i ≤ n.
Question 2
Let S = { pq |p, q are prime numbers greater than 0} and E = {0, −2, 2, −4, 4, −6, 6, · · · } be the set of even
integers. Prove that |S| = |E| by constructing a bijection from S to E.
Question 3
Some recursive function definitions can be invalid, meaning that they do not produce an output for every
input in their domain. For instance, the recursively defined function h(x) = h(h(x) + 1) is such an example
since attempting to evaluate h(x) involves again evaluating h(x). Hence, sometimes it is a challenge simply
to prove that a recursively defined function actually produces an output for every value.
1
Take-Home Portion
Due 11:59PM April 27th, 2021
INSTRUCTIONS
Provide answers to the following questions. For all questions that ask for a proof, be sure to carefully justify
all steps of your proof and clearly reference any definitions, corollaries or theorems you use from the textbook.
Your submitted solutions must be entirely your work, you may not work with other students in any way
on the solution to these problems. Doing so is a violation of the academic honesty policy and violations of
that policy is a serious academic offence and will be punished accordingly. See the course syllabus for more
on this.
Your submitted solutions must be in PDF format. It is strongly encouraged that your submitted solution
be typeset using Microsoft Word, Google Docs, LATEX or similar packages. However, hand written submissions
will be accepted so long as they are in PDF file format (openable by Adobe Acrobat or similar) and are
readable. Submissions which are unreadable for any reason (e.g., wrong file format, poor handwriting, poor
image capture/scanning, etc) will be given zero marks.
Also note that, for all questions that ask you to prove or show something, your proofs must be detailed,
thoroughly explained and rigourously argued. If you use results from the textbook you must clearly state
what is being used and where it came from.
PROBLEMS
Question 1
Let gi : Ai−1 → Ai be a sequence of functions for i = 0, . . . , n and some positive integer n. Further, let
fi = gi ◦ gi−1 ◦ · · · ◦ g0 . That is, fi is a composition of the functions g0 , g1 , . . . , gi .
a. Prove that, if fi is onto, then gi is onto.
b. Prove that, for all integers n ≥ 0, fn is one-to-one if and only if gi is one-to-one for all 0 ≤ i ≤ n.
Question 2
Let S = { pq |p, q are prime numbers greater than 0} and E = {0, −2, 2, −4, 4, −6, 6, · · · } be the set of even
integers. Prove that |S| = |E| by constructing a bijection from S to E.
Question 3
Some recursive function definitions can be invalid, meaning that they do not produce an output for every
input in their domain. For instance, the recursively defined function h(x) = h(h(x) + 1) is such an example
since attempting to evaluate h(x) involves again evaluating h(x). Hence, sometimes it is a challenge simply
to prove that a recursively defined function actually produces an output for every value.
1
