Formal Methods 101: Binary Relations

Introduction:

  • Relations (R) are a generalization of a functions (f), (such that f ⊂ R) and are used to specify sets; or more intuitively the relationship between a domain and codomain.
  • f is a strict subset of R because, though all functions are relations, not all relations are functions.
  • Standard notation:
    • Relation R
    • Set Element a, Set Element b
    • (a, b) ∈ R | a, b ∈ S
    • An easy way to interpret this that element ‘a’ is related to element ‘b’ if and only if (iff) the ordered pair (a, b) is contained in the set R.
    • Example: (1, 2) ∈ ‘<‘ | 1, 2 ∈ N
  • Shorthand notation (more intuitive):
    • Relation R
    • Set Element a, Set Element b
    • aRb | a, b ∈ S
    • Example: 1<2 | 1, 2 ∈ N

Binary Relations – Functions

  • A function is a relation in an element of a domain (set) maps to only one element in the codomain (set). If it maps to more than one, it is strictly a relation, not a function.
  • Functions may be broken down into Partial Order Functions and Total Order Functions. A function is a partial order function if the elements that map from the domain, map only to at most one element of the codomain. A function is a total order function if every element of the domain maps to at most one element of the codomain.
  • A function is said to have a ‘one-to-one’ correspondence (coined ‘bijective function’) if each element of the domain is mapped to exactly one element of the codomain, and each element of the codomain is mapped to exactly one element of the domain.
  • For example, a function maps from all the set of all real (domain) numbers to the set of all real numbers (codomain) such as the function describe below; is a bijective function because it has a one-to-one correspondence between its domain and codomain.
  • f:R→R | f(x)=2X+10

Binary Relations – Properties

  • Inverse
    • The inverse of a relation is denoted R-1
    • Ex. The inverse of < is >.
  • Transitive
    • A relation is transitive if aRb and bRc, then aRc.
    • Ex. 1<2 and 2<3, therefore 1<3.
  • Reflective
    • A relation is reflexive if aRa holds.
    • Ex. 3≤3 holds; so ‘≤‘ is reflexive.
  • Antisymmetric
    • A relation is antisymmetric if aRb = bRa only when a = b.
    • Ex. 3 ≤3 = 3 ≤ 3, but 3 ≤ 4 ≠ 4 ≤ 3
  • Symmetric
    • A relation is symmetric if aRb = bRa always holds.
    • Ex. S ∪ Q =  S ∪ Q
  • Partial Order Relation
    • A partial order relation is a relation that is transitive and antisymmetric
    • Ex. ≤ is transitive, antisymmetric in the R domain.
  • Total Order Relation
    • A total order relation is a relation that is transitive, antisymmetric, and every domain element comparable.
    • Ex. ≤ is transitive, antisymmetric, and every element of the domain is comparable in the R domain. (Note: ≤ is both a partial order and total order relation.)
  • Equivalence
    • An equivalence relation is a relation that is transitive, reflexive, and symmetric.
  • Closure
    • A closure (of a property) for a relation is a new relation that is created by added as few pairs as possible to give the original relation a specific property.

Leave a Reply

Your email address will not be published. Required fields are marked *