### Discrete Math Final: Questions 8 and 9

8. Consider the function $f: {\Bbb Z}^+ \rightarrow {\Bbb Z}^+$
given by $f(n) = n+1$ (for all positive integers $n$).

9. Now consider $g: {\Bbb Z} \rightarrow {\Bbb Z}^+$
given by $g(x) = |x| +1$ (for all integers $x$).

1a. The function $f: {\Bbb Z}^+ \rightarrow {\Bbb Z}^+$ given by f(n) = n + 1 is one-to-one.

Proof: Let a and b be positive integers such that f(a) = f(b).

Then a + 1 = b + 1 (use the definition of f to see this).

But then a = b (by “cancelling” 1’s [i.e., by subtracting 1 from each side of the previous equation]).

This proves the assertion.

[Because a and b were chosen arbitrarily from our domain and because “(\forall x, y) [f(x)=f(y)] \implies [x = y]” defines “f is one-to-one”.]

1b. The function $f: {\Bbb Z}^+ \rightarrow {\Bbb Z}^+$ given by f(n) = n + 1 is not onto.

Proof: Note that 1 is a positive integer, and so is in the codomain of f. Now suppose there exists a positive integer n satisfying “f(n) =1”. Some very simple algebra shows that then n=0. But 0 is not a positive integer (and so is not in the domain of f). So there is no such n. This proves the assertion.

[It’s very tempting for some beginners to “Let f(n) = 1” rather than use (the more elaborate) “suppose there exists n such that…” construction. But this is precisely what we can’t do (unless we already know that such an n exists…)]

9a. The function $g: {\Bbb Z} \rightarrow {\Bbb Z}^+$ given by $g(x) = |x| +1$ is not one-to-one.

Proof: Note that both 1 and -1 are integers [and so are “domain values”] and that g(1) = g(-1) = 2. Since 1 \not= -1, this proves our assertion.

9b. The function $g: {\Bbb Z} \rightarrow {\Bbb Z}^+$ given by $g(x) = |x| +1$ is onto.

Proof: Let $z \in {\Bbb Z}^+$. Since $z \ge 1$, we also have $z-1 \ge 0$, which in turn implies that $|z - 1| = z - 1$. Note that moreover $z-1 \in {\Bbb Z}$. We can now say that $g(z-1) = |z - 1| + 1 = z -1 + 1 = z$; g is onto.

[This was probably the hardest question on the exam since it calls for careful use of “absolute value”. The absolute value function is both “easy” to work with (I’ve learned that nothing is easy enough to write “easy” on the board without quote marks) and long familiar to all 366 students… but nevertheless; there it is. Only two students (in a class of 24) satisfied me completely on this one. My favorite of the rest used mathematical induction. A very good idea, oh anonymous one (but some details were lacking; minus-one-point)].