-1
$\begingroup$

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

  • 0
    @Willie Wong:sorry sir it is the tuple,i am a stupid i dont know even syntax forgive me sir2011-09-03

2 Answers 2

3

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.

  • 0
    @iyengar There is a theorem that determines whether a function is locally invertible: http://en.wikipedia.org/wiki/Inverse_function_theorem That's the closest thing to being relevant at all that I can think of.2011-09-03
1

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)$.