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.

  • 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.2012-05-19

1 Answers 1

1

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

  • 0
    Equality is one example of an equivalence relation. $g$ need not be injective. I think you may be assuming that the equivalence relation is defined by $x\sim y$ iff $f(x)=f(y)$ , but it is not, the implication only goes one way, to allow any element in an equivalence class, say $\[x\]$ to be taken to define $g(\[x\])$.2012-05-20