In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word homomorphism comes from the ancient Greek language: ὁμός (homos) meaning "same" and μορφή (morphe) meaning "form" or "shape".
The concept of homomorphism has been generalized, under the name of morphism, to many other structures that either do not have a underlying set, or are not algebraic. This generalization is the starting point of category theory.
A homomorphism is a map between two algebraic structures of the same type (that is of the same name), that preserves the operations of the structures. This means a map between two sets A, B equipped with the same structure such that, if ∗ is an operation of the structure (supposed here, for simplification, to be a binary operation), then
for every pair x, y of elements of A.[note 1] One says often that f preserves the operation or is compatible with the operation.
Formally, a map preserves an operation μ of arity k, defined on both A and B if
for all elements a1, ..., ak in A.
- A semigroup homomorphism is a map between semigroups that preserves the semigroup operation.
- A monoid homomorphism is a map between monoids that preserves the monoid operation and maps the identity element of the first monoid to that of the second monoid (the identity element is a 0-ary operation).
- A group homomorphism is a map between groups that preserves the group operation. This implies that the group homomorphism maps the identity element of the first group to the identity element of the second group, and maps the inverse of an element of the first group to the inverse of the image of this element. Thus a semigroup homomorphism between groups is necessarily a group homomorphism.
- A ring homomorphism is a map between rings that preserves the ring addition, the ring multiplication, and the multiplicative identity. Whether the multiplicative identity is to be preserved depends upon the definition of ring in use. If the multiplicative identity is not preserved, one has a rng homomorphism.
- A linear map is a homomorphism of vector space, That is a group homomorphism between vector spaces that preserves the abelian group structure and scalar multiplication.
- A module homomorphism, also called a linear map between modules, is defined similarly.
- An algebra homomorphism is a map that preserves the algebra operations.
An algebraic structure may have more than one operation, and a homomorphism is required to preserve each operation. Thus a map that preserves only some of the operations is not a homomorphism of the structure, but only a homomorphism of the substructure obtained by considering only the preserved operations. For example, a map between monoids that preserves the monoid operation and not the identity element, is not a monoid homomorphism, but only a semigroup homomorphism.
The notation for the operations does not need to be the same in the source and the target of a homomorphism. For example, the real numbers form a group for addition, and the positive real numbers form a group for multiplication. The exponential function
and is also a group homorphism.
The real numbers are a ring, having both addition and multiplication. The set of all 2 × 2 matrices is also a ring, under matrix addition and matrix multiplication. If we define a function between these rings as follows:
where r is a real number, then f is a homomorphism of rings, since f preserves both addition:
For another example, the nonzero complex numbers form a group under the operation of multiplication, as do the nonzero real numbers. (Zero must be excluded from both groups since it does not have a multiplicative inverse, which is required for elements of a group.) Define a function f from the nonzero complex numbers to the nonzero real numbers by
- f(z) = |z|.
That is, ƒ(z) is the absolute value (or modulus) of the complex number z. Then f is a homomorphism of groups, since it preserves multiplication:
- f(z1 z2) = |z1 z2| = |z1| |z2| = f(z1) f(z2).
Note that ƒ cannot be extended to a homomorphism of rings (from the complex numbers to the real numbers), since it does not preserve addition:
- |z1 + z2| ≠ |z1| + |z2|.
As another example, the picture shows a monoid homomorphism f from the monoid (N, +, 0) to the monoid (N, ×, 1). Due to the different names of corresponding operations, the structure preservation properties satisfied by f amount to f(x + y) = f(x) × f(y) and f(0) = 1.
- An isomorphism is a homomorphism that has an inverse. For structures with an underlying set, this implies that an isomorphism is bijective. For most algebraic structures a bijective homomorphism is an isomorphism. Thus some authors define isomorphisms as bijective homomorphims.:134:28
- A monomorphism is generally injective. For most algebraic structures, an injective homomorphism is a monomorphism. Thus some authors define monomorphisms as injective homomorphims.:134:29 A homomorphism that has a left inverse is a monomorphism, but the converse is not true (for example) for module homomorphisms.
- An epimorphism is often surjective, but this is not true for ring homomorphisms. For most algebraic structures, a surjective homomorphism is an epimorphism. For many algebraic structures, including groups, vector spaces and modules, a homomorphism is an epimorphism if and only if it is surjective. Thus some authors define epimorphisms as surjective homomorphims.:134:43 A homomorphism that has a right inverse is an epimorphism, but the converse is not true, for example for module homomorphisms.
- An endomorphism is a homomorphism from a structure to itself.:135
- An automorphism is an endomorphism which is also an isomorphism, i.e., an isomorphism from a structure to itself.:135
If there is an isomorphism between two structures, they are completely indistinguishable as far as the structure in question is concerned; in this case, they are said to be isomorphic.
The inclusion of Z in Q is a ring homomorphism, which is not surjective. This is an example of a ring epimorphism, which is not surjective. This is also an example of a ring homomorphism which is both a monomorphism and an epimorphism, but not an isomorphism.
The general definitions of isomorphism, monomorphisms and epimorphisms belongs to category theory, and are recalled here.
A morphism f : A → B is called:
- a monomorphism if f ∘ g1 = f ∘ g2 implies g1 = g2 for all morphisms g1, g2: X → A, where "∘" denotes (homo)morphism composition (a sufficient condition for this is f having a left inverse).
- an epimorphism if g1 ∘ f = g2 ∘ f implies g1 = g2 for all morphisms g1, g2: B → X (a sufficient condition for this is f having a right inverse).
- an isomorphism if there exists a morphism g: B → A such that f ∘ g = 1B and g ∘ f = 1A, where "1X" denotes the identity morphism on the object X.
Any homomorphism f : X → Y defines an equivalence relation ~ on X by a ~ b if and only if 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, in which case 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).
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(FA(a1,…,an)) = FB(h(a1),…,h(an)) for each n-ary function symbol F in L,
- RA(a1,…,an) implies RB(h(a1),…,h(an)) for each n-ary relation symbol R in L.
Formal language theory
Homomorphisms are also used in the study of formal languages (although within this context, often they are briefly referred to as morphisms). Given alphabets Σ1 and Σ2, a function h : Σ1∗ → Σ2∗ such that h(uv) = h(u) h(v) for all u and v in Σ1∗ is called a homomorphism (or simply morphism) on Σ1∗.[note 2] Let e denote the empty word. If h is a homomorphism on Σ1∗ and h(x) ≠ e for all x ≠ e in Σ1∗, then h is called an e-free homomorphism.
This type of homomorphism can be thought of as (and is equivalent to) a monoid homomorphism where Σ∗ the set of all words over a finite alphabet Σ is a monoid (in fact it is the free monoid on Σ) with operation concatenation and the empty word as the identity.
- Continuous function
- Homomorphic encryption
- Homomorphic secret sharing – a simplistic decentralized voting protocol
- Birkhoff, Garrett (1967) , Lattice theory, American Mathematical Society Colloquium Publications, 25 (3rd ed.), Providence, R.I.: American Mathematical Society, ISBN 978-0-8218-1025-5, MR 598630
- Mac Lane, Saunders (1971). Categories for the Working Mathematician. Graduate Texts in Mathematics. 5. Springer-Verlag. Exercise 4 in section I.5. ISBN 0-387-90036-5. Zbl 0232.18001.
- Dăscălescu, Sorin; Năstăsescu, Constantin; Raianu, Şerban (2001). Hopf Algebra: An Introduction. Pure and Applied Mathematics. 235. New York, NY: Marcel Dekker. p. 363. ISBN 0824704819. Zbl 0962.16026.
- Section 17.4, in Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7
- Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.
- T. Harju, J. Karhumӓki, Morphisms in Handbook of Formal Languages, Volume I, edited by G. Rozenberg, A. Salomaa, Springer, 1997, ISBN 3-540-61486-9.