Transversal (combinatorics): Difference between revisions

Revision as of 12:23, 12 April 2015

Revision as of 12:29, 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 a partition-based transversal occurs when one considers the equivalence relation known as the [[Kernel (set theory)|(set-theoretic) kernel of a function]], <math>\operatorname{ker} f := \left\{(x\,y) \left\{\, w \in X \mid f(x) = f(yw) \,\right\} \mid x \in X \,\right\}.</math>, which partitions the ___domain of ''f'' into equivalence classes such that all elements in a class map via ''f'' to the same value. If ''f'' is injective, there is only one transversal of <math>\operatorname{ker} f</math>. For a not-necessarily-injective ''f'', fixing a 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'', henceforth denoted by <math>\operatorname{Im}f</math>. Consequently, a function <math>g: (\operatorname{Im} f) \to T</math> is well defined by the property that for all ''z'' in <math>\operatorname{Im} f, g(z)=x</math> where ''x'' is the unique element in ''T'' such that <math>f(x)=z</math>; furthermore, ''g'' can be extended (not necessarily in a unique manner) 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''. It is a simple calculation to verify that ''g'' thus defined has the property 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]] for ''f''; 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''.