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.
Read more about this topic: Binary Relation
Famous quotes containing the words operations and/or relations:
“You cant have operations without screams. Pain and the knifetheyre 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] (18351910)