In this article we build upon our previous article on sets to introduce relations, the way of expressing relationships between elements of sets. An understanding of relations is crucial to understand functions, widely used in many advanced topics in mathematics.
To understand the relations, we recommend familiarity with the concepts in
Follow the above links to first get acquainted with the corresponding concepts.
A relation from a set \( \sA \) to a set \( \sB \) is a subset of \( \sA \times \sB \), where \( \times \) denotes the Cartesian product.
Consider the sets \( \sA = \lbrace 1, 2, 3 \rbrace \) and \( \sB = \lbrace x, y, z \rbrace \).
$$ R_1 = \lbrace (1,x), (2, y), (1, z) \rbrace $$ $$ R_2 = \lbrace (x,1), (y,2), (z,3) \rbrace $$ $$ R_3 = \lbrace (1,1), (2, y), (3, z) \rbrace $$
Among these, \( R_1 \) is a relation from \( \sA \) to \( \sB \) and \( R_2 \) is a relation from \( \sB \) to \( \sA \). The set \( R_3 \) is not a relation between \( \sA \) and \( \sB \) because it contains the ordered pair \( (1,1) \).
The domain of a relation \( R \) from a set \( A \) to a set \( B \) is defined as $$ \text{dom}(R) = \{ a \in A: (a,b) \in R, \text{ for some } b \in B \} $$
Thus, the domain of a relation is the set of all elements of \( A \) that appear in the relation.
Consider the relation \( R = \lbrace (1,x), (2,y), (2,z), (3,x) \rbrace \). Then \( \text{dom}(R) = \lbrace 1, 2, 3 \rbrace \).
The range of a relation \( R \) from a set \( A \) to a set \( B \) is defined as $$ \text{range}(R) = \{ b \in B: (a,b) \in R, \text{ for some } a \in A \} $$
Thus, the range of a relation is the set of all elements of \( B \) that appear in the relation.
Consider the relation \( R = \lbrace (1,x), (2,y), (2,z), (3,x) \rbrace \). Then \( \text{range}(R) = \lbrace x, y, z \rbrace \).
If \( R \) is a relation from a set \( A \) to a set \( B \), then an inverse relation \( R^{-1} \) is defined as $$ R^{-1} = \{ (b,a) : (a,b) \in R \} $$
Consider the relation \( R = \lbrace (x,1), (x,2), (y,1), (z,2) \rbrace \)
The inverse relation is \( \inv{R} = \lbrace (1,x), (1,y), (2,x), (2,z) \rbrace \).
A relation on a set \( A \) is a relation such that both the domain and the range of the relation belong to \( A \). This means, relation on a set \( A \) is a subset of \( A \times A \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
The relation \( R = \lbrace (1,1), (1,2), (2,3) \rbrace \) is a relation on the set \( A \) since both coordinates of each ordered pair belong to \( A \).
A relation \( R \) on a set \( A \) is said to be reflexive, if \( (x,x) \in R, \forall x \in A \).
Note that a reflexive relation on a set may also contain ordered pairs of the form \( (x,y) \) such that \( x \ne y \), as long as \( x \in A \) and \( y \in A \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
A relation \( R \) on a set \( A \) is said to be irreflexive, if for every \( x \in A \), \( (x,x) \not\in R \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
A relation \( R \) on a set \( A \) is said to be symmetric , if \( (x,y) \in R \) implies that \( (y,x) \in R \) for all \(x,y \in A \).
Note that if \( (x,y) \not\in R \), then we do not require \( (y,x) \) to be in \( R \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
A relation \( R \) on a set \( A \) is said to be antisymmetric , if \( (x,y) \in R \) and \( (y,x) \in R \) only if \( x = y \), for all \(x,y \in A \).
Note that if \( (x,y) \not\in R \), then we do not require \( (y,x) \) to be in \( R \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
A relation \( R \) on a set \( A \) is said to be asymmetric , if \( (x,y) \in R \) implies that \( (y,x) \not\in R \) for all \(x,y \in A \).
Note that if \( (x,y) \not\in R \), then we do not require \( (y,x) \) to be absent from \( R \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
A relation \( R \) on a set \( A \) is said to be transitive, if \( (x,y) \in R \) and \( (y,z) \in R \) implies that \( (x,z) \in R \), for all \( x,y,z \in A \).
Note that if \( (x,y) \not\in R \) or \( (y,z) \not\in R \), then \( (x,z) \) is not required to be in \( R \).
Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).
A relation on a set is known as an equivalence relation if it is reflexive, symmetric, and transitive.
Let \( A = \lbrace 1, 2, 3 \rbrace \).
Thus, the relation \( R_4 \) is an equivalence relation.
If \( R \) is an equivalence relation on a set \( A \), then for \( a \in A \), the set of all elements related to \( a \) is known as it's equivalence class. It is denoted as \( [a] \) and defined as
$$ [a] = \{x \in A: (x,a) \in R \} $$
Let \( A = \lbrace 1, 2, 3 \rbrace \). Let \( R = \lbrace (1,1), (2,2), (3,3), (1,2), (2,1) \rbrace \) be an equivalence relation on \( A \).
Then, the following are the equivalence classes associated with elements of \( A \).
A relation \( \complement{R} \) is said to be a complementary relation to the relation \( R \) if for every \( (a,b) \in R \), it is the case that \( (a,b) \not\in \complement{R} \).
Consider the relation \( R = \set{ (a,b) | a < b } \) on a set of integers. The complement of this relation is the relation \( \complement{R} = \set{ (a,b) | a \ge b } \).
Let \( R \) be a relation on a set \( A \). The powers \( R^n \), where \( n = 1, 2, 3, \ldots\), are defined inductively by
$$ R^1 = R \text{ and } R^{n+1} = R^n \circ R $$
where \( \circ \) denotes the composite relation.
Let \( R = \set{(a,b), (b,c)} \). Then
$$ R^1 = \set{(a,b), (b,c)} $$ $$ R^2 = \set{(a,c)} $$
Consider a relation \( R \) on a set \( A \). Suppose \( R \) does not have a particular property \( P \), such as reflexivity, symmetry, or transitivity.
If there is another relation \( S \) on the set \( A \) with the property \( P \) containing \( R \) such that \( S \) is the subset of all relations on the set \( A \) with the property \( P \) that contain \( R \), then the set \( S \) is known as closure of \( R \) with respect to \( P \).
Consider a relation \( R = \set{(x,x)} \) on the set \( A = \set{x, y} \). Clearly, \( R \) is not reflexive. However, the set \( S = \set{(x,x), (y,y)} \) is reflexive and \( R \subseteq S \). Moreover, \( S \) will be the subset of any reflexive relation on the set \( A \) that contains \( R \).
Thus, the relation \( S \) is the reflexive closure of \( R \).
With a sound understanding of relations, we move on to specialized relations known as functions.
Help us create more engaging and effective content and keep it free of paywalls and advertisements!
Stay up to date with new material for free.