Total Relation

Definition

Let $R:X\to Y\to \mathrm{Prop}$ be a relation.

$R$ is left-total (or total in $X$) iff every element of $X$ is related to at least one element of $Y$: $\forall x\in X.\exists y\in Y.Rxy.$

$R$ is right-total (or total in $Y$) iff every element of $Y$ is related by at least one element of $X$: $\forall y\in Y.\exists x\in X.Rxy.$

Relationship to Functions

A relation $R:X\to Y\to \mathrm{Prop}$ is a function iff it is left-total and right-unique (i.e., every $x\in X$ is related to exactly one $y\in Y$).

Right-totality of a function $f:X\to Y$ is precisely surjectivity.

Totality on a Single Set

When $R:A\to A\to \mathrm{Prop}$ is a homogeneous relation, $R$ is total (or connected) iff any two elements are comparable: $\forall x,y\in A.Rxy\vee Ryx.$ This is the additional condition that turns a partial order into a total order.

Related Concepts

• Predicate
• Unique (Relation)
• Surjection
• Partial Order
• Total Ordering