Editing Total relation (section)

==Algebraic characterization==
Total relations can be characterized algebraically by equalities and inequalities involving [[composition of relations|compositions of relations]]. To this end, let <math>X,Y</math> be two sets, and let <math>R\subseteq X\times Y.</math> For any two sets <math>A,B,</math> let <math>L_{A,B}=A\times B</math> be the [[universal relation]] between <math>A</math> and <math>B,</math> and let <math>I_A=\{(a,a):a\in A\}</math> be the [[identity relation]] on <math>A.</math> We use the notation <math>R^\top</math> for the [[converse relation]] of <math>R.</math>

* <math>R</math> is total iff for any set <math>W</math> and any <math>S\subseteq W\times X,</math> <math>S\ne\emptyset</math> implies <math>SR\ne\emptyset.</math><ref name=R&G>{{cite book|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url={{google books |plainurl=y |id=ZgarCAAAQBAJ|paged=54}}|date=6 December 2012|publisher=[[Springer Science & Business Media]]|isbn=978-3-642-77968-8|author-link1=Gunther Schmidt}}</ref>{{rp|54}}
* <math>R</math> is total iff <math>I_X\subseteq RR^\top.</math><ref name=R&G/>{{rp|54}}
* If <math>R</math> is total, then <math>L_{X,Y}=RL_{Y,Y}.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>If <math>Y=\emptyset\ne X,</math> then <math>R</math> will be not total.</ref>
* If <math>R</math> is total, then <math>\overline{RL_{Y,Y}}=\emptyset.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>Observe <math>\overline{RL_{Y,Y}}=\emptyset\Leftrightarrow RL_{Y,Y}=L_{X,Y},</math> and apply the previous bullet.</ref><ref name=R&G/>{{rp|63}}
* If <math>R</math> is total, then <math>\overline R\subseteq R\overline{I_Y}.</math> The converse is true if <math>Y\ne\emptyset.</math><ref name=R&G/>{{rp|54}}<ref name=GS11>{{cite book | doi=10.1017/CBO9780511778810 | isbn=9780511778810 | author=Gunther Schmidt | title=Relational Mathematics  | publisher=[[Cambridge University Press]] | year=2011 }} Definition 5.8, page 57.</ref>
* More generally, if <math>R</math> is total, then for any set <math>Z</math> and any <math>S\subseteq Y\times Z,</math> <math>\overline{RS}\subseteq R\overline S.</math> The converse is true if <math>Y\ne\emptyset.</math><ref group=note>Take <math>Z=Y,S=I_Y</math> and appeal to the previous bullet.</ref><ref name=R&G/>{{rp|57}}