In mathematics, a

binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...

''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is total (or left total) if the source set ''X'' equals the domain . Conversely, ''R'' is called right total if ''Y'' equals the range . When ''f'': ''X'' → ''Y'' is a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...

, the domain of ''f'' is all of ''X'', hence ''f'' is a total relation. On the other hand, if ''f'' is a

partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is ...

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

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technolog ...

Algebraic 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\times B

be the universal relation between

A

and

B,

and let

I_A=\

be the identity relation on

A.

We use the notation

R^\top

for the

converse relation In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent&n ...

R.

R

is total iff for any set

W

and any

S\subseteq W\times X,

S\ne\emptyset

implies

SR\ne\emptyset.

R

is total iff

I_X\subseteq RR^\top.

* If

R

is total, then

L_=RL_.

The converse is true if

Y\ne\emptyset.

Y=\emptyset\ne X,

then

R

will be not total. * If

R

is total, then

\overline=\emptyset.

The converse is true if

Y\ne\emptyset.

Observe

\overline=\emptyset\Leftrightarrow RL_=L_,

and apply the previous bullet. * If

R

is total, then

\overline R\subseteq R\overline.

The converse is true if

Y\ne\emptyset.

Definition 5.8, page 57. * More generally, if

R

is total, then for any set

Z

and any

S\subseteq Y\times Z,

\overline\subseteq R\overline S.

The converse is true if

Y\ne\emptyset.

Take

Z=Y,S=I_Y

and appeal to the previous bullet.

Notes

References

* 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, * Gunther Schmidt & Thomas Strohlein (2012)

987 Year 987 ( CMLXXXVII) was a common year starting on Saturday (link will display the full calendar) of the Julian calendar. Events By place Byzantine Empire * February 7 – Bardas Phokas (the Younger) and Bardas Skleros, two memb ...

* Gunther Schmidt (2011) {{Order theory Binary relations