Homomorphism: Difference between revisions
FeatherPluma (talk | contribs) |
FeatherPluma (talk | contribs) |
||
Line 77: | Line 77: | ||
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 group homomorphism, (a single binary operation, an inverse operation, being a unary operation, and identity, being a nullary operation) but not a ring isomorphism (two binary operations, the additive inverse and the identity elements), because it may fail to preserve the additional monoid structure required by the definition of a ring. |
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 group homomorphism, (a single binary operation, an inverse operation, being a unary operation, and identity, being a nullary operation) but not a ring isomorphism (two binary operations, the additive inverse and the identity elements), because it may fail to preserve the additional monoid structure required by the definition of a ring. |
||
== Types == |
|||
== Specific kinds of homomorphisms == |
|||
[[Image:Morphisms3.svg|250px|thumb|Relationships between different kinds of homomorphisms. <br> ''Hom'' = set of Homomorphisms,<br> ''Mon'' = set of Monomorphisms, <br>''Epi'' = set of Epimorphisms,<br> ''Iso'' = set of Isomorphisms, <br>''End'' = set of Endomorphism,<br> ''Aut'' = set of Automorphisms.<br> Notice that: {{nowrap|1=''Mon'' ∩ ''Epi'' = ''Iso''}}, {{nowrap|1=''Iso'' ∩ ''End'' = ''Aut''}}. <br>The sets {{nowrap|(''Mon'' ∩ ''End'') \ ''Aut''}} and {{nowrap|(''Epi'' ∩ ''End'') \ ''Aut''}} contain only homomorphisms from some infinite structures to themselves.]] |
[[Image:Morphisms3.svg|250px|thumb|Relationships between different kinds of homomorphisms. <br> ''Hom'' = set of Homomorphisms,<br> ''Mon'' = set of Monomorphisms, <br>''Epi'' = set of Epimorphisms,<br> ''Iso'' = set of Isomorphisms, <br>''End'' = set of Endomorphism,<br> ''Aut'' = set of Automorphisms.<br> Notice that: {{nowrap|1=''Mon'' ∩ ''Epi'' = ''Iso''}}, {{nowrap|1=''Iso'' ∩ ''End'' = ''Aut''}}. <br>The sets {{nowrap|(''Mon'' ∩ ''End'') \ ''Aut''}} and {{nowrap|(''Epi'' ∩ ''End'') \ ''Aut''}} contain only homomorphisms from some infinite structures to themselves.]] |
||
{| style="float:right; border: 1px solid darkgray;" |
{| style="float:right; border: 1px solid darkgray;" |
Revision as of 02:48, 27 September 2015
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 ancient Greek language: ὁμός (homos) meaning "same" and μορφή (morphe) meaning "form" or "shape". Isomorphisms, automorphisms, and endomorphisms are special types of homomorphisms.
Definition and illustration
Definition
A homomorphism is a map that preserves selected structure between two algebraic structures, with the structure to be preserved being given by the naming of the homomorphism.
Particular definitions of homomorphism include the following:
- A semigroup homomorphism is a map that preserves an associative binary operation.
- A monoid homomorphism is a semigroup homomorphism that maps the identity element to the identity of the codomain.
- A group homomorphism is a homomorphism that preserves the group structure. It may equivalently be defined as a semigroup homomorphism between groups.
- A ring homomorphism is a homomorphism that preserves the ring structure. Whether the multiplicative identity is to be preserved depends upon the definition of ring in use.
- A linear map is a homomorphism that preserves the vector space structure, namely the abelian group structure and scalar multiplication. The scalar type must further be specified to specify the homomorphism, e.g. every R-linear map is a Z-linear map, but not vice versa.
- A module homomorphism is a map that preserves module structures.
- An algebra homomorphism is a homomorphism that preserves the algebra structure.
- A functor is a homomorphism between two categories.
Not all structure that an object possesses need be preserved by a homomorphism. For example, one may have a semigroup homomorphism between two monoids, and this will not be a monoid homomorphism if it does not map the identity of the domain to that of the codomain.
For example, a group is an algebraic object consisting of a set together with a single binary operation, satisfying certain axioms. If (G, ∗) and (H, ∗′) are groups, a homomorphism from (G, ∗) to (H, ∗′) is a function f : (G, ∗) → (H, ∗′) such that f(g1 ∗ g2) = f(g1) ∗′ f(g2) for all elements g1, g2 ∈ G. Since inverses exist in G and H, one can show that the identity of G maps to the identity of H and that inverses are preserved.
The algebraic structure to be preserved may include more than one operation, and a homomorphism is required to preserve each operation. For example, a ring has both addition and multiplication, and a homomorphism from the ring (R, +, ∗, 0, 1) to the ring (R′, +′, ∗′, 0′, 1′) is a function such that f(r + s) = f(r) +′ f(s), f(r ∗ s) = f(r) ∗′ f(s) and f(1) = 1′ for any elements r and s of the domain ring. If rings are not required to be unital, the last condition is omitted. In addition, if defining structures of (e.g. 0 and additive inverses in the case of a ring) were not necessarily preserved by the above, preserving these would be added requirements.
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 f : A → B is a function between two algebraic structures of the same type such that
- f(μA(a1, ..., an)) = μB(f(a1), ..., f(an))
for each n-ary operation μ and for all elements a1, ..., an ∈ A.
Basic examples
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Exponentiation_as_monoid_homomorphism_svg.svg/215px-Exponentiation_as_monoid_homomorphism_svg.svg.png)
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:
and multiplication:
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.
Informal discussion
Because abstract algebra studies sets endowed with operations that generate interesting structure or properties on the set, functions which preserve the operations are especially important. 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 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) = ex satisfies this condition: 2 + 3 = 5 translates into e2 · e3 = e5.
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 group homomorphism, (a single binary operation, an inverse operation, being a unary operation, and identity, being a nullary operation) but not a ring isomorphism (two binary operations, the additive inverse and the identity elements), because it may fail to preserve the additional monoid structure required by the definition of a ring.
Types
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Morphisms3.svg/250px-Morphisms3.svg.png)
Hom = set of Homomorphisms,
Mon = set of Monomorphisms,
Epi = set of Epimorphisms,
Iso = set of Isomorphisms,
End = set of Endomorphism,
Aut = set of Automorphisms.
Notice that: Mon ∩ Epi = Iso, Iso ∩ End = Aut.
The sets (Mon ∩ End) \ Aut and (Epi ∩ End) \ Aut contain only homomorphisms from some infinite structures to themselves.
| ||||||||||||||||||||
| ||||||||||||||||||||
|
In abstract algebra, several specific kinds of homomorphisms are defined as follows:
- An isomorphism is a bijective homomorphism.
- An epimorphism (sometimes called a cover) is a surjective homomorphism. Equivalently, [note 1] f: A → B is an epimorphism if it has a right inverse g: B → A, i.e. if f(g(b)) = b for all b ∈ B.
- A monomorphism (sometimes called an embedding or extension) is an injective homomorphism. Equivalently, [note 1] f: A → B is a monomorphism if it has a left inverse g: B → A, i.e. if g(f(a)) = a for all a ∈ A.
- An endomorphism is a homomorphism from an algebraic structure to itself.
- An automorphism is an endomorphism which is also an isomorphism, i.e., an isomorphism from an algebraic structure to itself.[1]
- The trivial homomorphism between unital magmas is the constant map onto the identity element of the codomain.[2]
These descriptions may be used in order to derive several properties. For instance, since a function is bijective if and only if it is both injective and surjective, in abstract algebra a homomorphism is an isomorphism if and only if it is both a monomorphism and an epimorphism. An isomorphism always has an inverse f−1, which is a homomorphism, too (cf. Proof 1). If there is an isomorphism between two algebraic structures, they are completely indistinguishable as far as the structure in question is concerned; in this case, they are said to be isomorphic.
Category theory
Since homomorphisms are morphisms in an appropriate category, we may consider the analogous specific kinds of morphisms defined in any category. However, the definitions in category theory are somewhat different. For endomorphisms and automorphisms, the descriptions above coincide with the category theoretic definitions; the first three descriptions do not. In category theory, a morphism f : A → B is called:
- monomorphism if f ∘ g1 = f ∘ g2 implies g1 = g2 for all morphisms g1, g2: X → A, where "∘" denotes function composition corresponding to e.g. (f ∘ g1)(x) = f(g1(x)) in abstract algebra. (A sufficient condition for this is f having a left inverse, cf. Proof 2.)
- 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, cf. Proof 3.)
- 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.[note 2]
For instance, the inclusion ring homomorphism of Z as a (unitary) subring of Q is not surjective (i.e. not epi in the set-theoretic sense), but an epimorphic in the sense of category theory.[3][4] This inclusion thus also is an example of a ring homomorphism which is (in the sense of category theory) both mono and epi, but not iso.
Kernel
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).
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(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.
In the special case with just one binary relation, we obtain the notion of a graph homomorphism. For a detailed discussion of relational homomorphisms and isomorphisms see.[5]
Formal language theory
Homomorphisms are also used in the study of formal languages[6] (although within this context, often they are briefly referred to as morphisms[7]). 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 3] 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.
See also
- continuous function
- diffeomorphism
- homomorphic encryption
- homomorphic secret sharing – a simplistic decentralized voting protocol
- morphism
Notes
- ^ a b tacitly assuming the axiom of choice and a nonconstructive setting
- ^ The notion of "object" and "morphism" in category theory generalizes the notion of "algebraic structure" and "homomorphism", respectively.
- ^ In homomorphisms on formal languages, the ∗ operation is the Kleene star operation. The ⋅ and ∘ are both concatenation, commonly denoted by juxtaposition.
References
- ^ Birkhoff, Garrett (1967) [1940], Lattice theory, American Mathematical Society Colloquium Publications, vol. 25 (3rd ed.), Providence, R.I.: American Mathematical Society, ISBN 978-0-8218-1025-5, MR 0598630 Here: Sect.VI.3, p.134
- ^ Bourbaki, Algebra, ch. I §2.1, p. 13
- ^ Mac Lane, Saunders (1971). Categories for the Working Mathematician. Graduate Texts in Mathematics. Vol. 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. Vol. 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.
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.