A relation is called a binary relation on sets and .

The domain of a relation, written as ), is a set of elements in s.t. if , for some . And the codomain is the set of elements such that for some .

A binary relation is a partial function from to if whenever and , we have . And it is a total function if (in other words, every elements in the set is in the domain).

We often denote a binary relation as rather than . For example, we denote strict equivalent as .

Ordered Sets

Some definitions:

  • reflexive: for all in domain
  • symmetric: for all and in domain (the domain and codomain is the same in this case)
  • transitive:
  • antisymmetric:

A reflexive and transitive relation is called a preorder on its domain . Preorders are written with symbols like . And means . A preorder is called a partial order if it is also antisymmetric. And a partial order is a total order if it also has the property that for each and in domain, either or .

A reflexive, transitive, and symmetric relation on a set is called an equivalence of .