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.