MTH4140 Home
Relations
Cartesian product of sets
The cartesian product \(A\times B\) of sets \(A\) and \(B\) is the set of ordered pairs whose first component is from \(A\) and the second component is from \(B\). For example, if \(A=\{1,2,3,4\}\) and \(B=\{3, a, 9\}\), then their cartesian product is:
\[A\times B=\{(1,3), (1, a), (1,9), (2,3), (2,a), (2,9), (3,3), (3,a), (3,9), (4,3), (4,a), (4,9)\}.\]
We use the notation \(A^2\) for \(A\times A\).
Cartesian product is used to formally define many important concepts in mathematics. For the beginning, you may notice that we can define the two-dimensional plane as the product of the line \(\mathbb R\) with itself. Later on we will see that relations, functions, and graphs can be defined using cartesian product.
Relation
A subset \(S\subseteq A\times A\) is called a relation on the set \(A\).
Consider the set \(A=\{1,2,a,b,c\}\) and the relation \(S=\left\{(1,b), (2,a), (2,c), (c,1), (c,b)\right\}\). We write \((2,a)\in S\) and say
The elements \(2\) and \(a\) are in relation \(S\)
We also write \(2Sa\) instead of \((2,a)\in S\).
Some famous relations are \( < \) and \( > \) on the set \(\mathbb N\) of all positive integers. We write \((2,7)\in < \), or \(2 < 7\).
Definition
A relation \(\rho \subseteq A\times A\) is called reflexive if for every \(a\in A\) we have \(a\rho a\).
A relation \(\rho \subseteq A\times A\) is called symmetric if for every \(a,b\in A\) we have that \(a\rho b\) implies that \(b\rho a\).
A relation \(\rho \subseteq A\times A\) is called transitive if for every \(a,b,c\in A\) we have \[a\rho b\;\mbox{and} \;b\rho c \quad\quad \Longrightarrow \quad\quad a\rho c.\]
Problem 1
For each of the following relations determine whether it is reflexive, symmetric, and transitive.
- (a) Relation \( < \) on the set \(\mathbb N\);
- (b) Relation \(\leq\) on the set \(\mathbb N\);
- (c) Relation \( > \) on the set \(\mathbb N\);
- (d) Relation \(\equiv_3\) on the set \(\mathbb N\) defined as \(a\equiv_3b\) if and only if \(a\) and \(b\) have the same remainder when divided by \(3\);
- (e) The set \(A\) is defined as \[A=\left\{1,2,3,4,5,6,7\right\}.\] The relation \(\rho\) is defined as
\[\rho=\left\{
(1,2), (2,1), (1,5), (5,1), (2,5), (5,2), (3,7), (7,3), (4,6), (6,4)
\right\};\]
- (e) The set \(A\) is defined as \[A=\left\{1,2,3,4,5,6,7\right\}.\] The relation \(\eta\) is defined as
\begin{eqnarray*}\eta&=&\left\{
(1,2), (2,1), (1,5), (5,1), (2,5), (5,2), (3,7), (7,3), (4,6), (6,4),\right.\newline && \left. (1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7)
\right\}.\end{eqnarray*}
- (a) The relation \( < \) on \(\mathbb N\) is transitive, but is neither reflexive nor symmetric.
- (b) The relation \(\leq\) on the set \(\mathbb N\) is reflexive and transitive, but not symmetric.
- (c) The relation \( > \) on the set \(\mathbb N\) is transitive, but neither reflexive nor symmetric.
- (d) The relation \(\equiv_3\) on the set \(\mathbb N\) is reflexive, symmetric, and transitive.
- (e) The relation \(\rho\) is symmetric and transitive, but not reflexive.
- (e) The relation \(\eta\) is reflexive, symmetric, and transitive.
Equivalence classes
If \(\rho\) is an equivalence relation on \(A\) then for every given element \(x\in A\), the equivalence class of \(x\), denoted by \(C_x\) is the set defined in the following way:
\[C_x=\left\{y: y\rho x\right\}.\]
Problem 2
For each of the relations from Problem 1 that happens to be an equivalence relation, determine the equivalence classes.
- (a) The relation \( < \) on \(\mathbb N\) is not an equivalence relation.
- (b) The relation \(\leq\) on the set \(\mathbb N\) is not an equivalence relation.
- (c) The relation \( > \) on the set \(\mathbb N\) is not an equivalence relation.
- (d) The relation \(\equiv_3\) on the set \(\mathbb N\) is an equivalence relation. The equivalence classes are the following three sets
\begin{eqnarray*}
A=\left\{3i+1: i\in\mathbb N\right\},\quad B=\left\{3i+2: i\in\mathbb N\right\}, \mbox{ and}\quad C=\left\{3i:i\in\mathbb N\right\}.
\end{eqnarray*}
- (e) The relation \(\rho\) is not an equivalence relation.
- (e) The equivalence classes of the relation \(\eta\) are the following three sets
\begin{eqnarray*}
X=\left\{1,2,5\right\},\quad Y=\left\{3,7\right\}, \mbox{ and} \quad Z=\left\{4,6\right\}.
\end{eqnarray*}