next up previous contents
Next: Equivalence relations Up: Binary relations Previous: The general case   Contents

Binary relations between elements of a set

Let $ E \times E$ be the Cartesian square of $ E$, i.e. the set of pairs of elements of $ E$, $ E \times E = \{ (a,b) \; \vert \; a,b \in E \}$. A binary relation $ \mathcal{R}$ on $ E$ is a subset of $ E \times E$. We write $ a \mathrel{\mathcal{R}}b$ iff $ (a,b) \in \mathcal{R}$. We can think of $ \mathcal{R}$ as a directed graph with an edge from $ a$ to $ b$ iff $ a \mathrel{\mathcal{R}}b$. For example, take $ E=\{ 2,4,5,6,8,10 \}$, together with the relation denoted by $ \vert$ and defined as follows: for any $ a$ and $ b$ in $ A$, $ a\vert b$ if, and only if, $ b$ is a multiple of $ a$. For this relation, the graph is

$\displaystyle \mathcal{G}= \{ (2,2),(2,4),(2,6),(2,8),(2,10),(4,8),(5,10) \}.$    

This can be dispayed as in Figure 2. A loop on an element means that the element is related to itself (here this occurs for every element as every natural number is a multiple of itself).

Figure 2: The directed graph of a relation
\begin{figure}
\centering
\mbox{\epsfig{file=InSetRelation-1.eps,height=3.5cm}}
\end{figure}

Definition 4.2.1   A relation $ \mathcal{R}$ on the set $ E$ is reflexive if

$\displaystyle \forall a \in E, \; a \mathrel{\mathcal{R}}a.$    

Example 4.2.2   Let $ A=\{a,b,c,d,e \}$ be a set and let $ \mathcal{R}$ be the binary relation on $ A$ determined by the diagram in Figure 3.

Figure 3: Diagrams for a reflexive relation
\begin{figure}
\centering
\mbox{\subfigure[]{\epsfig{file=ReflexiveRelation-1...
...bfigure[]{\epsfig{file=ReflexiveRelation-2.eps,width=4.5cm}}
}
\end{figure}

The relation $ \mathcal{R}$ is reflexive.

Example 4.2.3   Let $ E$ be the set of inhabitants of a given town. We define two relations:
  1. For any two inhabitants $ a$ and $ b$ of $ E$, we denote $ a \mathcal{R} b$ if $ a$ lives next door to $ b$. This relation is not reflexive, as a single inhabitant cannot live next door to himself (actually, we should give a counter-example).
  2. In the same set $ E$, we denote $ a \mathcal{R} b$ if they live in a flat with the same number of rooms. This is a reflexive relation.

Definition 4.2.4   A relation $ \mathcal{R}$ on the set $ E$ is symmetric if

$\displaystyle \forall a,b \in E, \; a \mathrel{\mathcal{R}}b \Rightarrow b \mathrel{\mathcal{R}}a.$    

Example 4.2.5   Take $ A=\{a,b,c,d,e \}$ and let $ \mathcal{R}$ be the binary relation on $ A$ determined by the diagram in Figure 4.

Figure 4: A diagram for a symmetric relation
\begin{figure}
\centering
\mbox{\epsfig{file=SymmetricRelation.eps,height=4cm}}
\end{figure}

This relation is symmetric.

Note that the relation in this example is not reflexive, as the element $ b$ is not related to itself (in the diagram, there is no point at $ (b,b)$).

Example 4.2.6  
  1. Let $ E$ be the set of students of an institution. If $ a$ and $ b$ are two students in $ E$, we write $ a \mathrel{\mathcal{R}}b$ when $ a$ and $ b$ come from the same town. The relation $ \mathcal{R}$ is symmetric: for any two students $ a$ and $ b$, saying that ``$ a$ and $ b$ come from the same town'' is equivalent (thus implies) saying that ``$ b$ and $ a$ come from the same town''.
  2. Let $ A$ be the set of children in a kindergarden. For two children $ x$ and $ y$, we write $ x \mathrel{\mathcal{R}}y$ if $ x$ is the sister of $ y$. Being symmetric or not depends on the set $ E$ itself. If $ x$ is the sister of $ y$ and $ y$ is a boy, then $ y \not\mathcal{R}x$.

Definition 4.2.7   A relation $ \mathcal{R}$ on the set $ E$ is transitive if

$\displaystyle \forall
 a,b,c \in E, \; [(a \mathrel{\mathcal{R}}b) \wedge (b \mathrel{\mathcal{R}}c)] \Rightarrow a \mathrel{\mathcal{R}}c.$    

Example 4.2.8       
  1. The binary relation of Example 2.5 is not transitive. There we have: $ a \mathcal{R} b$ and $ b \mathcal{R}d$, but $ a\not\mathcal{R}d$.
  2. Let $ E$ be the set of all the students in a class. We define the relation $ \mathcal{S}$ on $ E$ as follows: if $ x$ and $ y$ are two students in $ E$, we write $ x \mathcal{S} y$ if $ x$ and $ y$ have the same eye color. This relation is transitive: suppose that $ x$, $ y$ and $ z$ are any three students in $ E$ such that $ x$ and $ y$ have the same eye color and $ y$ and $ z$ have the same eye color; then $ x$ and $ z$ have the same eye color.

Note that transitivity is not an immediate constatation from a cartesian diagram; it is more easily seen on an arrow diagram (how?).

Figure 5: Diagrams for a transitive relation
\begin{figure}
\centering
\mbox{\subfigure{\epsfig{file=TransitiveRelation-1....
...subfigure{\epsfig{file=TransitiveRelation-2.eps,height=4cm}}
}
\end{figure}

Definition 4.2.9   A relation $ \mathcal{R}$ on the set $ E$ is antisymmetric if

$\displaystyle \forall a,b \in E, \; 
 [ (a \mathrel{\mathcal{R}}b) \wedge ( b \mathrel{\mathcal{R}}a) ] \Rightarrow a = b.$    

Example 4.2.10   Let $ E= \mathbb{N}- \{ 0 \}$ be the set of all positive integers. We define the binary relation $ \vert$ by:

$\displaystyle \forall a \in E, \; \forall b \in E, \; a \; \vert \; b \Longleftrightarrow 
 \exists k \in E \; ; \; b=ka.$    

In other words $ a \; \vert \; b$ if, and only if, $ b$ is a multiple of $ a$. For instance, $ 3 \; \vert \; 15$ and $ 12 \; \vert \; 72$, but $ 5 \; \not\vert \; 17$. The relation $ \vert$ is transitive. Let $ a$, $ b$ and $ c$ be three positive integers such that $ a \; \vert \; b$ and $ b \; \vert \; c$, i.e.

$\displaystyle \exists k \in E \; ; \; b=ka$    and $\displaystyle \exists q \in E \; ; \; c=qb$    

It follows that $ c=qb=q(ka)=(qk)a$, and $ qk$ is an integer. Whence the result.

We will discover later the great importance of this relation in Mathematics.
next up previous contents
Next: Equivalence relations Up: Binary relations Previous: The general case   Contents
root 2002-06-10