### Discrete Math Final: Questions 8 and 9

8.Consider the function

given by (for all positive integers ).

a.Isfone-to-one? (Prove your answer.)

b.Isfonto? (Prove your answer.)

9.Now consider

given by (for all integers ).

a.Isgone-to-one? (Prove your answer.)

b.Isgonto? (Prove your answer.)

1a. The function 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 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 given by 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 given by *is* onto.

**Proof:** Let . Since , we also have , which in turn implies that . Note that moreover . We can now say that ; 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)].*

## Leave a Comment