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

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.