Transversal (combinatorics): Difference between revisions

Revision as of 12:03, 12 April 2015

Revision as of 12:04, 12 April 2015

Line 10:

In general, since any [[equivalence relation]] on an arbitrary set gives rise to a partition, picking any representative from each [[equivalence class]] results in a transversal.

Another instance of this partition-induced transversal occurs when one considers the equivalence relation known as the [[Kernel (set theory)|(set-theoretic) kernel of a function]]: :, <math>\operatorname{ker} f := \{(x,y) \mid f(x) = f(y)\}</math>. If ''f'' is injective, there's a unique transversal of <math>\operatorname{ker} f</math>. For a not-necessarily-injective ''f'', a fixed transversal ''T'' of <math>\operatorname{ker} f</math> induces a one-to-one correspondence between ''T'' and the [[Image_%28mathematics%29#Image_of_a_function|image]] of ''f'', thus a function ''g'' with the property that for all ''x'' in ''T'', <math>g(z) = x</math> when <math>f(x)=z</math> is well defined with ___domain the image of ''f'' and [[codomain]] ''T''; ''g'' can be extended so that it is defined on the whole codomain of ''f'' by picking arbitrary values for ''g(z)'' when ''z'' is outside the image of ''f''. Furthermore, it a simple calculation to verify that <math>f\circ g \circ f = f</math>, which is the proof (when the ___domain and codomain of ''f'' are the same set) that the [[full transformation semigroup]] is a [[regular semigroup]]. <math>g</math> acts as a (not necessarily unique) [[Inverse_element#In_a_semigroup|quasi-inverse]]; within semigroup theory this is simply called an inverse. Note however that for an arbitrary ''g'' with the aforementioned property the "dual" equation <math>g \circ f \circ g= g</math> may not hold. However if we denote by <math>h= g \circ f \circ g</math>, then ''f'' is a quasi-inverse of ''h'', i.e. <math>h \circ f \circ h = h</math>.

<!-- this calculation is rather hard to follow without a picture, so I'm not sure it adds much as it is

As a concrete instance, if <math>f: \{1,2,3\} \to \{1,2,3\}</math> is the non-bijective mapping <math>f(1) = 2, f(2)=2, f(3)=3</math>, then its kernel is <math>\operatorname{ker} f = \{ \{1,2\}, \{3\} \}</math>. A transversal of <math>\operatorname{ker} f</math> is <math>T_1 = \{ \{1\}, \{3\} \}</math> and another transversal is <math>T_2 = \{ \{2\}, \{3\} \}</math>. Fixing <math>T_1</math> as the choice of transversal, a function <math>g</math> induced by <math>T_1</math> must have the property that <math>g(2) = 1</math> and <math>g(3) = 3</math>; however the transversal <math>T_1</math> does not constrain where ''g'' maps 1. Nevertheless, it can be verified that ''g'' has the desired quasi-inverse role relative to ''f'': <math>f(g(f(1))) = f(g(2)) = f(1)</math>, <math>f(g(f(2))) = f(g(2)) = f(1) = 2 = f(2)</math>, <math>f(g(f(3))) = f(g(3)) = f(3)</math>. Note that <math>g(1)</math> did not appear in these calculations. One could choose <math>g(1)=2</math>, a choice that makes ''g'' bijective; therefore, we expect that <math>g \circ f \circ g = h \neq g</math>. And indeed <math>h(1) = g(f(g(1)))=1\neq 2 = g(1)</math>. However <math>h(f(h(1)))=h(f(1))=h(2)=g(f(g(2))= g(2)=1</math> is compatible with the role of ''f'' as quasi-inverse of ''h''.