Binary Relation - Operations On Binary Relations

Operations On Binary Relations

If R is a binary relation over X and Y, then the following is a binary relation over Y and X:

• Inverse or converse: R −1, defined as R −1 = { (y, x) | (x, y) ∈ R }. A binary relation over a set is equal to its inverse if and only if it is symmetric. See also duality (order theory).

If R is a binary relation over X, then each of the following is a binary relation over X:

• Reflexive closure: R =, defined as R = = { (x, x) | x ∈ X } ∪ R or the smallest reflexive relation over X containing R. This can be seen to be equal to the intersection of all reflexive relations containing R.
• Reflexive reduction: R ≠, defined as R ≠ = R \ { (x, x) | x ∈ X } or the largest irreflexive relation over X contained in R.
• Transitive closure: R +, defined as the smallest transitive relation over X containing R. This can be seen to be equal to the intersection of all transitive relations containing R.
• Transitive reduction: R −, defined as a minimal relation having the same transitive closure as R.
• Reflexive transitive closure: R *, defined as R * = (R +) =, the smallest preorder containing R.
• Reflexive transitive symmetric closure: R ≡, defined as the smallest equivalence relation over X containing R.

If R, S are binary relations over X and Y, then each of the following is a binary relation:

• Union: R ∪ S ⊆ X × Y, defined as R ∪ S = { (x, y) | (x, y) ∈ R or (x, y) ∈ S }.
• Intersection: R ∩ S ⊆ X × Y, defined as R ∩ S = { (x, y) | (x, y) ∈ R and (x, y) ∈ S }.

If R is a binary relation over X and Y, and S is a binary relation over Y and Z, then the following is a binary relation over X and Z: (see main article composition of relations)

• Composition: S ∘ R, also denoted R ; S (or more ambiguously R ∘ S), defined as S ∘ R = { (x, z) | there exists y ∈ Y, such that (x, y) ∈ R and (y, z) ∈ S }. The order of R and S in the notation S ∘ R, used here agrees with the standard notational order for composition of functions.