1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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.) $\endgroup$
    – anon
    May 19, 2012 at 17:22
  • $\begingroup$ 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? $\endgroup$
    – zell
    May 19, 2012 at 17:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – plm
    May 19, 2012 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    May 19, 2012 at 19:43

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – plm
    May 19, 2012 at 17:53
  • $\begingroup$ @ plm: Find out the quotient set. $\endgroup$
    – users31526
    May 19, 2012 at 17:59
  • $\begingroup$ @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.) $\endgroup$
    – plm
    May 19, 2012 at 18:23
  • $\begingroup$ @ plm :zell(problem poster) already prescribe an equivalence relation..so you should not take another.. $\endgroup$
    – users31526
    May 19, 2012 at 19:18
  • $\begingroup$ Are you kidding? What equivalence relation does zell "prescribe"? $\endgroup$
    – plm
    May 20, 2012 at 0:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .