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

$$\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

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

$$\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

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

$$\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

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

$$\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

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

$$\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:

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

$$\exists k \in E \; ; \; b=ka \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.