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.