operations on relations (original) (raw)

Recall that an n-ary relation (n>0) is a subset of a product 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)∣b∈B}) 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 composition of ρ and σ, the inverse (or converse) and the complement of ρ by

• •
  ρ∘σ:={(a,c)∣(a,b)∈ρ⁢ and ⁢(b,c)∈σ⁢ for some ⁢b∈B},
• •
  ρ-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.

2. 1. (ρ∘σ)-1=σ-1∘ρ-1.
3. 1. 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. 1. ρ-n may be also be defined, in terms of ρ-1 for n>0.
5. 1. However, ρn+m≠ρn∘ρm for all integers, since ρ-1∘ρ≠ρ∘ρ-1 in general.
6. 1. Nevertheless, we may define Δ:={(a,a)∣a∈A}. This is called the identity or diagonal relation on A. It has the property that Δ∘ρ=ρ∘Δ=ρ. For this, we may define, for every relation ρ on A, ρ0:=Δ.
7. 1. Let ℛ be the set of all binary relations on a set A. Then (ℛ,∘) is a monoid (http://planetmath.org/Monoid) with Δ as the identity element.

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

• •
• •
• •
  ρ is anti-symmetric if ρ∩ρ-1⊆Δ;
• •
• •
  ρ is a pre-order if it is reflexive and transitive
• •
  ρ is a partial order 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 symmetry and anti-symmetry are preserved by the inverse operation.

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 a∈A and b∈B, define

ρ⁢(a,⋅)⊆B is called the section 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 ⁢b∈B}, and
• •
  ran⁡(ρ):={b∣(a,b)∈ρ⁢ for some ⁢a∈A}.

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. 1. dom⁡(ρ) is the disjoint union of A-sections of ρ and ran⁡(ρ) is the disjoint union of B-sections of ρ.
3. 1. dom⁡(ρ-1)=ran⁡(ρ) and ran⁡(ρ-1)=dom⁡(ρ).
4. 1. ρ∘ρ-1=dom⁡(ρ)×dom⁡(ρ) and ρ-1∘ρ=ran⁡(ρ)×ran⁡(ρ).
5. 1. If A=B, then dom⁡(ρ)×A=ρ∘A2 and ran⁡(ρ)=A2∘ρ.
6. 1. 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 R∘S, as a subset of A1×⋯×An-1×B2×⋯⁢Bm, to be the set

      {(a1,…,an-1,b2,…,bm)∣∃c∈C⁢ 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 R∘S={a∣(a,c)∈R⁢ and ⁢c∈S}. The case where m=2 and n=1 is similar. If m=n=1, then R∘S={ true } if R∩S≠∅. Otherwise, it is set to { false }.