Homomorphisms as formal concepts
by
Reinhard Pöschel
TU Dresden, Institut f. Algebra, 01062 Dresden, GERMANY
Coauthors: Bernhard Ganter (TU Dresden), Martin Rößiger (TU Dresden)

We present a general unified setting in which algebras, coalgebras and relational systems with base set A can be described by a relation \alpha subset or equal F(A)×G(A) (in case of algebras and coalgebras by a mapping \alpha: F(A) --> G(B)) for suitable functors F and G from Set to Set. Here we restrict to so-called data functors. Homomorphisms j: (A, \alpha) --> (B, \beta) are mappings j: A --> B which are compatible with \alpha and \beta, i.e. satisfy \alpha o G(j)^· subset or equal F(j)^· o \beta. (Here \psi^· denotes the graph of a function \psi.) For structures (A, \alpha) and (B, \beta) there can be associated a formal context K_{A --> B}=(F(A×B), G(A×B), I).

Theorem. A mapping j: A --> B is a homomorphism if and only if (F(j^·), G(j^·)) is a formal concept in the concept lattice of K_{A --> B} .

The theorem enables us, for example, to use algorithms from formal concept analysis for computing all homomorphims.

Date received: June 17, 1999