4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.