CSCI-C 241 HW #11
Instructor: Wennstrom
Assigned Wednesday, April 7th, 2021
Due Tuesday, April 13th, 2021
1. Let A = {1, 2, 3} and B = {a, b, c, d}. Give an example of the following. If you think
no such example exists, you must explain why not. You may not use any examples
from elsewhere in this assignment. (Hint: Only four of these are impossible.) For parts
(a)-(j), you should use set-list notation or a directed graph. For the remaining parts,
use function notation.
(a) A function on A that is one-to-one and onto
(b) A function on A that is one-to-one, but not onto
(c) A function on A that is onto, but not one-to-one
(d) A function on A that is neither one-to-one nor onto
(e) A function from A to B that is one-to-one
(f) A function from A to B that is onto
(g) A function from A to B that is not one-to-one
(h) A function from B to A that is one-to-one
(i) A function from B to A that is onto
(j) A function from B to A that is not onto
(k) A function from Z to N. (You may use function notation or set-builder notation.)
It doesn’t matter if it’s one-to-one or onto, neither, or both.
(l) A function on Z that is one-to-one and onto
(m) A function on Z that is one-to-one, but not onto
(n) A function on Z that is onto, but not one-to-one
(o) A function on Z that is neither one-to-one nor onto
(p) A function from the set of all formulas of propositional logic to N. (You may use
function notation or set-builder notation.) It doesn’t matter if it’s one-to-one or
onto, neither, or both.
For the following problems, you should either be writing a proof (following course guidelines)
or giving a counterexample and a short explanation of why your counterexample works. (You
do not need to go into great detail about your counterexample, but don’t just write “5 and
7”.)
2. Let f(x) = 3x− 5 be a function on the real numbers.
(a) Prove that f is one-to one.
(b) Prove that f is onto.
3. (a) Define k : R→ R by k(x) = (x− 3)2. Prove that k is not one-to-one.
(b) Let R>3 = {x | x ∈ R ∧ x > 3}. (In other words, R>3 is the set of all real numbers
that are greater than 3.) Define k2 : R>3 → R by k2(x) = (x − 3)2. Prove that k2
is one-to-one.
4. Define g : R → R by g(x) = dxe. The operator d·e is the ceiling operator that
just rounds up to the smallest integer bigger than (or equal to) x. So for example
g(3.14) = d3.14e = 4, g(2.00001) = d2.00001e = 3, g(17) = d17e = 17, and g(−2.25) =
d−2.25e = −2.
(a) Prove that g is not one-to-one.
(b) Prove that g is not onto.
(c) g is not onto because the codomain is all real numbers. What set would you have
to change the codomain to in order to make g an onto function?
5. Define a function h on the set of strings by h(s) = (s with all dashes removed ). So
h("A-B-C") = "ABC" and h("foobar") = "foobar".
(a) Prove that h is not one-to-one.
(b) Prove that h is not onto.
6. Define the function a from the set of strings to N by:
a(s) = (the sum of all the numeric digits in s)
So for example, a("10203") = 1+0+2+0+3 = 6, a("10-plus-62") = 1+0+6+2 = 9,
and a("foobar") = 0.
Warning: a works on digits not numbers, so a("12") is 3, not 12.
(a) Prove that a is not one-to-one.
(b) Prove that a is onto.
7. Bonus: Let P∗(N) be the set of all nonempty subsets of N. Define m : P∗(N) → N
by m(A) = the smallest member of A. So for example, m
({3, 5, 10}) = 3 and m({n |
n is prime }) = 2.
(a) Prove that m is not one-to-one.
(b) Prove that m is onto.
Page 2

欢迎咨询51作业君