Editing Total relation

{{Short description|Type of logical relation}}
{{for|relations ''R'' where ''<nowiki>x=y</nowiki>'' or ''xRy'' or ''yRx'' for all ''x'' and ''y''|connected relation}}

In [[mathematics]], a [[binary relation]] ''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is '''total''' (or '''left total''') if the source set ''X'' equals the domain {''x'' : there is a ''y'' with ''xRy'' }. Conversely, ''R'' is called '''right total''' if ''Y'' equals the range {''y'' : there is an ''x'' with ''xRy'' }.

When ''f'': ''X'' → ''Y'' is a [[function (mathematics)|function]], the domain of ''f'' is all of ''X'', hence ''f'' is a total relation. On the other hand, if ''f'' is a [[partial function]], then the domain may be a proper subset of ''X'', in which case ''f'' is not a total relation.

"A binary relation is said to be total with respect  to a universe of discourse just in case everything in that universe of discourse stands in that relation to something else."<ref>[http://caae.phil.cmu.edu/projects/logicandproofs/alpha/htmltest/m15_functions/chapter15.html Functions] from [[Carnegie Mellon University]]</ref>

==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}}

==See also==
* [[Serial relation]] &mdash; a total homogeneous relation

==Notes==
{{reflist|group=note}}

==References==
{{reflist}}

* [[Gunther Schmidt]] & Michael Winter (2018) ''Relational Topology''
* C. Brink, W. Kahl, and G. Schmidt (1997) ''Relational Methods in Computer Science'', Advances in Computer Science, page 5, {{ISBN|3-211-82971-7}}
* Gunther Schmidt & Thomas Strohlein (2012)[1987] {{Google books|ZgarCAAAQBAJ|Relations and Graphs|page=54}}
* Gunther Schmidt (2011) {{Google books|E4REBTs5WsC|Relational Mathematics|page=57}}

{{Order theory}}

[[Category:Properties of binary relations]]