Homomorphism

From Wikipedia, the free encyclopedia

(Redirected from Homomorphisms)

Not to be confused with homeomorphism.

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). The word homomorphism comes from the Greek language: ὁμός (homos) meaning "same" and μορφή (morphe) meaning "shape". Note the similar root word ὅμοιος (homoios), meaning "similar," which is found in another mathematical concept, namely homeomorphisms.

[edit] Definition and illustration

[edit] First example: even and odd integers

The integers are one of the most basic examples of a group, and it is common to denote this group by Z. The addition of even and odd numbers obey familiar equations:

even + even = even
even + odd = odd
odd + even = odd
odd + odd = even

With this in mind, let us define X to be the two element set {"even" , "odd"}. The above equations define an addition operation on this set, and they give us another basic example of a group. Here "even" is the identity element in X.

Let us define a map from Z to X by sending every even integer to "even" and every odd integer to "odd". Then the identity in Z (i.e. zero) is sent to the identity in X (i.e. "even", since zero is an even number). The addition operation is preserved under this map, because the even and odd integers obey the above relations. This map is an example of a group homomorphism from Z to X.

[edit] Definition

The definition of homomorphism depends on the kind of algebraic structure in question. For example, the definition of a homomorphism of groups is different from the definition of a homomorphism of rings. Nevertheless, we can generally say that a homomorphism is a map from one algebraic structure to another of the same type that preserves all the relevant structure; it maps identity elements to identity elements, and it is compatible with all binary operations.

For example, if one considers two sets X and Y with a single binary operation defined on them (an algebraic structure known as a magma), a homomorphism is a map $\phi: X \rightarrow Y$ such that

$\phi(u \cdot v) = \phi(u) \circ \phi(v)$

where $\cdot$ is the operation on $X$ and $\circ$ is the operation on $Y$ .

Each type of algebraic structure has its own type of homomorphism. For specific definitions see:

group homomorphism
ring homomorphism
module homomorphism
linear operator (a homomorphism on vector spaces)
algebra homomorphism

The notion of a homomorphism can be given a formal definition in the context of universal algebra, a field which studies ideas common to all algebraic structures. In this setting, a homomorphism $\phi: A \rightarrow B$ is a map between two algebraic structures of the same type such that

$\phi(f_A(x_1, \ldots, x_n)) = f_B(\phi(x_1), \ldots, \phi(x_n))\,$

for each n-ary operation $f$ and for all $x i$ in $A$ .

[edit] Informal discussion

Because abstract algebra studies sets with operations that generate interesting structure or properties on the set, the most interesting functions are those which preserve the operations. These functions are known as homomorphisms.

For example, consider the natural numbers with addition as the operation. A function which preserves addition should have this property: f(a + b) = f(a) + f(b). For example, f(x) = 3x is one such homomorphism, since f(a + b) = 3(a + b) = 3a + 3b = f(a) + f(b). Note that this homomorphism maps the natural numbers back into themselves.

Homomorphisms do not have to map between sets which have the same operations. For example, operation-preserving functions exist between the set of real numbers with addition and the set of positive real numbers with multiplication. A function which preserves operation should have this property: f(a + b) = f(a) * f(b), since addition is the operation in the first set and multiplication is the operation in the second. Given the laws of exponents, f(x) = e^x satisfies this condition : 2 + 3 = 5 translates into e² * e³ = e⁵.

A particularly important property of homomorphisms is that if an identity element is present, it is always preserved, that is, mapped to the identity. Note in the first example f(0) = 0, and 0 is the additive identity. In the second example, f(0) = 1, since 0 is the additive identity, and 1 is the multiplicative identity.

If we are considering multiple operations on a set, then all operations must be preserved for a function to be considered as a homomorphism. Even though the set may be the same, the same function might be a homomorphism, say, in group theory (sets with a single operation) but not in ring theory (sets with two related operations), because it fails to preserve the additional operation that ring theory considers.

[edit] Relation to category theory

Since homorphisms are morphisms, the following specific kinds of morphisms defined in any category are defined for homomorphisms as well. However, the definitions in category theory are somewhat technical. In the important special case of module homomorphisms, and for some other classes of homomorphisms, there are much simpler descriptions, as follows:

An isomorphism is a bijective homomorphism.

An epimorphism is a surjective homomorphism.

A monomorphism (also sometimes called an extension) is an injective homomorphism.

An endomorphism is a homomorphism from an object to itself.

An automorphism is an endomorphism which is also an isomorphism.

These descriptions may be used in order to derive several interesting properties. For instance, since a function is bijective if and only if it is both injective and surjective, a module homomorphism is iso if and only if it is both mono and epi.

For endomorphisms and automorphisms, the descriptions above coincide with the category theoretic definitions; the first three descriptions do not. For instance, the precise definition for a homomorphism f to be iso is not only that it is bijective, and thus has an inverse f^-1, but also that this inverse is a homorphism, too. This has the important consequence that two objects are completely indistinguishable as far as the structure in question is concerned, if there is an isomorphism between them. Two such objects are said to be isomorphic.

Actually, in the algebraic setting (at least within the context of universal algebra) this extra condition on isomorphisms is automatically satisfied. However, the same is not true for epimorphisms; for instance, the inclusion of Z as a (unitary) subring of Q is not surjective, but an empimorphic ring homomorphism^[1]. This inclusion thus also is an example of a ring homorphism which is both mono and epi, but not iso.

Relationships between different kinds of module homomorphisms.
H = set of Homomorphisms, M = set of Monomorphisms,
P = set of ePimorphisms, S = set of iSomorphisms,
N = set of eNdomorphisms, A = set of Automorphisms.
Notice that: M ∩ P = S, S ∩ N = A,
(M ∩ N) \ A and (P ∩ N) \ A contain only homomorphisms from some infinite modules to themselves.

[edit] Kernel of a homomorphism

Main article: Kernel (algebra)

Any homomorphism f : X → Y defines an equivalence relation ~ on X by a ~ b iff f(a) = f(b). The relation ~ is called the kernel of f. It is a congruence relation on X. The quotient set X/~ can then be given an object-structure in a natural way, i.e. [x] * [y] = [x * y]. In that case the image of X in Y under the homomorphism f is necessarily isomorphic to X/~; this fact is one of the isomorphism theorems. Note in some cases (e.g. groups or rings), a single equivalence class K suffices to specify the structure of the quotient; so we can write it X/K. (X/K is usually read as "X mod K".) Also in these cases, it is K, rather than ~, that is called the kernel of f (cf. normal subgroup, ideal).

[edit] Homomorphisms of relational structures

In model theory, the notion of an algebraic structure is generalized to structures involving both operations and relations. Let L be a signature consisting of function and relation symbols, and A, B be two L-structures. Then a homomorphism from A to B is a mapping h from the domain of A to the domain of B such that

h(F^A(a₁,…,a_n)) = F^B(h(a₁),…,h(a_n)) for each n-ary function symbol F in L,
R^A(a₁,…,a_n) implies R^B(h(a₁),…,h(a_n)) for each n-ary relation symbol R in L.

In the special case with just one binary relation, we obtain the notion of a graph homomorphism.

[edit] Homomorphisms and e-free homomorphisms in formal language theory

Homomorphisms are also used in the study of formal languages.^[2] Given alphabets $Σ 1$ and $Σ 2$ , a function h : $\Sigma_1^*$ → $\Sigma_2^*$ such that $h (u v) = h (u) h (v)$ for all u and v in $\Sigma_1^*$ is called a homomorphism on $\Sigma_1^*$ .^[3] Let e denote the empty word. If h is a homomorphism on $\Sigma_1^*$ and $h(x) \ne e$ for all $x \ne e$ in $\Sigma_1^*$ , then h is called an e-free homomorphism.

[edit] See also

morphism
graph homomorphism
continuous function
homeomorphism
diffeomorphism
Homomorphic secret sharing - A simplistic decentralized voting protocol.

[edit] References

^ Exercise 4 in section I.5, in Saunders Mac Lane, Categories for the Working Mathematician, ISBN 0-387-90036-5
^ Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0 7204 2506 9.
^ In homomorphisms on formal languages, the * operation is the Kleene star operation. The $\cdot$ and $\circ$ are both concatenation, commonly denoted by juxtaposition.

A monograph available free online:

Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.

[0] Exercise 4 in section I.5, in Saunders Mac Lane, Categories for the Working Mathematician, ISBN 0-387-90036-5

[1] Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0 7204 2506 9.

[2] In homomorphisms on formal languages, the * operation is the Kleene star operation. The $\cdot$ and $\circ$ are both concatenation, commonly denoted by juxtaposition.

[1]

[2]

[3]

Homomorphism

From Wikipedia, the free encyclopedia

Contents

[edit] Definition and illustration

[edit] First example: even and odd integers

[edit] Definition

[edit] Informal discussion

[edit] Relation to category theory

[edit] Kernel of a homomorphism

[edit] Homomorphisms of relational structures

[edit] Homomorphisms and e-free homomorphisms in formal language theory

[edit] See also

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages