Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

this is an elementary doubt ,i am not asking advance mathematics ,please dont close this i have been having this doubt,

many-to one functions are not injective ,but they can be onto i mean let us take the following example

let $f : N \times N \mapsto N$ be a many to one function defined by $f(a,b)=a.b$ but how can we prove that the function is onto ????

in general how can we prove the surjectiveness of many to one functions

suppose let us take the number $n$ to be the count of the cardinality of elements that function binds and sends to the other side,i mean the codomain in the above example the value of $n$ is $2$ (as function $f$ sends the 2 elements $a$ and $b$ to the another side )

so how can we prove the surjectiveness of the function, i mean the definition is bit manipulated ,

the new version of the definition seems to be

"for every $y \in $ Codomain $\exists (x_1,x_2....x_n) \in $ Domain such that $f(x_1,x_2....x_n)=y$ , which is a new surjective function notion

please suggest your valuable comments in proving the surjectiveness of many to one functions (i think that word surjectiveness dont exist as the editor is showing red line,but that words gits rightly)

i mean ,how to prove that a many to one function is onto

thanks a lot,to one and all

share|cite|improve this question
@Willie Wong:thanks a lot mr.wille wong sir,for editing,i am in debt with your help – Iyengar Sep 3 '11 at 15:04
You know (i) that the personal pronoun "I" is not written as "i" and (ii) that sentences begin with capital letters, and ordinarily end with a period. When the non-standard English is due to infrequent use, that is fine. But why add to that the deliberate use of non-standard English? – André Nicolas Sep 3 '11 at 15:09
sorry sir,i dont know these protocols as i dont come from a sophisticated background,i am a self-taught person,i will surely rectify myself@andre – Iyengar Sep 3 '11 at 15:12
When you say $x_1, x_2, \ldots, x_n\in$ Domain, do you mean that the ordered tuplet $(x_1,x_2,\ldots,x_n)$ is in the domain, or do you mean that each of the $x_1, x_2, \ldots$ is an element of Domain? – Willie Wong Sep 3 '11 at 16:07
@Willie Wong:sorry sir it is the tuple,i am a stupid i dont know even syntax forgive me sir – Iyengar Sep 3 '11 at 16:09
up vote 3 down vote accepted

With your first example, we can prove that it is onto by giving a representation for every natural number (that is, the range). In particular, since $1 \cdot n = n$ for all $n$, this shows that every natural number gets hit. How often? Well, each number gets hit a number of times equal to its number of factorizations (including the trivial one). So that's that one.

But this really isn't so different than any other function. In general, to show a function is onto you must show that it takes every value in the range. Sometimes you do it explicitly. Sometimes you talk about continuity and limits and intermediate values. And sometimes, it's too hard to efficiently say. There's no single, all-powerful method, and like many things in math, it is often easier to prove that something is not onto (or some other property) by finding a single counterexample than to prove that it is.

share|cite|improve this answer
sir ,thanks a lot for your answer,but i was just mentioning about the function as an example,not concentrating solely on it,but i am asking for general way,i mean if there was only one way like the standard elementary proof,like step 1:we consider the function $y=f(x)$ and then we take $x=f^{-1}(y)$ and then proceed to prove the onto of a function ok – Iyengar Sep 3 '11 at 14:52
@iyengar Finding inverses is hard, in general (even when they do exist). And as you have noticed, many-to-one functions are not invertible. – mixedmath Sep 3 '11 at 14:55
and what the thing i want to ask is that ,is there any similar procedure but this case we have more than one variable its like $f(x_1,x_2....x_n)=y$ then $x_1,x_2.....x_n=f^{-1}(y)$ and then it becomes a problem to verify – Iyengar Sep 3 '11 at 14:56
math:and i read a very deep result that depends upon the P vs NP problem, many-to-one function is invertible if and only if P = NP. see here – Iyengar Sep 3 '11 at 15:02
@iyengar: a many-to-one function is not invertible. Period. The relation with P=NP is about computational complexity of partial inverses, not about the existence of inverse function. – Willie Wong Sep 3 '11 at 15:06

It appears that by "many-to-one function", you mean "function of multiple arguments". If this is the case, "many-to-one function" isn't a good term to use here, because people are likely to think that you mean "non-injective function" or "surjective function".

Functions of multiple arguments can be injective, surjective, both, or neither. An example of an injective function is $f : (\mathbb{Z} \times \mathbb{Z}) \to \mathbb{R}$ where $f(a,b) = a + b \sqrt{2}$. One surjective function is the one you gave: $g : (\mathbb{Z} \times \mathbb{Z}) \to \mathbb{Z}$ where $g(a,b) = ab$. There are plenty of bijective functions $h : (\mathbb{N} \times \mathbb{N}) \to \mathbb{N}$; one of them is the Cantor pairing function.

An easy way to treat functions of multiple arguments is to treat them as functions of one argument, where that argument is an ordered pair. Consider the equation $g(3,5) = 15$. We can say that $g$ is taking one argument, $(3,5)$, and returning $15$. This way, the definitions of "injective" and "surjective" that we are used to still work, with no changes.

So, how do you prove that $g : (\mathbb{Z} \times \mathbb{Z}) \to \mathbb{Z}$ is surjective? The same way you would prove it for a function of one argument. You assume that $y$ is an element of $\mathbb{Z}$, and you prove that there exists an element $x$ of $\mathbb{Z} \times \mathbb{Z}$ (that is, an ordered pair $x$ of integers) such that $g(x) = y$. In this case, you can simply let $x = (1,y)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.