# Proving a function is one-to-one

what is the easiest way to prove a function si one to one? Also to prove it's not one to one...

Deﬁne $f : \mathbb{N} \to \mathbb{N}$ by $f(n) = \cdots$. Deﬁne $g : \mathbb{N}\times\mathbb{N} \to N$ by $g(m, n) = \cdots$.

For $f$ and $g$ I need to say if it's one to one or not one to one, I'm not sure what kind of values I should expect (it's a very entry level course into discrete mathematics) Would anyone be able to hazard a bit of a guess as to what the values should be?

-
To prove f is a one-to-one function, I'd check whether f(a) = f(b) implies a = b. To prove it not, I'd look for a counter-example. I don't think you need any further expectations/guessing. –  Ahmed Abdelkader Nov 7 '11 at 11:06
@jolpi: I am not sure what this question is asking exactly? Do you want us to suggest some exercises, on which you can try your understanding of this notion? –  Martin Sleziak Nov 7 '11 at 11:14
@MartinSleziak that would be good if you wouldn't mind. –  jolpi Nov 7 '11 at 11:19
I think the comments you got to your previous question, math.stackexchange.com/questions/79399/basic-relation-help apply here, too. Anyway, there are books full of worked exercises. For example, there is a Schaum's Outline on Discrete Mathematics. –  Gerry Myerson Nov 7 '11 at 11:29
Perhaps you can find a few exercises by yourself: exercise "one-to-one" function or exercise injective function. –  Martin Sleziak Nov 7 '11 at 11:41

What is the easiest way to prove that a given function is one-to-one? Depends on the function!

For some functions, the definition is simplest: show that if you have $a$ and $b$ in the domain such that $f(a)=f(b)$, then you can conclude that $a=b$.

For some functions, the contrapositive of the definition is simplest: show that if $a$ and $b$ are in the domain and $a\neq b$, then $f(a)\neq f(b)$.

For yet other functions, it is easier to prove they are one-to-one by showing that they have a left inverse: that is, if $f\colon X\to Y$, then coming up with a function $g\colon Y\to X$ such that $g\circ f = \mathrm{id}_X$, the identity of $X$; this immediately implies that $f$ is one-to-one.

When the sets have other structure, there may be other tools available (showing that a linear transformation is one-to-one can be done by showing that if $T(\mathbf{x})=\mathbf{0}$, then $\mathbf{x}=\mathbf{0}$, for example).

Which one is easiest? Depends on the function.

What's the easiest way to show that a function is not one-to-one? The absolutely, definitely best way is to exhibit two specific elements in the domain, $a$ and $b$, showing that $a\neq b$, and then showing that $f(a)\neq f(b)$. In fact, I would say that 99% of the "proofs that a function is not one-to-one" should at the very list end with such an explicit example.

How do you find such examples? Again, it depends on the function. Sometimes you try to see if the function is one-to-one by considering what you can conclude if $f(a)=f(b)$; this will lead you to a relationship between $a$ and $b$, and often you can see that the relation can be satisfied with $a\neq b$. This will lead you to an example. For instance, to show that $f\colon\mathbb{R}\to\mathbb{R}$ defined by $f(x)=x^2$ is not one-to-one, you could go through the following thought process:

"I wonder if it is one to one... let's see... if $f(a)=f(b)$, then this means that $a^2=b^2$; taking square roots, that says that $|a|=|b|$... ah! but that can happen even if $a\neq b$! For instance, if $a=-b$... Okay, so here's a proof that $f$ is not one-to-one: take $a=1$, $b=-1$. Then $a\neq b$, and $f(a)=f(1) = 1$, $f(b)=f(-1) = 1$. So $f(a)=f(b)$, and this shows that $f$ is not one-to-one."

Which one is easiest? Depends on the function.

-

How about $f(n) = n$ and $g(m,n) = n + m$?

Here is a recipe on how to come up with your own examples:

Go look up the definition of function. Then notice that when making up your own functions all you need to pay attention to is that you don't have one value in the domain map to two values in the range.

What I'm saying is: before you try to work with functions by proving or disproving properties about them, you need to know your definitions.

-
Coming from someone who does exactly that themselves sometimes this might seem like amusing advice but so there. –  Rudy the Reindeer Nov 7 '11 at 11:57

I still think that this is not an appropriate question for this forum, nevertheless a few standard exercises:

1. Let $\mathbb N=\{0,1,2,3,\dots\}$. Are the following functions from $\mathbb N$ to $\mathbb N$ injective?

• $a(n)=n+1$
• $b(n)=2n$
• $c(n)=\lfloor \sqrt n \rfloor$
• $d(n)= \begin{cases} n+1,&n \text{ is even}\\n-1,&\text{otherwise}\end{cases}$
• $e(n)=n^2$
• $f(n)=n(n+1)$
• $g(n)=n^2-n$
2. Are the following functions from $\mathbb N\times\mathbb N$ to $\mathbb N$ injective?

• $a(m,n)=m+n$
• $b(m,n)=m\cdot n$
• $c(m,n)=\frac{(m+n)(m+n+1)}2+n$ (this one is slightly more difficult, you can have a look at the solution here)
3. Perhaps you can also find a few exercises by searching stackexchange:

-