Sets, Relations, & Functions
Mathematical Logic
Group Theory
Counting & Probability
Mathematical & Recurrence
Discrete Structures
Boolean Algebra
Discrete Mathematics Resources
- Discrete Mathematics - Discussion
- Discrete Mathematics - Resources
- Discrete Mathematics - Quick Guide
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Discrete Mathematics - Relations
Whenever sets are being discussed, the relationship between the elements of the sets is the next thing that comes up. Relations may exist between objects of the same set or between objects of two or more sets.
Definition and Properties
A binary relation R from set x to y (written as $xRy$ or $R(x,y)$) is a subset of the Cartesian product $x imes y$. If the ordered pair of G is reversed, the relation also changes.
Generally an n-ary relation R between sets $A_1, dots , and A_n$ is a subset of the n-ary product $A_1 imes dots imes A_n$. The minimum cardinapty of a relation R is Zero and maximum is $n^2$ in this case.
A binary relation R on a single set A is a subset of $A imes A$.
For two distinct sets, A and B, having cardinapties m and n respectively, the maximum cardinapty of a relation R from A to B is mn.
Domain and Range
If there are two sets A and B, and relation R have order pair (x, y), then −
The domain of R, Dom(R), is the set $lbrace x :| : (x, y) in R :for: some: y: in: B brace$
The range of R, Ran(R), is the set $lbrace y: |: (x, y) in R :for: some: x: in: A brace$
Examples
Let, $A = lbrace 1, 2, 9 brace $ and $ B = lbrace 1, 3, 7 brace$
Case 1 − If relation R is equal to then $R = lbrace (1, 1), (3, 3) brace$
Dom(R) = $lbrace 1, 3 brace , Ran(R) = lbrace 1, 3 brace$
Case 2 − If relation R is less than then $R = lbrace (1, 3), (1, 7), (2, 3), (2, 7) brace$
Dom(R) = $lbrace 1, 2 brace , Ran(R) = lbrace 3, 7 brace$
Case 3 − If relation R is greater than then $R = lbrace (2, 1), (9, 1), (9, 3), (9, 7) brace$
Dom(R) = $lbrace 2, 9 brace , Ran(R) = lbrace 1, 3, 7 brace$
Representation of Relations using Graph
A relation can be represented using a directed graph.
The number of vertices in the graph is equal to the number of elements in the set from which the relation has been defined. For each ordered pair (x, y) in the relation R, there will be a directed edge from the vertex ‘x’ to vertex ‘y’. If there is an ordered pair (x, x), there will be self- loop on vertex ‘x’.
Suppose, there is a relation $R = lbrace (1, 1), (1,2), (3, 2) brace$ on set $S = lbrace 1, 2, 3 brace$, it can be represented by the following graph −
![Relation](/discrete_mathematics/images/relation.jpg)
Types of Relations
The Empty Relation between sets X and Y, or on E, is the empty set $emptyset$
The Full Relation between sets X and Y is the set $X imes Y$
The Identity Relation on set X is the set $lbrace (x, x) | x in X brace$
The Inverse Relation R of a relation R is defined as − $R = lbrace (b, a) | (a, b) in R brace$
Example − If $R = lbrace (1, 2), (2, 3) brace$ then $R $ will be $lbrace (2, 1), (3, 2) brace$
A relation R on set A is called Reflexive if $forall a in A$ is related to a (aRa holds)
Example − The relation $R = lbrace (a, a), (b, b) brace$ on set $X = lbrace a, b brace$ is reflexive.
A relation R on set A is called Irreflexive if no $a in A$ is related to a (aRa does not hold).
Example − The relation $R = lbrace (a, b), (b, a) brace$ on set $X = lbrace a, b brace$ is irreflexive.
A relation R on set A is called Symmetric if $xRy$ imppes $yRx$, $forall x in A$ and $forall y in A$.
Example − The relation $R = lbrace (1, 2), (2, 1), (3, 2), (2, 3) brace$ on set $A = lbrace 1, 2, 3 brace$ is symmetric.
A relation R on set A is called Anti-Symmetric if $xRy$ and $yRx$ imppes $x = y : forall x in A$ and $forall y in A$.
Example − The relation $R = lbrace (x, y) o N |:x leq y brace$ is anti-symmetric since $x leq y$ and $y leq x$ imppes $x = y$.
A relation R on set A is called Transitive if $xRy$ and $yRz$ imppes $xRz, forall x,y,z in A$.
Example − The relation $R = lbrace (1, 2), (2, 3), (1, 3) brace$ on set $A = lbrace 1, 2, 3 brace$ is transitive.
A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive.
Example − The relation $R = lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) brace$ on set $A = lbrace 1, 2, 3 brace$ is an equivalence relation since it is reflexive, symmetric, and transitive.