# What does “relation induced by a partition” mean?

The question is: What is the equivalence relation R, induced by the partition P of A? (A, P are given)

I don't get what "induced by" means.

There is a particular natural connection between equivalence relations and partitions. Each partition corresponds to an equivalence relation, and each equivalence relation corresponds to a partition. Going back and forth along this correspondence will get you back where you started.

The correspondence is this: Given a partition, each element is related to each element in the same part, and nothing else. The other way: Given an equivalence relation, a part of the partition is given by a maximal set of elements all related to one another.

This correspondence is what they mean by "the equivalence relation induced by the partition".

I suspect that they use the word "induce" because the correspondence is based on a concrete construction to get from one to the other. Not all such natural correspondences are like that.

The partition $$P$$ is a set $$\{A_\lambda\mid\lambda\in\Lambda\}$$ of subsets of $$A$$. The relation $$R$$ is the one defined by$$a\mathrel Ra'\iff\text{for some }\lambda\in\Lambda,\ a,a'\in A_j.$$

• Except that a partition need not be finite. – freakish Jan 20 at 8:04
• I've edited my answer. Thank you. – José Carlos Santos Jan 20 at 8:28

That would mean that you think of the partition $$P$$ as giving the equivalence classes of the relation $$R$$, so $$aRb$$ if and only if there is an $$S \in P$$ such that $$a, b \in S$$.

In this way, equivalence relations and partitions are kind of interchangeable - any equivalence relation corresponds exactly to a partition of the set, which is the equivalence classes.

Let $$P$$ be a partitioning of $$X$$. Then it induces an equivalence relation $$\sim_P$$ such that $$x\sim_P y$$ if and only if $$x,y$$ belong to the same element of $$P$$.

Conversly if $$\sim$$ is an equivalence relation then it induces a partitioning $$P_\sim:=\{[x]_\sim\ |\ x\in X\}$$ where $$[x]_\sim=\{y\in X\ |\ y\sim x\}$$.

The nice property of these operations is that they are inverses of each other:

$$P_{\sim_P}=P$$ $$\sim_{P_\sim}=\sim$$

In other words partitionings and equivalence relations are the same thing.