Structure Homomorphism

In logic, the term "homomorphism" is used in a manner similar to but a bit different from its usage in abstract algebra. The usage in logic is a special case of a "morphism" from category theory.

Let A=(A,(c^A)_(c in C),(P^A)_(P in P),(f_(f in F)^A), and B=(A,(c^B)_(c in C),(P^B)_(P in P),(f_(f in F)^B) be structures for a common language L, and let h:A->B. Then h is a homomorphism from A to B provided that it satisfies the following:

1. For each constant c in C, h(c^A)=c^B.

2. For each predicate symbol P in P, if the arity of P is n, then

 P^B={h(a_1),...,h(a_n)|(a_1,...,a_n) in P^A}.

3. For each function symbol (or operation) f in F, if the arity of f is n, then for any a_1,...,a_n in A,


For example, let G=(G,E) and H=(H,F) be (directed) graphs (the set G is the set of vertices of G, and H is the set of vertices of H, while E is the relational representation of the edges of the graph G, etc.). A homomorphism from G to H is a function h:G->H such that for any vertices g_1 and g_2 of G, g_1 and g_2 are connected by a directed edge (from g_1 to g_2 if and only if the vertices h(g_1) and h(g_2) are connected by a directed edge from h(g_1) to h(g_2).

Another example is available in the theory of ordered groups. Let G=(G,e^G,*^G,iota^G,<=^G) and H=(G,e^H,*^H,iota^H,<=^H) be ordered groups. (We are using the symbol iota to denote the multiplicative inversion operation. We will drop the superscripts ^G and ^H, and for any x in G (or x in H), we denote iota(x) by x^(-1).) Formal application of our definition of a homomorphism in this setting indicates that h:G->H is a homomorphism if and only if it satisfies the following:

1. h(e)=e.

2. For x,y in G, h(x*y)=h(x)*h(y).

3. For any x in G, h(x^(-1))=(h(x))^(-1).

4. For any x,y in G, x<=y if and only if h(x)=h(y).

(Of course, these conditions can be shown to be redundant. Hence many texts define homomorphisms with requiring the preservation of the group identity (e), and with postulating the preservation of multiplicative inversion.)

The homomorphisms of universal algebra are special cases of structure homomorphisms, and the notion of a structure homomorphism also extends the corresponding morphism notions in categories of ordered sets and various relational/algebraic structures.

See also


This entry contributed by Matt Insall (author's link)

Explore with Wolfram|Alpha


Bell, J. L. and Slomson, A. B. Models and Ultraproducts: an Introduction. Amsterdam, Netherlands: North-Holland, 1971.Enderton, H. B. A Mathematical Introduction to Logic. New York: Academic Press, 1972.Insall, E. "Nonstandard Methods and Finiteness Conditions in Algebra." Ph.D. dissertation. Houston, Texas: University of Houston, 1989.

Referenced on Wolfram|Alpha

Structure Homomorphism

Cite this as:

Insall, Matt. "Structure Homomorphism." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications