Why Reflexivity cannot be deduced by Symmetry and Transitivity?

The short answer is: quantifiers matter, they’re very important.

The question was asked me by students who were starting studying equivalence relations. They wondered: why refelxivity is needed? Can’t it be deduced by Symmetry and Transitivity?

Let’s recall the definition of equivalence relation.

Given two sets $A$ e $B$, a relation is any subset of the cartesian product $A\times B$. A relation can also be defined between elements of one set $A$: in this case the relation is a subset of the cartesian product $A\times A$ ($A^{2}$).

A relation $R$ in $A\times A$ is said to be an equivalence if it is Reflexive, Symmetric e Transitive.

Reflexivity (M): $\forall x\in A, (x,x)\in R$

Symmetry (S): $(x,y)\in R \Rightarrow (y,x)\in R$

Transitivity (T): $(x,y)\in R \wedge (y,z)\in R\Rightarrow (x,z)\in R$

The reasoning made by students was like the following: S $\Rightarrow (x,y)\in R\Rightarrow (y,x)\in R$, hence, through T, $(x,x)\in R$, which looks like reflexivity M.

Looks like… The keypoint is that neither S nor T guarentee that all the elements of A are linked through R to at least one element of A: universal quantifier “for all” ($\forall$) is missed. Universal quantifier which is instead included inside reflexivity M.

In other words, reflexivity M – exactly thanks to the universal quantifier “for all” ($\forall$) – is the only property among the three which guarentees no element of A is left outside the relation R; what S and T cannot do.

It’s useful to recall that an equivalence relation on a set A naturally builds some subsets – the so called equivalence classes – which are a partition of A. So, using the definition of partition, no element of A can be excluded by the partition, that is, all elements of A must stay in one of the partition subsets.

Now, an example. The relation defined as follows:

$R:\left \{(m,n)\in \mathbb{Z}^{2} : mn>0\right \}$

is obviously symmetric and transitive; moreover almost all the elements of $\mathbb{Z}$ are linked to themselves through $R$. By the way the relation is not reflexive since $0\in\mathbb{Z}$ is not linked to itself through $R$ (indeed it’s not linked to any other element of $\mathbb{Z}$).

Should you have any comments, doubts or questions, feel free to leave them in the comments section. Thank you. See you soon.

Leave a Reply

Your email address will not be published. Required fields are marked *