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

Is it possible to convert a one-to-many function to a one-to-one function.
The input is going to be unique and hence the out of the function should also be unique.
Repeating output would only create more ambiguity when the reverse mapping is to be done.
I hope the question makes some sense.
Thanks in advance.

share|cite|improve this question
One way to create a genuine function from a one-to-many relation is to enlarge the "domain". For example, if you have a one-to-many binary relation $R$ which is a subset of $X\times Y$ (so $X$ might be thought of as the "domain" of $R$) then there's a natural function $f\colon R\to Y$ given by $f((x,y))=y$. You could think of the passage from $R$ to $f$ as fattening up the domain from $X$ to $R$. – mac Apr 15 '11 at 19:46
Or something else you could do is to change the "codomain" to the power set of $Y$: define $g:X\to \mathcal{P}(Y)$ by $g(x)=\{ y\in Y\colon (x,y)\in R\}$. I guess one nice thing about both of these is that you don't lose any information: you can recover $R$ from both $f$ and $g$. – mac Apr 15 '11 at 19:46
A one-to-many "function" is a one-to-one function from your domain into a space of sets. – Raphael Apr 15 '11 at 19:55
What is the domain/range of your function/relation? discrete? over integers? over reals? continuous? any other details that might help? – Mitch Apr 16 '11 at 15:53

One-to-many relations are usually not called "functions", since a function by definition has a single function value for each element of its domain.

If you have a one-to-many relation on a finite domain, you can always define a function by arbitrarily choosing one of the possible function values for each element of the domain. If the domain is infinite, you can also assume that such a function (defined by infinitely many choices) exists if you don't care about foundational issues. If you do, then you either need a rule that specifies a unique choice of function value for each element of the domain, or you need the axiom of choice, which guarantees that such a function exists even if you can't specify it.

share|cite|improve this answer

Yes (with suitable interpretation of 1-many and 1-1: 1-1 has a particular technical meaning by itself that at most one item of the domain relates to any given item of the codomain, but I take it that you mean can you make a function out of a relation that is not functional (the converse of the technical meaning of 1-1). And I take it that that is what you're looking for.

This could be done arbitrarily in many ways (choose randomly one output), but I think the most reasonable construction would be to reimagine the range as over the powerset of the original range. To explain, suppose you have a relation $R$ between $D$ a domain and $C$ a codomain, that is $$R\subseteq D\times C.$$

A function is a relation $F\subseteq D\times C$ such that there is at most one element of $C$ corresponding to an element of $D$ (in the relation graph the outdegree of any vertex is at most 1).

To create $R_F$ as a version of $R$ that preserves all the 'values' but is functional somehow, use the powerset of $D$:

$$R_F = D\times 2^C : p = \{c| (d,c) \in R\} \implies (d, p) \in R_F.$$

So now $R_F$ is a function, because at most one element of $2^C$ is associated with any $d \in D$.

That might very well be overkill, and all you want is to get rid of duplicates either in the domain -or- codomain. Then you can just arbitrarily remove duplicates. Or if you want to assume continuity/differentiability, you can omit segments that have negative first derivative.

share|cite|improve this answer
Thanks for the informative replies. As Mitch said removing duplicates is where the main problem lies. I am scaling a set of co-ordinates, which is in turn generating the duplicates. The reverse mapping gets screwed because of the duplicates. – user9629 Apr 16 '11 at 8:32

yes, if you are free to change its range. lets define a relation $f\subseteq( \mathbb R^+\times\ \mathbb R^+)$. lets further define $max(\mathbb R^+) = lim_{l\to \text{infinity}}l, l\in \mathbb R^+$. $\delta x$ can be defined as $lim_{x_f \rightarrow x_i} x_f - x_i$ if '$i$' and '$f$' here represents initial and final respectively. Its possible to convert this to one to one relation if we have the freedom to alter the range of the original relation. For this particular case we may extend the present range which is $\mathbb R^+$ to $U$ which can be defined as, $U=\{x:x\in [0,l^{n+1} \text{ where the least count is }\delta x\}$. we may also wright $\delta x $ as, $\frac 1l$. We can define a relation $f'\subset (U\times U)$ (if $(i,j) \in f'$ then $(i,k) \notin f'$ though $k\in U$ or if $(j,i) \in f'$ then $(k,i) \notin f'$ though $k\in U$).

we can convert $f$ to $f'$ in the following way: let $x \in \mathbb R $ be mapped with $n$ number of solutions present in the set $A=\{y_1, y_2, ..., y_n\}$; then this can be represented in the function $f'$ as (x,$\sum_{i=0}^n l^{i-1}y_i)$. The same method can also be adapted in converting many to one to one to one relation.

converting a one to many to one to one can be accomplished by changing its range as, you will have to represent a set of elements in the same value. If you are representing $n$ elements of a set, then you would need to modify the set's range to $U$.

set theory in general is only a way (or language) of representing information and it doesn't matter how the information is represented, but what matters is its readability and elegance.

share|cite|improve this answer

Your Answer


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