Containment for \(c, s, t\) operators on a binary relation. (English) Zbl 1082.08001

Farmer, Frank D.

Algebra Univers. 51, No. 2-3, 153-175 (2004).

Summary: The operators \(c\), \(s\) and \(t\) are complement, symmetric and transitive closure of a binary relation. If \(u\) and \(v\) denote finite sequences of these operators then we define \(u \preccurlyeq v\) iff, for every binary relation \(R\), \(uR \subseteq vR \). We find the distinct representative and containment between these sequences. The asymmetric operator is not one of these. There are 54 representatives for binary relations, 20 for transitive relations, and 10 for symmetric relations. There are 26 component types of a binary relation, 10 for transitive relations, and 6 for symmetric relations. There are 16 connected types of a binary relation, 8 for transitive relations, and 4 for symmetric relations. We study well-founded relations. Total relations may not be contractible but well-founded ones are. The complement of (a Hasse diagram of) a non-empty partial order of arbitrary cardinality is contractible. Ordered sets are naturally homotopy-equivalent to partially ordered sets. There are 10 relations which can have arbitrary polyhedral homotopy type and 42 are either contractible or the homotopy type of a wedge of \(n\)-spheres. The homotopy type of two relations is not determined.

MSC:

08A02	Relational systems, laws of composition
03E20	Other classical set theory (including functions, relations, and set algebra)
06A06	Partial orders, general
55P10	Homotopy equivalences in algebraic topology

Keywords:

symmetric closure; complement; transitive closure; binary relation; well-founded relations; Hasse diagram; partial order; homotopy type