A general extension theorem for binary relations
type: Item
instance of: scholarly article
title: A general extension theorem for binary relations
zbMATH Open document ID: 0948.03046
author: John Duggan
published in: Journal of Economic Theory
publication date: 2000-11-19T00:00:00Z
review text: 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 t…
Mathematics Subject Classification ID: 03E20
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 1310715
zbMATH Keywords: binary relations
zbMATH Keywords: transitive closure
zbMATH Keywords: asymmetric part
zbMATH Keywords: transitive-consistent
zbMATH Keywords: compatible extension
zbMATH Keywords: compatible intension
zbMATH Keywords: closed upward
zbMATH Keywords: arc-receptive
reviewed by: Egbert Harzheim
MaRDI profile type: Publication
full work available at URL: jeth.1998.2504
OpenAlex ID: W1972253237
cites work: A quasiordering is the intersection of orderings
cites work: Q5668657
cites work: Choice structures and preference relations
cites work: Q3291034
cites work: Revealed Preference Theory
cites work: Q4403954
cites work: A generalization of Moulin's Pareto extension theorem
DOI: 10.1006/JETH.1998.2504
Recommended article: A generalization of Arrow's lemma on extending a binary relation
Recommended article: Q4861831
Recommended article: Extension of the Zorn lemma to general nontransitive binary relations
Recommended article: Q3752445
Recommended article: Upper semicontinuous extensions of binary relations
Recommended article: Q5553264
Recommended article: Q4011720
Recommended article: On the typification of binary relations
Recommended article: Q5173679
description: scientific article; zbMATH DE number 1310715