Relations and Functions

Types of Relations

  • Identity Relation: R is an identity relation if (a, b) ∈ R if a = b, a ∈ A, b ∈ A. In other words, every element of ‘A’ is related to only itself.
  • Universal Relation: Let ‘A’ be any set and ‘R’ be the set A × A, then R is called the universal relation in ‘A’.
  • Void Relation: φ is called void relation in a set.
  • Types of Relations:
        Reflexive: If aRa ∀ a ∈ A i.e. if (a, a) ∈ R ∀ a ∈ A
        Symmetric: If aRb ⇒ bRa ∀ a, b ∈ A, i.e. if (a, b) ∈ R ⇒ (b, a) ∈ R
        Antisymmetric: If aRb and bRa ⇒ a = b, ∀ a, b ∈ A
        Transitive: If aRb and bRc ⇒ aRc, ∀ a, b, c ∈ A, i.e. (a, b) ∈ R and (b, a) ∈ R ⇒ (a, c) ∈ R, ∀ a, b, c ∈ A
        Equivalence relation: It should be reflexive, symmetric and transitive.
  • Inverse relation: If R is a relation from A to B, then R−1 is a relation from B to A and is defined as R−1 = {(b, a) / (a, b) ∈ R}
               i.e. aRb ⇒ bR−1a
        Domain of R = Range of R−1
        Range of R = Domain of R−1
  • Composite relation: If R ⊆ A × B and S ⊆ B × C then the composite relation is SoR ⊆ A × C
    SoR = {(a, b) ∈ R and (b, c) ∈ S ⇒ (a, c) ∈ SoR}
  • Partially ordered relation: A relation R is defined on the set A is said to be partially ordered relation if it is reflexive and antisymmetric and transitive.
  • Every identity relation is reflexive, converse need not be true also identity relation is reflexive, symmetric and transitive
  • The relation R on a set A is symmetric if and only if R = R−1.
  • The identity relation on a set is an anti-symmetric relation.
  • A relation which is not symmetric need not be antisymmetric.
  • a and b are relatively prime means the greatest common divisor of a and b is equal to 1
  • a ≡ b (mod m) means a – b is divisible by m.

Part1: View the Topic in this video From 48:30 To 52:54

Part2: View the Topic in this video From 00:40 To 54:40

Part3: View the Topic in this video From 00:40 To 15:48

Disclaimer: may from time to time provide links to third party Internet sites under their respective fair use policy and it may from time to time provide materials from such third parties on this website. These third party sites and any third party materials are provided for viewers convenience and for non-commercial educational purpose only. Compete does not operate or control in any respect any information, products or services available on these third party sites. makes no representations whatsoever concerning the content of these sites and the fact that has provided a link to such sites is NOT an endorsement, authorization, sponsorship, or affiliation by with respect to such sites, its services, the products displayed, its owners, or its providers.

  • The number of reflexive relations from A to A is 2n(n − 1). If n(A) = n.
  • The number of symmetric relations from A to A is 2^{\frac{n(n+1)}{2}} if n(A) = n.