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.

Define kernel of a function $f : X \rightarrow Y$:

$$ \text{ker}\space f = \{\space (x, x')\space |\space f(x) = f(x') \space\} $$

The kernel contains pairs of equivalent inputs to $f$. Number of such pairs can be interpreted as degree to which $f$ fails to be injective: $\frac{|\text{ker}\space f|}{|X|^2} \in (0,1]$ – assuming $x = x'$ is allowed.

Similar – as wikipedia states – algebraic "kernel of a homomorphism measures the degree to which the homomorphism fails to be injective".

This triggers my questions:

  • Degree of anti-injectiveness is in fact degree of symmetry of the mathematical object being described (e.g. in the function case, the symmetry is invariance of function's value to input change). Can the kernel(s) be thus related to or described by symmetry groups?
  • Are there significant results in which kernel has key role?
share|improve this question
2  
When you have the kernel of a homomorphism from, say, one vector space to another, what is "the mathematical object being described"? The domain? The codomain? The homomorphism itself? Question not clear to me. –  Gerry Myerson May 19 '12 at 12:13
    
@GerryMyerson like the wiki page says: "(...) degree to which the homomorphism fails to be injective" –  Calikin May 19 '12 at 15:57
1  
Your definition of kernel is the standard definition of kernel in the setting of Universal Algebra; e.g., that is how the kernel of a homomorphism is defined for semigroups. In the case of groups and rings, we can "get away" with just looking at the elements that map to $0$ because the equation $f(a)=f(b)$ is equivalent to the equation $f(a-b)=0$ (for abelian groups/rings) or to $f(ab^{-1})=1$ (for multiplicative groups). The kernel can be used to define quotients, which consist precisely of "moding out" by the relation (identify things that map to the same thing). –  Arturo Magidin May 19 '12 at 20:42

1 Answer 1

up vote 5 down vote accepted

Short answer: Yes, they can be related to symmetry groups, but not in a very useful manner (they correspond to the subgroup of the permutation group of the underlying set that respects a certain partition); they are far more useful algebraically, and yes, there are very important theorems that rely on the notion of kernel, at least in Universal Algebra (and specific settings within it, like semigroup theory.)

Longer answer.

The definition you give is the standard definition of "kernel" in the context of Universal Algebra that allows the statement (and proof) of the general Homomorphism Theorems. It is also the standard way to define a kernel in semigroups.

By algebra, I mean a a set $A$ together with a set of finitary operations on $A$. The type of the algebra, or its "signature" is a description of the arities of the operations. For example, a semigroup is an algebra with signature $(2)$, because it consists of a set together with a single binary operation (the $2$ represents the fact that it is binary). A monoid is an algebra with signature $(2,0)$, because it has a binary operation (the product), and a nullary operation corresponding to the identity. A group is an algebra with signature $(2,1,0)$ (the product, the function taking each element to its inverse, and the nullary function pointing to the identity). A ring is an algebra with signature $(2,2,1,0)$ (addition, product, additive inverses, additive identity). A ring with $1$ is an algebra with signature $(2,2,1,0,0)$ (the extra nullary operation identifies the multiplicative identity), etc. I highly recommend George Bergman's An Invitation to General Algebra and Universal Constructions for much more.

A homomorphism between two algebras with the same signature is a function between their underlying sets that "respects the operations". If $\times_A$ is a binary operation on the algebra $A$, and $\times_B$ is the corresponding binary operation on the algebra $B$, for example, we require that $f(\times_A(x,y)) = \times_B(f(x),f(y))$ for all $x,y\in A$.

In this very general context, the definition of "kernel" is precisely the one you give: the kernel of a homomorphism $f$ is defined to be the set of all pairs $(x,y)$ such that $f(x)=f(y)$. This gives you an equivalence relation on $A$, but more than that: you can verify that this equivalence relation, viewed as a subset of $A\times A$, is in fact a subalgebra of $A\times A$ (where $A\times A$ is given an algebraic structure by defining the operations "componentwise"). These kinds of equivalence relations/subalgebras are called congruences, and play the same role as normal subgroups play in groups and ideal play in rings: they are precisely the kinds of equivalence relations that allow you to define meaningful quotients.

Now, it would be too difficult to continue talking in full generality, so let's consider the special case of semigroups (sets with a single binary, associative operation; I allow the empty set as a semigroup, just so you know).

Given a semigroup $S$, a congruence on $S$ is an equivalence relation on $S$ with the property that, viewed as a subset of $S\times S$, is a subsemigroup of $S$. We have the following result:

Theorem. Let $S$ be a semigroup, and let $\sim$ be an equivalence relation on $S$. Let $S/\sim$ be the set of equivalence classes of $\sim$ in $S$. Then $\sim$ is a congruence on $S$ if and only if the operation on $S/\sim$ defined by $${}[a]\cdot[b] = [ab]$$ is well defined, where $[x]$ is the equivalence class of $x\in S$.

Proof. Suppose $\sim$ is a congruence. We want to show that if $[a]=[x]$ and $[b]=[y]$, then $[ab]=[xy]$. If $[a]=[x]$ and $[b]=[y]$, then $(a,x),(b,y)\in \sim$; since $\sim$ is a subsemigroup of $S\times S$, the product of $(a,x)$ and $(b,y)$ is also in $\sim$, so $(a,x)(b,y) = (ab,xy)\in \sim$, hence $[ab]=[xy]$, as desired.

Conversely, assume that $[a]\cdot[b] = [ab]$ is well defined. Let $(a,x),(b,y)\in\sim$; we need to show that $(ab,xy)\in \sim$. But $[ab]=[a]\cdot[b]=[x]\cdot[y]=[xy]$, since $\cdot$ is well-defined, so $(ab,xy)\in\sim$, as desired. $\Box$

And:

Theorem. Let $S$ be a semigroup, and let $\Phi$ be an equivalence relation on $S$. Then $\Phi$ is a congruence on $S$ if and only if there exists a semigroup $T$ and a semigroup homomorphism $f\colon S\to T$ such that $$ \Phi = \{(s,t)\in S\times S\mid f(s)=f(t)\} = \mathrm{ker}(f).$$

Proof. Assume that $\Phi$ is a congruence. Then $(S/\Phi,\cdot)$ is a semigroup, since $\cdot$ is well-defined, and $${}\Bigl([a]\cdot[b]\Bigr)\cdot[c] = [ab]\cdot[c] = [(ab)c] = [a(bc)] = [a]\cdot[bc] = [a]\Bigl([b]\cdot[c]\Bigr).$$ Now let $f\colon S\to S/\Phi$ be given by $f(a)=[a]$. Then $f$ is a homomorphism, and $\mathrm{ker}(f) = \Phi$, since $f(a)=f(b)$ if and only if $[a]=[b]$ if and only if $(a,b)\in\Phi$.

Conversely, we prove that the kernel of a homomorphism is a congruence. It is straightforward that it is an equivalence relation; to show it is a congruence, it suffices to show that if $(a,b),(x,y)\in\mathrm{ker}(f)$, then $(ax,by)\in\mathrm{ker}(f)$. Indeed, we have $f(a)=f(x)$ and $f(b)=f(y)$, hence, since $f$ is a homomorphism, $$f(ab) = f(a)f(b) = f(x)f(y) = f(xy)$$ so $(ab,xy)\in \mathrm{ker}(f)$. Thus, $\mathrm{ker}(f)$ is a congruence on $S$. $\Box$

Now we can state the homomorphism theorems in terms of congruences: if $f\colon S\to T$ is a homomorphism, then $f(S)$ is isomorphic to $S/\mathrm{ker}(f)$; if $\Phi$ is a congruence on $S$, then a homomorphism $f\colon S\to T$ factors through $S/\Phi$ if and only if $\mathrm{ker}(f)\subseteq \Phi$. There is a one-to-one, inclusion preserving correspondence between congruences of $S/\Phi$ and congruences of $S$ that contain $\Phi$. And if $\psi$ is a congruence of $S/\Phi$ and $\Psi$ is the corresponding congruence on $S$, then $(S/\Phi)/\Psi \cong S/\Psi$.

In the group and ring setting, you can get away with subgroups and ideals instead of congruences because we have inverses: $f(a)=f(b)$ if and only if $f(ab^{-1})=1$ ($f(a-b)=0$ in the ring/additive group setting). So in fact a congruence $\Phi\subseteq A\times A$ is completely determined by $\Phi\cap(A\times\{1\})$ (in the group setting; by $\Phi\cap(A\times\{0\}$ in the ring/additive group setting).

In that sense, the kernel of $f$ plays exactly the same role as the kernel (in the usual sense) of a linear transformation , group homomorphism, or ring homomorphism plays in terms of "measuring how far $f$ is from being one-to-one". If you think about the kernel of a linear transformation, it does not really open the door to an action of a symmetric group or to some sort of "symmetry" on the vector space, except perhaps for talking about the permutations of the vector space that respect the partition induced by the kernel (the cosets of the kernel, in the group/ring setting).

share|improve this answer
1  
+1 This is a nice answer. –  dtldarek May 22 '12 at 9:18

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.