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 asor ) is a subset of the Cartesian product . If the ordered pair of G is reversed, the relation also changes.
Generally an n-ary relation R between setsis a subset of the n-ary product . The minimum cardinality of a relation R is Zero and maximum is in this case.
A binary relation R on a single set A is a subset of.
For two distinct sets, A and B, having cardinalities m and n respectively, the maximum cardinality 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
- The range of R, Ran(R), is the set
- Case 1 − If relation R is ‘equal to’ then
- Case 2 − If relation R is ‘less than’ then
- Case 3 − If relation R is ‘greater than’ then
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 relationon set , it can be represented by the following graph −
Types of Relations
- The Empty Relation between sets X and Y, or on E, is the empty set
- The Full Relation between sets X and Y is the set
- The Identity Relation on set X is the set
- The Inverse Relation R’ of a relation R is defined as −
Example − Ifthen will be
- A relation R on set A is called Reflexive if
Example − The relationon set is reflexive.
is related to a (aRa holds)
- A relation R on set A is called Irreflexive if no
Example − The relationon set is irreflexive.
is related to a (aRa does not hold).
- A relation R on set A is called Symmetric if
Example − The relationon set is symmetric.
implies , and .
- A relation R on set A is called Anti-Symmetric if
Example − The relationis anti-symmetric since and implies .
and implies and .
- A relation R on set A is called Transitive if
Example − The relationon set is transitive.
and implies .
- A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive.
Example − The relationon set is an equivalence relation since it is reflexive, symmetric, and transitive.