Partition inducing equivalence

38 Views Asked by At

In NPTEL Lecture 23 on Discrete Mathematics, the professor proves that every partition induces equivalence. But is it necessary that the elements in the partition blocks are necessarily reflexive symmetric and transitive? Can't they be separate components of a digraph not satisfying these properties? Because in that case also they remain disjoint.

1

There are 1 best solutions below

0
On

Somehow you're confused about what has been proved. If $\sim$ is the equivalence relation induced by a partition, then for any block $B$ of the partition, every $x,y\in B$ are $\sim$-equivalent ($x\sim y$), by definition; and for any other block $B'$, nothing in $B$ is equivalent to anything in $B'$. The relation $\sim$ is still reflexive, symmetric and transitive on each block.

With your example of a digraph, the connected components partition the nodes, and the corresponding equivalence relation is $x\sim y \iff$ $x,y$ are in the same connected component.