Relation & Its Types
Relations Definition
A relation in mathematics is a rule that associates elements of one set with elements of another (or the same) set. Formally, a relation from a set A to a set B is any subset of the Cartesian product A × B. Each element of a relation is an ordered pair (x, y) with x ∈ A and y ∈ B.
Real-life example: when students stand in a queue arranged by ascending height, there is an ordered relation between each student and their height. Another way to describe a relation is simply: "a set of ordered pairs".
If R is a relation from A to B then
- R ⊂ A × B.
- The set of first components of ordered pairs in R is called the domain of R and is denoted Dom(R).
- The set of second components of ordered pairs in R is called the range (or image) of R and is denoted Ran(R).
Example:
- Let R = {(1,2), (-3,4), (5,6), (-7,8), (9,2)}.
- Then Dom(R) = {-7, -3, 1, 5, 9}.
- And Ran(R) = {2, 4, 6, 8}.
A relation may be visualised in different ways: by listing ordered pairs, by an arrow (mapping) diagram, by a directed graph (digraph), or by an adjacency matrix. The mapping shown above is an example of a relation from set A into set B where ordered pairs are (1,c), (2,n), (5,a), (7,n); here set {1,2,5,7} is the domain and {a,c,n} is the range.
Representations of a Relation
Common representations useful in computer science and discrete mathematics:
- Set of ordered pairs: explicit listing, e.g. R = {(1,2), (2,3)}.
- Directed graph (digraph): vertices represent elements; an arrow from x to y indicates (x,y) ∈ R.
- Adjacency matrix: for finite A = {a1,...,an}, the matrix M of R has M[i,j] = 1 if (ai,aj) ∈ R, otherwise 0. This is useful for algorithmic operations (composition, transitive closure).
- Predicate form: R = {(x,y) ∈ A × B : P(x,y)} where P is a condition, e.g. "x divides y".
Basic Properties of Relations
When the domain and range are the same set A (i.e. R ⊂ A × A), certain properties are important in classification and applications:
- Reflexive: ∀a ∈ A, (a,a) ∈ R.
- Symmetric: ∀a,b ∈ A, if (a,b) ∈ R then (b,a) ∈ R.
- Antisymmetric: ∀a,b ∈ A, if (a,b) ∈ R and (b,a) ∈ R then a = b.
- Transitive: ∀a,b,c ∈ A, if (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R.
These properties can be combined to define important classes of relations such as equivalence relations and partial orders (see below).
Types of Relations
Below are common types of relations with formal definitions, examples and remarks.
Empty Relation (Null Relation)
A relation R on A is an empty relation if it contains no ordered pairs.
- Notation: R = ∅, and ∅ ⊂ A × A.
- Example: For A = {1,2,3}, R = ∅ has Dom(R) = ∅ and Ran(R) = ∅.
- Remarks: An empty relation is vacuously transitive and symmetric, but it is reflexive only when A = ∅.
Universal Relation (Full Relation)
The universal relation on A is the entire Cartesian product A × A.
- Notation: R = A × A.
- Example: If A = {a,b,c} then R = {(x,y) : x,y ∈ A} contains all nine ordered pairs.
- Remarks: Universal relation is reflexive, symmetric and transitive.
Identity Relation (Diagonal Relation)
The identity relation on A contains exactly those pairs that relate an element to itself.
- Notation: I_A = {(a,a) : a ∈ A}.
- Example: For A = {a,b,c}, I_A = {(a,a), (b,b), (c,c)}.
- Remarks: Identity relation is reflexive, symmetric only if A has at most one element, antisymmetric, and transitive.
Inverse Relation
The inverse (or converse) of a relation R ⊂ A × B is the relation R-1 ⊂ B × A obtained by swapping each ordered pair.
- Definition: R-1 = {(b,a) : (a,b) ∈ R}.
- Example: If R = {(a,b), (c,d)} then R-1 = {(b,a), (d,c)}.
- Remarks: (R-1)-1 = R, and Dom(R) = Ran(R-1), Ran(R) = Dom(R-1).
Reflexive Relation
A relation R on A is reflexive if every element of A is related to itself.
- Formal: ∀a ∈ A, (a,a) ∈ R.
- Example: On A = {1,2}, R = {(1,1), (2,2), (1,2)} is reflexive.
- Remarks: Reflexivity depends on the underlying set A. Adding or removing (a,a) changes reflexivity.
Symmetric Relation
A relation R on A is symmetric if whenever a is related to b then b is related to a.
- Formal: ∀a,b ∈ A, (a,b) ∈ R ⇒ (b,a) ∈ R.
- Example: For A = {1,2}, R = {(1,2), (2,1)} is symmetric. If R also contains (1,1) and (2,2) it remains symmetric.
- Remarks: A relation can be symmetric without being reflexive or transitive.
Antisymmetric Relation
A relation R on A is antisymmetric if the only time two distinct elements relate in both directions is when they are equal.
- Formal: ∀a,b ∈ A, (a,b) ∈ R and (b,a) ∈ R ⇒ a = b.
- Example: The relation "≤" on numbers is antisymmetric because if a ≤ b and b ≤ a then a = b.
- Remarks: Antisymmetry does not forbid (a,a); it only restricts mutual pairs for distinct elements.
Transitive Relation
A relation R on A is transitive if an indirect link composes into a direct link.
- Formal: ∀a,b,c ∈ A, (a,b) ∈ R and (b,c) ∈ R ⇒ (a,c) ∈ R.
- Example: Relation "is ancestor of" is transitive: if A is ancestor of B and B of C, then A is ancestor of C.
- Remarks: Transitive closure of R is the smallest transitive relation containing R; algorithms (e.g. Warshall) compute it from the adjacency matrix.
Equivalence Relation
An equivalence relation on A is a relation that is reflexive, symmetric and transitive simultaneously.
- Formal: R is an equivalence relation ⇔ R is reflexive, symmetric and transitive.
- Example: On integers, the relation "congruent modulo n" is an equivalence relation.
- Remarks: Equivalence relations partition the set A into disjoint equivalence classes. For a ∈ A, the equivalence class [a] = {x ∈ A : (a,x) ∈ R}.
Partial Order
A partial order is a relation that is reflexive, antisymmetric and transitive.
- Formal: R is a partial order ⇔ R is reflexive, antisymmetric and transitive.
- Example: The relation "≤" on real numbers and the subset relation ⊆ on sets are partial orders.
- Remarks: A set equipped with a partial order is called a poset. Not every pair of elements need be comparable in a partial order.
Examples and Small Exercises
- Let A = {1,2,3}. Decide which of the following R are reflexive, symmetric, antisymmetric and/or transitive:
- R1 = ∅
- R2 = A × A
- R3 = {(1,1),(2,2),(3,3),(1,2),(2,1)}
- Compute inverse and composition: If R = {(1,2),(2,3)} and S = {(2,1),(3,2)}, then R-1 = {(2,1),(3,2)} and R ∘ S = {(1,1),(2,2)}? (verify by arranging ordered-pair composition rules).
- Given adjacency matrix M of a relation on {a,b,c}, use matrix multiplication (Boolean product) to check for paths of length 2 and decide transitivity.
Applications in Computer Science and Mathematics
- Equivalence relations are used to group objects by indistinguishability (e.g. hashing buckets, state minimisation in automata).
- Partial orders model dependency relations, scheduling (topological sort), and type hierarchies.
- Adjacency matrices and digraphs implement relations in algorithms: reachability, transitive closure, graph traversal (BFS/DFS).
- Inverse relations and relation composition form the basis of database query operations (joins) and relational algebra.
Summary
A relation is a subset of a Cartesian product and may be classified by properties such as reflexivity, symmetry, antisymmetry and transitivity. Important special relations include the empty relation, universal relation, identity relation, inverse relation, equivalence relations and partial orders. Visual and matrix representations make relations amenable to algorithmic treatment in computer science.
