around-binary-relations-on-sets-image

Around binary relations on sets

We are considering here binary relations on a set \(A\). Let’s recall that a binary relation \(R\) on \(A\) is a subset of the cartesian product \(R \subseteq A \times A\). The statement \((x,y) \in R\) is read as \(x\) is \(R\)-related to \(y\) and also denoted by \(x R y \).

Some importants properties of a binary relation \(R\) are:

reflexive
For all \(x \in A\) it holds \(x R y\)
irreflexive
For all \(x \in A\) it holds not \(x R y\)
symmetric
For all \(x,y \in A\) it holds that if \(x R y\) then \(y R x\)
antisymmetric
For all \(x,y \in A\) if \(x R y\) and \(y R x\) then \(x=y\)
transitive
For all \(x,y,z \in A\) it holds that if \(x R y\) and \(y R z\) then \(x R z\)

A relation that is reflexive, symmetric and transitive is called an equivalence relation. Let’s see that being reflexive, symmetric and transitive are independent properties.

Symmetric and transitive but not reflexive

We provide two examples of such relations. For the first one, we take for \(A\) the set of the real numbers \(\mathbb R\) and the relation \[R = \{(x,y) \in \mathbb R^2 \, | \, xy >0\}.\] \(R\) is symmetric as the multiplication is also symmetric. \(R\) is also transitive as if \(xy > 0\) and \(yz > 0\) you get \(xy^2 z >0\). And as \(y^2 > 0\), we have \(xz > 0\) which means that \(x R z\). However, \(R\) is not reflexive as \(0 R 0\) doesn’t hold.

For our second example, we take \(A= \mathbb N\) and \(R=\{(1,1)\}\). It is easy to verify that \(R\) is symmetric and transitive. However \(R\) is not reflexive as \(n R n\) doesn’t hold for \(n \neq 1\).

Reflexive and transitive but not symmetric

We take \(A=\mathbb R\) and \[R = \{(x,y) \in \mathbb R^2 \, | \, \vert x \vert \le \vert y \vert\}.\] One can verify that \(R\) is reflexive and transitive. It is also not symmetric. It is not antisymmetric either. As a counterexample we have \(\vert -3 \vert \le \vert 3 \vert\) and \(\vert 3 \vert \le \vert -3 \vert\). However \(-3 \neq 3\).

Reflexive and symmetric but not transitive

Consider \(A=\mathbb R\) and \[R = \{(x,y) \in \mathbb R^2 \, | \, \vert x – y \vert \le 1\}.\] In other word, \(x\) is \(R\)-related to \(y\) if and only if the relative distance between \(x\) and \(y\) is less than \(1\) foot. \(R\) is reflexive and symmetric but not transitive as \(\vert 1 – 0 \vert \le 1\), \(\vert 2 – 1 \vert \le 1\) but \(\vert 2 – 0 \vert > 1\).

A relation that is reflexive, antisymmetric and transitive is called a partial order. Let’s see that being reflexive, antisymmetric and transitive are independent properties.

Reflexive and transitive but not antisymmetric

We already came across such a binary relation above considering \(A=\mathbb R\) and \[R = \{(x,y) \in \mathbb R^2 \, | \, \vert x \vert \le \vert y \vert\}.\]

Reflexive and antisymmetric but not transitive

Here we take \(A = \mathbb R\) and \[R = \{(x,y) \in \mathbb R^2 \, | \, x \le y \text{ and } \vert x-y \vert \le 1\}.\] \(R\) is reflexive and antisymmetric as \(\le\) is a partial order of \(\mathbb R\). \(R\) is not transitive as \(0 R 1\) and \(1 R 2\) while \(0 R 2\) doesn’t hold.

Antisymmetric and transitive but not reflexive

We define on \(\mathbb N\) the binary relation \(R\) by: \(a R b \) if and only if \(a\) is even and divides \(b\). If \(a R b\) and \(b R a\), \(a\) and \(b\) are both even and as the divisibility relation is antisymmetric, \(R\) is also antisymmetric. For \(a,b,c \in \mathbb N\), if \(aRb\) and \(b R c\) both hold, \(a,b\) are even and \(a\) divides \(c\) by transitivity of the divisibility relation. Hence \(a Rc\) which proves that \(R\) is transitive.

However, \(R\) is not reflexive as \(3 R 3\) doesn’t hold because \(3\) is not even.

Leave a Reply