Encyclopedia

Total relation

Type of logical relation

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated February 7, 2024

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, 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."

01Algebraic characterization

Total relations can be characterized algebraically by equalities and inequalities involving compositions of relations. To this end, let $X,Y$ be two sets, 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 .$
$R$ is total iff $I_{X}\subseteq RR^{\top }.$
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 .$
If $R$ is total, then ${\overline {R}}\subseteq R{\overline {I_{Y}}}.$ The converse is true if $Y\neq \emptyset .$
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 .$

Watch videos about Total relationExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Total relation”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Total relation

01Algebraic characterization

Sources and credits

Related topics

Serial relation