operations on relations


Recall that an n-ary relationMathworldPlanetmathPlanetmath (n>0) is a subset of a productMathworldPlanetmathPlanetmath of some n sets. In this definition, any n-ary relation for which n>1 is automatically an (n-1)-ary relation, and consequently a binary relation. On the other hand, a unary, or 1-ary relation, being the subset B of some set A, can be viewed as a binary relation (either realized as B×B or ΔB:={(b,b)bB}) on A. Hence, we shall concentrate our discussion on the most important kind of relations, the binary relations, in this entry.

Compositions, Inverses, and Complements

Let ρA×B and σB×C be two binary relations. We define the compositionMathworldPlanetmathPlanetmath of ρ and σ, the inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath (or converseMathworldPlanetmath) and the complementMathworldPlanetmathPlanetmath of ρ by

  • ρσ:={(a,c)(a,b)ρ and (b,c)σ for some bB},

  • ρ-1:={(b,a)(a,b)ρ}, and

  • ρ:={(a,b)(a,b)ρ}.

ρσ,ρ-1 and ρ are binary relations of A×C,B×A and A×B respectively.

Properties. Suppose ρ,σ,τ are binary relations of A×B,B×C,C×D respectively.

  1. 1.

    Associativity of relational compositionsPlanetmathPlanetmath: (ρσ)τ=ρ(στ).

  2. 2.

    (ρσ)-1=σ-1ρ-1.

  3. 3.

    For the rest of the remarks, we assume A=B. Define the power of ρ recursively by ρ1=ρ, and ρn+1=ρρn. By 1 above, ρn+m=ρnρm for m,n.

  4. 4.

    ρ-n may be also be defined, in terms of ρ-1 for n>0.

  5. 5.

    However, ρn+mρnρm for all integers, since ρ-1ρρρ-1 in general.

  6. 6.

    Nevertheless, we may define Δ:={(a,a)aA}. This is called the identityPlanetmathPlanetmath or diagonal relation on A. It has the property that Δρ=ρΔ=ρ. For this, we may define, for every relation ρ on A, ρ0:=Δ.

  7. 7.

    Let be the set of all binary relations on a set A. Then (,) is a monoid (http://planetmath.org/Monoid) with Δ as the identity elementMathworldPlanetmath.

Let ρ be a binary relation on a set A, below are some special relations definable from ρ:

  • ρ is reflexiveMathworldPlanetmathPlanetmath if Δρ;

  • ρ is symmetricMathworldPlanetmathPlanetmath if ρ=ρ-1;

  • ρ is anti-symmetric if ρρ-1Δ;

  • ρ is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath if ρρρ;

  • ρ is a pre-order if it is reflexive and transitive

  • ρ is a partial orderMathworldPlanetmath if it is a pre-order and is anti-symmetric

  • ρ is an equivalence if it is a pre-order and is symmetric

Of these, only reflexivity is preserved by and both symmetryMathworldPlanetmath and anti-symmetry are preserved by the inverse operationMathworldPlanetmath.

Other Operations

Some operations on binary relations yield unary relations. The most common ones are the following:

Given a binary relation ρA×B, and an elements aA and bB, define

ρ(a,):={y(a,y)ρ} and ρ(,b):={x(x,b)ρ}.

ρ(a,)B is called the sectionMathworldPlanetmath of ρ in B based at a, and ρ(,b)A is the section of ρ in A (based) at b. When the base points are not mentioned, we simply say a section of ρ in A or B, or an A-section or a B-section of ρ.

Finally, we define the domain and range of a binary relation ρA×B, to be

  • dom(ρ):={a(a,b)ρ for some bB}, and

  • ran(ρ):={b(a,b)ρ for some aA}.

respectively. When ρ is a function, the domain and range of ρ coincide with the domain of range of ρ as a function.

Remarks. Given a binary relation ρA×B.

  1. 1.

    ρ(a,), realized as a binary relation {a}×ρ(a,) can be viewed as the composition of Δaρ, where Δa={(a,a)}. Similarly, ρΔb=ρ(,b)×{b}.

  2. 2.

    dom(ρ) is the disjoint unionMathworldPlanetmath of A-sections of ρ and ran(ρ) is the disjoint union of B-sections of ρ.

  3. 3.

    dom(ρ-1)=ran(ρ) and ran(ρ-1)=dom(ρ).

  4. 4.

    ρρ-1=dom(ρ)×dom(ρ) and ρ-1ρ=ran(ρ)×ran(ρ).

  5. 5.

    If A=B, then dom(ρ)×A=ρA2 and ran(ρ)=A2ρ.

  6. 6.

    The composition of binary relations can be generalized: let R be a subset of A1××An and S be a subset of B1××Bm, where m,n are positive integers. Further, we assume that An=B1=C. Define RS, as a subset of A1××An-1×B2×Bm, to be the set

    {(a1,,an-1,b2,,bm)cC with (a1,,an-1,c)R and (c,b2,,bm)S}.

    If m=n=2, then we have the familiar composition of binary relations. If m=1 and n=2, then RS={a(a,c)R and cS}. The case where m=2 and n=1 is similarMathworldPlanetmathPlanetmath. If m=n=1, then RS={ true } if RS. Otherwise, it is set to { false }.

Title operations on relations
Canonical name OperationsOnRelations
Date of creation 2013-03-22 16:26:40
Last modified on 2013-03-22 16:26:40
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 14
Author CWoo (3771)
Entry type Definition
Classification msc 08A02
Classification msc 03E20
Synonym inverse relation
Synonym relation composition
Synonym converse of a relation
Synonym diagonal relation
Related topic GeneralAssociativity
Related topic RelationAlgebra
Defines power of a relation
Defines relational composition
Defines inverse of a relation
Defines section
Defines domain
Defines range
Defines identity relation