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) | xX } ∪ 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) | xX } 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: RSX × Y, defined as RS = { (x, y) | (x, y) ∈ R or (x, y) ∈ S }.
  • Intersection: RSX × Y, defined as RS = { (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 yY, 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.

Read more about this topic:  Binary Relation

Famous quotes containing the words operations and/or relations:

    You can’t have operations without screams. Pain and the knife—they’re inseparable.
    —Jean Scott Rogers. Robert Day. Mr. Blount (Frank Pettingell)

    I know all those people. I have friendly, social, and criminal relations with the whole lot of them.
    Mark Twain [Samuel Langhorne Clemens] (1835–1910)