A general extension theorem for binary relations (Q1294002): Difference between revisions

First a lot of properties (besides the generally known) for binary relations \(B\) on a set \(X\) are defined: Let \(\Delta\) be the identity relation on \(X\) and \(T_B\) the transitive closure of \(B\), \(B^-:=(X\times X)\setminus B\), \(B^{-1}: =\{(y,x) |(x,y)\in B\}\); \(P_B:= B\setminus B^{-1}\) is called the asymmetric part of \(B\). Then \(B\) is called complete if \(B\cup B^{-1}= X\times X\), asymmetric if \(B\cap B^{-1}= \emptyset\), total if \(\Delta^-\subseteq B\cup B^{-1}\), negatively transitive if \(B=T^-_{B^-}\), acyclic if \(\Delta \cap T_B=\emptyset\), negatively acyclic if \(\Delta \cap T_{B^-}= \emptyset\), \(P\)-acyclic if \(\Delta\cap T_{P_B}= \emptyset\). A relation \(B\) is transitive-consistent if \(P_B \subseteq P_{T_B}\) resp. negatively transitive-consistent if \(P_B\subseteq P_{T^-_{B^-}}\). A relation \(B'\) is a compatible extension of a relation \(B\) if \(B\subseteq B'\) and \(P_B\subseteq P_{B'}\), resp. a compatible intension of \(B\) if \(B'\subseteq B\) and \(P_B \subseteq P_{B'}\). A class \({\mathfrak B}\) of relations is said to be closed upward if for all chains \({\mathfrak C}\) in \({\mathfrak B}\) there holds \(\bigcup\{B|B\in {\mathfrak C}\}\in {\mathfrak B}\), and it is called transitive-closed if for all \(B\in {\mathcal B}\) there holds \(T_B\in {\mathfrak B}\). The class \({\mathfrak B}\) said to be arc-receptive if, for all distinct \(x\) and \(y\) and for all transitive \(B\in {\mathcal B}\), \((y,x)\notin B\) implies \(T_{B\cup\{(x,y)\}} \in{\mathfrak B}\). Then the following general extension theorem is proved: Assume \({\mathfrak B}\) is closed upward and arc-receptive. If \(B\) is transitive-consistent and \(T_B\in {\mathfrak B}\), then \(T_B= \bigcap\{B'\in {\mathfrak B}|B'\) is a total, transitive compatible extension of \(B\}\). As a special case it follows that a complete, negatively transitive relation is the union of all linear orders embedded within it. Remark: On page 4 in the definition of linear order the property ``total'' should be added.