Total relation: Difference between revisions

Content deleted Content added

Inline

Revision as of 10:15, 17 May 2022

In mathematics, a binary relation R ⊆ A×B is total (or left total) if the source set A equals the domain {x : there is a y with xRy }. Conversely, R is called right total if B equals the range {y : there is an x with xRy }.

When f: A → B is a function, the domain of f is all of A, 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 A, 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."^[1]

Algebraic characterization

Total relations can be characterized algebraically by equalities and inequalities involving compositions of relations. To this end, let $X$ be a set, let $Y\neq \emptyset ,$ and let $R\subseteq X\times Y.$ For any two sets $A,B,$ let $L_{A,B}=A\times B$ be the universal relation between $A$ and $B,$ and let $I_{A}=\{(a,a):a\in A\}$ be the identity relation on $A.$ We use the notation $R^{\top }$ for the converse relation of $R.$

$R$ is total iff for any set $W$ and any $S\subseteq W\times X,$ $S\neq \emptyset$ implies $SR\neq \emptyset .$ ^[2]^: 54
$R$ is total iff $I_{X}\subseteq RR^{\top }.$ ^: 54
If $R$ is total, then $L_{X,Y}=RL_{Y,Y}.$ The converse is true if $Y\neq \emptyset .$
If $R$ is total, then ${\overline {RL_{Y,Y}}}=\emptyset .$ The converse is true if $Y\neq \emptyset .$ ^{[note 1]}^[2]^: 63
If $R$ is total, then ${\overline {R}}\subseteq R{\overline {I_{Y}}}.$ The converse is true if $Y\neq \emptyset .$ ^[2]^[3]
More generally, if $R$ is total, then for any set $Z$ and any $S\subseteq Y\times Z,$ ${\overline {RS}}\subseteq R{\overline {S}}.$ The converse is true if $Y\neq \emptyset .$ ^{[note 2]}^[2]^: 57

Notes

^ Observe ${\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},$ and apply the previous bullet.
^ Take $Z=Y,S=I_{Y}$ and appeal to the previous bullet.

References

^ Functions from Carnegie Mellon University
^ ^a ^b ^c ^d Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8.
^ Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.

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] Relations and Graphs, p. 54, at Google Books
Gunther Schmidt (2011) Relational Mathematics, p. 57, at Google Books

[3] Observe ${\overline {RL_{Y,Y}}}=\emptyset \Leftrightarrow RL_{Y,Y}=L_{X,Y},$ and apply the previous bullet.

[5] Take $Z=Y,S=I_{Y}$ and appeal to the previous bullet.

[1] Functions from Carnegie Mellon University

[R&G-2] Schmidt, Gunther; Ströhlein, Thomas (6 December 2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8.

[GS11-4] Gunther Schmidt (2011). Relational Mathematics. Cambridge University Press. doi:10.1017/CBO9780511778810. ISBN 9780511778810. Definition 5.8, page 57.

[1]

[2]

[note 1]

[3]

[note 2]

@@ Line 9: / Line 9: @@
 ==Algebraic characterization==
-Total relations can be characterized algebraically by equalities and inequalities involving [[composition of relations]]. To this end, let <math>X</math> be a set, let <math>Y\ne\emptyset,</math> 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 function|identity relation]] on <math>A.</math> We use the notation <math>R^\top</math> for the [[converse relation]] of <math>R.</math>
+Total relations can be characterized algebraically by equalities and inequalities involving [[composition of relations|compositions of relations]]. To this end, let <math>X</math> be a set, let <math>Y\ne\emptyset,</math> 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 function|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}}