1. Introductions to Relations

 

Binary Relation

Let us consider A and B are two non-empty arbitrary sets. A binary relation or, simply, relation R is defined to be a subset of A x B from a set A to B. Suppose R is a relation from A to B. Then R is a set of ordered pairs (a, b) where a ∈ A and b ∈ B.

If (a, b) ∈ R and R ⊆ A x B, then we say that "a is related to b by R" i.e. aRb. If A and B are equal sets, then R is a relation from a set A to itself or from a set B to itself, then we say that R ∈ A x A or R ∈ B x B is a relation on A.

If there are m elements in set A and n elements in set B, then maximum number of elements in the largest relation set is m x n. Hence maximum combinations of relations from A to B is 2^{m x n}.

Example: Let A = {1, 2} and B = {a, b}
Largest relation set or A x B = {(1, a), (1, b), (2, a), (2, b)}
Smallest relation set = ∅
Different combinations of relation sets are:
R₁ = ∅
R₂ = {(1, a)}
R₃ = {(1, b)}
R₄ = {(2, a)}
R₅ = {(2, b)}
R₆ = {(1, a), (1, b)}
R₇ = {(1, a), (2, a)}
R₈ = {(1, a), (2, b)}
R₉ = {(1, b), (2, a)}
R₁₀ = {(1, b), (2, b)}
R₁₁ = {(2, a), (2, b)}
R₁₂ = {(1, a), (1, b), (2, a)}
R₁₃ = {(1, a), (1, b), (2, b)}
R₁₄ = {(1, b), (2, a), (2, b)}
R₁₅ = {(1, a), (2, a), (2, b)}
R₁₆ = {(1, a), (1, b), (2, a), (2, b)}

Domain of Relation

The domain of relation R is the set of all first elements of the ordered pairs which belong to R. If the two non-empty arbitrary sets are A and B, related by a Relation R from A to B, then the set of elements in A is the domain of relation R. It is denoted by DOM(R).

Range of Relation

The range of relation R is the set of all second elements of the ordered pairs which belong to R. If the two non-empty arbitrary sets are A and B, related by a Relation R from A to B, then the set of elements in B is the range of relation R. It is denoted by RAN(R).

Example

Let A = {a, b, c, d}, B = {1, 2, 3, 4} and R = {(a, 1), (b, 2), (b, 4), (c, 1)}
DOM(R) = {(a, b, c}
RAN(R) = {1, 2, 4}

Complement of a Relation

Consider a relation R from a set A to set B. The complement of relation R denoted by R is a relation from A to B such that

R^' = {(a, b) : (a, b) ∈ A x B and (a, b) ∉ R}

Example: Let A = {a, b}, B = {1, 2, 3} and R = {(a, 2), (b, 1), (b, 3)}
R^' = {(a, 1), (a, 3), (b, 2)}

Inverse of a Relation

Consider a relation R from a set A to set B. The inverse of relation R denoted by R^-1 is a relation from B to A which consists of those ordered pairs which, when reversed, belong to R, that is

R^-1 = {(b, a) : (a, b) ∈ A x B and (a, b) ∈ R}

Example: Let A = {a, b}, B = {1, 2, 3} and R = {(a, 2), (b, 1), (b, 3)}
R^-1 = {(2, a), (1, b), (3, b)}

Previous                                  Next