Relation: For any non-empty sets A and B, a subset of A × B is called a relation from A to B.
Example: A relation assigns the x’s with y’s
This relation can be written as {(1, 6), (2, 2), (3, 4), (4, 8), (5, 10)}
Example:
A x B = {{a, x), (b, x), (c, x), (a, y), (b, y), (c, y), (a, z), (b, z), (c, z)}
R = {(a, y), (b, z), (c, z)}
If S is a relation in A i.e. S ⊂ A × A and (x, y) ∈ S, we say x is related to y by S.
Types of Relation
Void or Empty Relation: relation in the set A with no elements is called an empty relation. Φ ⊂ A × A, Φ is a relation called empty relation.
{(x, y) A x B, y = x + 6} = {(2, 8), (4, 10)}
Universal Relation: A relation in the set A which is A × A itself is called a universal relation.
Reflexive Relation: If S is a relation in the set A and aSa, ∀ a ∈ A i.e. (a, a) ∈ S, a ∈ A, we say S is a reflexive relation.
Example: Let A = {3, 4, 5} and R = {(a, a): a A}. Hence, R = {(3, 3), (4, 4), (5, 5)} which is a reflexive relation.
Symmetric Relation: If S is a relation in a set A and if aSb ⇒ bSa i.e. (a, b) ∈ S ⇒ (b, a) ∈ S ∀ a, b ∈ A. We say S is a symmetric relation in A.
Example: The relation “is equal to” is a symmetric relation for if a = b then b = a
Transitive Relation: If S is a relation in the set A and if aSb and bSc ⇒ aSc ∀ a, b, c ∈ A i.e. (a, b) ∈ S and (b, c) ∈ S ⇒ (a, c) ∈ S ∀ a, b, c ∈ A, thus we say that S is a transitive relation in A.
Example: The relation “is greater than” is a transitive relation, if a > b and b > c, then a > c
Equivalence Relation: If a relation S in a set A is reflexive, symmetric and transitive is called an equivalence relation in A. I.e. relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)} on set A = {1, 2, 3} is equivalence relation as it is reflexive, symmetric, and transitive
If S is equivalence relation and (x, y) ∈ S then x ~ y.
Anti-symmetric Relation: If S is a relation in A and if (a, b) ∈ S and (b, a) ∈ S ⇒ a = b ∀ a, b, ∈ A, then S is said be an anti-symmetric relation.
Equivalence Classes: Let A bean equivalence relation in A. let a ∈ A, then the subset {x ∈ A, xSa} is said to be equivalence class corresponding to a.