A general extension theorem for binary relations (Q1294002): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jeth.1998.2504 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1972253237 / rank | |||
Normal rank |
Revision as of 21:52, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A general extension theorem for binary relations |
scientific article |
Statements
A general extension theorem for binary relations (English)
0 references
19 November 2000
0 references
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.
0 references
binary relations
0 references
transitive closure
0 references
asymmetric part
0 references
transitive-consistent
0 references
compatible extension
0 references
compatible intension
0 references
closed upward
0 references
arc-receptive
0 references