Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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
1  
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
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

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.