# Unique decomposition of a mapping by an equivalence relation

I have a math question from computer science. The following should be a fundamental fact from mathematics. Can you the mathematicins tell me how you would say it in a more elegant way?

Given

1. a mapping f: A=>B
2. an equivalence relation ~ on A

satisfying,

for each a1,a2 of A, a1 ~ a2 implies f(a1)=f(a2)

Then, there exists a unique factorisation of the mapping f

$f= g \circ h$

such that

1. h is a mapping from A to a A/~
2. g is a mapping from A/~ to B.

There must be some more elegant way to say this in mathematics, like some algebra thing with isomorphism, congruence, or quotient etc. as keywords. I would like to avoid terms from category theory if possible, because that is too much for most computer scientists.

So, I am looking for a mathematical way to say the above fact. It seems really close to the first isomorphism theorem. Any idea? Thanks.

-
Of course $h$ isn't just any map from $A$ to $A/\sim$: it's the quotient map in particular, sending $a$ to the equivalence class $[a]$. One could say $f$ is constant on equivalence classes, but perhaps the best way to phrase this is basically already in your question: "$f$ factors through the quotient map." At least IMHO. (Uniqueness is a logically necessary feature of the factorization, so it goes without saying.) –  anon May 19 '12 at 17:22
Thank you. Maybe I do not yet understand. (1) Do you think the claim is correct? (2) Do you think there is some algebra-related theorems like isomorphism theorem that can state this fact in a more elegant way? –  zell May 19 '12 at 17:29
Actually the decomposition is not necessarily unique. If you take $f$ a constant map and equality as equivalence relation on a 2 element set, you can take either $h$ the identity or the permutation of your 2 elements, and $f=G$ and this gives 2 factorizations. You must fix $h$. Then you are unfortunately looking at a categorical construction, the quotient, the initial object among objects with an $h$ which allow such unique factorizations. –  plm May 19 '12 at 17:48
This is precisely the universal property of the quotient set (which can be expressed equivalently in the language of partitions). If $\rm\:F = ker\: f\supseteq ker\: h\: = H\:$ then $\rm\:A/F\:$ is a quotient of $\rm\:A/H,\:$ i.e. $\rm\:A/H\:$ is the most general (universal) quotient of $\rm\:A\:$ whose kernel contains $\rm\:H.$ This is essentially the content of the second isomorphism theorem. Here $\rm\:ker\:f = \{(a,b)\in A^2: f(a) = f(b)\},\:$ which is clearly an equivalence relation. –  Bill Dubuque May 19 '12 at 19:43

Without loss of generality let $f:A\rightarrow B$ is onto [if not take $B=range(f)$] then from the quotient set of $A$ w.r.t given equivalence relation the induced function becomes $1-1$ (from your observation it is $g$).

You already observed the existence. Only remaining part is this decomposition is unique. Since your $h$ is unique (canonical map) and $g$ is invertible there is no other way to factorize $f$.

Q.E.D

-
Why would $g$ be injective (1-to-1)? Take $f$ a constant map on a 2-element set $\{0,1\}$, say $f(x)=0$, let ~ be equality and $h$ the identity on $\{0,1\}$. $g=f$ is not injective, not invertible. –  plm May 19 '12 at 17:53
@ plm: Find out the quotient set. –  users31526 May 19 '12 at 17:59
@Knashik, since I take equality as equivalence relation the quotient is basically the same set. (Actually it is $\{\{0\},\{1\}\}$, with the standard construction of quotient as the set of equivalence classes, the partition induced by an equivalence relation.) –  plm May 19 '12 at 18:23
@ plm :zell(problem poster) already prescribe an equivalence relation..so you should not take another.. –  users31526 May 19 '12 at 19:18
Are you kidding? What equivalence relation does zell "prescribe"? –  plm May 20 '12 at 0:30
show 1 more comment