MTH4140 Home
# Relations

## Cartesian product of sets

## Relation

*The elements \(2\) and \(a\) are in relation \(S\)*
**Definition**
**Problem 1**
## Equivalence classes

**Problem 2**

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.

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

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\).

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.\]

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*}

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\}.\]

For each of the relations from Problem 1 that happens to be an equivalence relation, determine the equivalence classes.