MVLSC HomeIssue Contents

Semirigid Equivalence Relations on a Finite Set
Masahiro Miyakawa, Maurice Pouzet, Ivo G. Rosenberg and Hisayuki Tatsumi

A system R of equivalence relations on a set A (with at least 3 elements) is semirigid if only the trivial operations (the projections and constant functions) preserve all members of R. To a system R of equivalence relations we associate a graph GR. We observe that if R is semirigid then the graph GR is 2-connected. We show that the converse holds if all the members of R are atoms of the lattice E of equivalence relations on A. We present a notion of graphical composition of semirigid systems and show that it preserves semirigidity.

Keywords: Clones, semirigidity, equivalence relations, decompositions of relational structures, connectedness, biconnectedness.

2000 Mathematics Subject Classification. 94D05, 03B50.

Full Text (IP)