A proposition of the form R(x,y) where x and y are variables expresses a **relation**.
Such statements are often written in the alternative form xRy. A binary relation may also
be regarded as a set of pair sequences, in which case we can write the statement in the form (x,y)∈R.

The set X of all x such that xRy for some y is called the **foredomain** of R,
and the set Y of all y such that xRy for some x is the **postdomain** of R, their union X∪Y is the **domain** of R.
The set X×Y of all ordered pairs (x,y) with x in X and y in Y is the **span** of R. Thus R⊆(X×Y).

For a given pair (a,b) with a in X and b in Y we either have aRb or not aRb, that is the truth values of these statements are either T(aRb)=1 or T(aRb)=0. Thus a relation R can be also represented in truth-table form, where the rows are labelled with the elements of X and the columns with the elements of Y and the table entries are 1 or 0 according as (a,b) are related by R or not.

Simple relations can often helpfully be represented by geometrical network diagrams, in which the elements of X∪Y are denoted by marked and labelled points, and the pair (x,y) in R is denoted by an arrowed line joining point x to point y.

The **negation** of a relation R is the relation ‘notR’,
for which x(notR)y is true if and only if xRy is false in a given context I that contains X∪Y.
The negation of a relation is often shown by the same symbol with a stroke through it. [For example = and ≠]

If xRx is true for all x in a set X then the relation is said to be **reflexive** in X;
if xRx is false for all x in X then R is **irreflexive** in X.
From any relation R we can derive the reflexive relation: ‘either xRy or x=y or both’.
This type of compound relation is often denoted by combining the symbol for R with the equality sign.
For example ‘less than or equal to’ combines < with = to give ≤.
Similarly from any relation R we can derive an irreflexive relation ‘xRy but not x=y’.

The **reversal** of a relation R is the proposition ~R such that y(~R)x if and only if xRy.
Thus ~R is formed from R by reversing the order of all the ordered pairs.
It follows that ~(~R)=R. The reversal of a relation is often denoted by reversing
the symbol for the relation (e.g. < and >, or ≤ and ≥).

It is possible to have ~R = R, in which case the relation is **symmetric**, in other words xRy implies yRx.
The symbol for a symmetric relation is usually chosen to be reversible (e.g. =).
From any relation R we can form its **symmetric completion** R∪(~R), which is the smallest symmetric relation containing R.
On the other hand if R and ~R have no pairs in common, the relation is **asymmetric**, that is aRb implies that b(notR)a.
Any relation can be split into two parts (although either may be null), one of which is symmetric R∩(~R), and the other asymmetric R−(~R).
A relation R is **non-symmetric** if aRb and a≠b implies b(notR)a for all a, b in its domain.
A relation is **antisymmetric** if xRy and yRx together imply x=y in its domain.

If R and S are relations then their ‘product’ R°S is the relation that holds between x and z when xRy and ySz for some y.
We find that ~(R°S) = (~S)°(~R); note the reversal of order.
If xRy and yRz implies xRz the relation R is said to be **transitive**.
This can be expressed by (R°R)⊆R. If R is transitive it follows that (R°n)⊆R for any n,
where R°n denotes R°R°...R°R where there are n occurrences of R.
From any relation we can form its **transitive completion** ∪(R, R°2, R°3, ...)
which is the smallest transitive relation containing R.

A relation that is reflexive, symmetric and transitive is called an **equivalence**.
An equivalence relation has the property of partitioning the entities to which it applies into mutually exclusive sets,
called equivalence **classes** (or *categories*) such that members of the same class are equivalent to each other.
Conversely any such partition determines an equivalence relation. [Equality, coexistence and isomorphism are
examples of equivalence relations. The equivalence classes of equality being the unit sets of individual entities.]

From any relation we can form its **equivalence completion** the transitive completion of its symmetric completion (or vice versa).
This equivalence partitions the domain of R, and therefore R itself, into **components**.
A relation with just one component is said to be **connected**.
An equivalence relation is reflexive for all elements within its domain, since if x is in the domain then xRy or yRx for some y,
so xRy and yRx by symmetry, so xRx by transitivity.
For an equivalence relation to partition a set A it must be reflexive in A or, equivalently,
every element of A must be in the domain of the equivalence relation.

A relation that is non-symmetric and transitive is called an **ordering** (or *partial order* relation).
An ordering that is reflexive is antisymmetric. An ordering that is irreflexive is asymmetric.
If R is a reflexive or irreflexive ordering then so is its converse ~R.

If ≤ denotes a reflexive order defined in a set S, and T is a subset of S,
then an element s of S such that s≤t for all t in T is called a **lower bound**
of T with respect to ≤ in S. Similarly if t≤s' for all t in T then s' is called an **upper bound**.

A **least** element u in a set T has the property that u≤t for all t in T, i.e. it is a lower bound contained in T.
Similarly a **greatest** element v has the property t≤v for all t, i.e. it is an upperbound contained in T.
If either of these elements exist they are unique, by antisymmetry. Since, if u and u' are two least elements then u≤u' and u'≤u so u = u',
and similarly for the greatest element.

An ordering R is a **simple** ordering if for any a and b, a≠b, we always have either aRb or bRa.
Every [finite] set in a simple ordering has a least and a greatest element.
Any two simple reflexive or irreflexive orderings of n elements are isomorphic.
In particular, if a *greatest lower bound* or a *least upper bound* exists it is unique.
A relation that has a least upper bound and a greatest lower bound for any subset we call a **latticial** ordering.