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.

• Reflexive

  • A relation is reflexive if aRa holds.

  • Ex. 3≤3 holds; so ‘≤‘ is reflexive.

• Irreflexive (or anti-reflexive)

  • A relation if irreflexive if aRa does not hold.

  • Ex. 3 < 3 does not hold; therefore, < is irreflexive.

• Coreflexive

  • A relation is coreflexive if aRb only holds when a = b.

  • Ex. A relation on integers where each even number is related to itself and there are no other relations. Note: Equality is the only relation that is both reflexive and coreflexive.

• Quasi-reflexive

  • A relation is quasi-reflexive if aRb implies aRa and bRb.

  • Ex. A relation that states “has the same limit as” in regards to sequences. If two sequences have the same limit, the limit of the sequence is the limit of the sequence.

• Antisymmetric

  • A relation is antisymmetric if aRb = bRa only if a = b. (Note: there is no guarantee that aRb holds)

  • Ex. 3 ≤3 = 3 ≤ 3, but 3 ≤ 4 ≠ 4 ≤ 3

• Symmetric

  • A relation is symmetric if aRb = bRa always holds.

  • Ex. S ∪? = S ∪?

• Asymmetric

  • A relation is symmetric if aRb holds, then bRa does not hold.

  • Ex. < is asymmetric. I.e. Irreflexive and Transitive

• Connex

  • A relation is connex if aRb holds and bRa holds for all a, b ∈X. (i.e. every domain element comparable).

  • Ex. ≤ is a connex relation

• Semiconnex

  • A relation is semiconnex if aRb holds and bRa holds for all a, b ∈X, when a≠b. (i.e. every distinct element of a domain is comparable).

  • Ex. <is a connex relation

Binary Relations – Types

• Preorder Relation (or Quasiorder)

  • Reflexive

  • Transitive

• Strict Order Relation (or Strong Partial Order, or Strict Partial Order)

  • Antisymmetric

  • Irreflexive

  • Transitive

  • Ex. < is Asymmetric, Transitive in the ℝ domain.

  • Note: Antisymmetric and Irreflexive implies Asymmetric.

• Partial Order Relation (or POSET, Weak Partial Order, or Non-Strict Partial Order)

  • Antisymmetric

  • Reflexive

  • Transitive

  • Ex. ≤ is Antisymmetric, Antisymmetric, Transitive in the ℝ domain.

• Total Order Relation

  • Antisymmetric

  • Reflexive

  • Transitive

  • Connex

  • Ex. ≤ is Antisymmetric, Transitive, Connex in the ℝ domain.

• Equivalence Relation

  • Symmetric

  • Reflexive

  • Transitive

  • Ex. = is Symmetric, Reflexive, and Transitive.

Binary Relations – Other Properties

• Equivalence Classes

  • Equivalence relations may naturally split up a set into subsets of equivalence classes.

  • Ex. Consider the relation “has the same color as”. All green elements will be lumped into one equivalence class, all blue elements into another, etc..

• Closure

  • A closure (of a property) for a relation is a new relation that is created by adding as few pairs as possible to give the original relation a specific property.

• Dual (or inverse, or opposite order)

  • The dual of a relation is the relation obtained by flipping the ordering or applying the definition in inverse order.