0

Suppose that $X$ is some set and $\sim$ is an equivalence relation on $X$ and $X\neq \varnothing$. For each $x\in X$ define $$R(x):=\{y\in X: y\sim x\}$$ an equivalence class of $x$. One can show that if $R(x_1)\cap R(x_2)\neq \varnothing$ then $R(x_1)=R(x_2).$

I would like to understand why these equivalence classes form the partition of $X$. So I need to show that there exist $\{P_i\}_{i\in I}$ such that $P_i\cap P_j=\varnothing$ and $X=\cup_{i\in I}P_i$, right?

Intuitively, I know that they form partition but cannot prove it rigorously. I was wondering how to specify these partitioning sets explicitly.

RFZ
  • 16,814

2 Answers2

1

The set of partitions is just $V = \{R(x) \mid x \in X\}$.

More formally, let $P_v = v$ for all $v \in V$. Note that $P_v \subseteq X$ for all $v \in V$. I claim that $\{P_v\}_{v \in V}$ is a partition.

There are three conditions that must be checked. First, we must show that $\forall v \in V \exists x \in P_v$. To show this, consider some $v \in V$. Write $v = R(x)$ for some $x$. Then $x \in v = P_v$.

The second condition is that $\bigcup\limits_{v \in V} P_v = X$. To show this, suppose we have some $x \in X$. Then $x \in R(x)$. Let $R(x) = v$. Then $x \in v = P_v$. Therefore, $x \in \bigcup\limits_{v \in V} P_v$. Thus, we see that $\bigcup\limits_{v \in V} P_v = X$.

Finally, the third condition is that for all $v_1, v_2 \in V$, if $\exists x \in P_{v_1} \cap P_{v_2}$, then $v_1 = v_2$. Suppose there is some $x \in P_{v_1} \cap P_{v_2}$. Then we see that $R(x) = v_1$. And we see that $R(x) = v_2$. Therefore, $v_1 = v_2$.

Mark Saving
  • 31,855
  • Let me ask you some questions: you wrote that $V$ is the set of partitions. But it does not look correct because if $x_1\sim x_2$ then $R(x_1)=R(x_2)$ and each of $R(x_1)$ and $R(x_2)$ belongs to $V$. I guess you need to change it somehow – RFZ Oct 01 '21 at 23:40
  • @PlayGame No. $V$ is indeed the set of partitions. You are correct that if $x_1 \sim x_2$ then $R(x_1) = R(x_2)$, but this is irrelevant. The key here is to look at $V$ as a set which is indexed by itself, not indexed by $x \in X$. – Mark Saving Oct 01 '21 at 23:41
  • In other words, some sets in $V$ can intersect each other and hence are equal. This set may contain repeating elements, right? – RFZ Oct 01 '21 at 23:42
  • @PlayGame No. Two elements in $V$ can have a nonempty intersection if and only if they are the same element. I'm not sure what you mean by "This set may contain repeating elements". – Mark Saving Oct 01 '21 at 23:43
  • The elements of $V$ are equivalence classes, right? If we pick two equivalence classes and they have nonempty intersection then they are equal, right? Suppose these equivalence classes are $R(x_1)$ and $R(x_2)$, i.e. $R(x_1)=R(x_2)\in V$. – RFZ Oct 01 '21 at 23:45
  • So did you get what I am asking about? – RFZ Oct 01 '21 at 23:49
  • @PlayGame I have rewritten the answer to be more explicit. – Mark Saving Oct 01 '21 at 23:54
  • You claim that ${P_v: v\in V}$ forms a partition of $X$, right? but those sets should be pairwise disjoint, right? I still cannot get the point. – RFZ Oct 02 '21 at 00:04
  • We see that $X=\cup_{v\in V}P_v$, i.e. if we take the union of all sets $P_v$ we'll get the set $X$. in order to show that it is a partition we need to show that they are pairwise disjoint, right? – RFZ Oct 02 '21 at 00:22
  • 1
    @PlayGame ${P_v}{v \in V}$ are pairwise disjoint. This is exactly what I have shown. ${P_v}{v \in V}$ being pairwise disjoint means, by definition, that if $P_v \cap P_u$ has an element, then $v = u$. This is what I proved. – Mark Saving Oct 02 '21 at 20:43
  • 1
    or in other words if $v\neq u$ then $P_v\cap P_u=\varnothing$, right? – RFZ Oct 03 '21 at 17:32
  • @PlayGame Correct. – Mark Saving Oct 03 '21 at 17:38
  • Thank you so much! I accepted your answer as the best one. I guess you finally resolved my issue) Thank you so much) – RFZ Oct 03 '21 at 17:40
  • Let me ask you a question please: what is the reason that you introduced the set $P_v$ which is indexed with $v\in V$? I cannot get it – RFZ Oct 03 '21 at 17:55
  • Because in your edition you considered partition as the set ${R(x):x\in X}$ – RFZ Oct 03 '21 at 18:01
  • Can you explain my question, please? – RFZ Oct 04 '21 at 15:43
  • 1
    @PlayGame I introduced the indexed set because you defined a partition as an indexed set ${P_i}_{i \in I}$. So I wanted to produce an indexed set that satisfied the definition of a partition. – Mark Saving Oct 04 '21 at 16:08
1

I'll try to keep my explanation as simple as possible, bear with me.

  1. Each element of $X$ belongs to some equivalence class of $X$.

This is pretty straightforward. Since $\sim$ is reflexive, every $x \in X$ satisfies $x \sim x$ and so $x \in R(x)$.

  1. Any two equivalence classes of $X$ are either disjoint or identical.

Which means for any $x_1$ and $x_2$ in $X$, either $R(x_1)= R(x_2)$ or $ R(x_1) \cap R(x_2)= \varnothing$.

In simple words, the equivalence classes of any two elements are either the same or share no common elements at all. This is because if $x \in R(x_1)$ and $x \in R(x_2)$ then $x \sim x_1$ and $x \sim x_2$ and by symmetry and transitivity of $\sim$, we have $x_1 \sim x$ and $x \sim x_2 \Rightarrow x_1 \sim x_2$.

  1. Union of all equivalence classes is $X$.

From 1, we know that $ x \in R(x), \ \forall x \in X$, so $\{x \} \subseteq R(x)$. Thus $\bigcup\limits_{x \in X} \{x \} = X \subseteq \bigcup\limits_{x \in X} R(x) \subseteq X$ since $R(x) \subseteq X, \ \forall x \in X$.

Hence,we have that $\bigcup\limits_{x \in X} R(x) = X$.

Ibrahim
  • 455
  • Yeah, the union of all $R(x)$ over $x\in X$ gives us the whole set $X$. In order for them to be partition we require that elements of ${R(x):x\in X}$ are disjoint. But you said that for some $x_1\sim x_2$ they could be identical i.e. $R(x_1)=R(x_2)$. and you see that $R(x_1)$ actually intersects $R(x_2)$. – RFZ Oct 02 '21 at 00:27
  • @PlayGame I see your confusion. You're interpreting $R(x_1)$ and $R(x_2)$ as two different sets. They're not. Think of $R(x_1)= R(x_2)$ this way, they are only but alternative names of the same set. So you would not include them twice while constructing your partition ${ P_i}{i \in I}$. Or simply put, there is only one $i$ that represents the set that go by the names $R(x_1)$ or $R(x_2)$ or $R(y), y \sim x_1$ in ${P_i}{i \in I}$. – Ibrahim Oct 02 '21 at 00:39
  • Could you explain your last comment in a more detailed way, please? – RFZ Oct 02 '21 at 00:45
  • 1
    @PlayGame Sure. Here's another crack at it. Take an arbitrary set $S= { a, b , c, d }$. Now if I were to tell you $b = d$, how many elements do you suppose $S$ contains? $4$? Nope, only $3$, that's because $b$ and $d$ are one and the same, you wouldn't count it twice. To maintain the analogy, let $ { R(x) : x \in X }=S $, and let $b= R(x_1), d= R(x_2) \in S $. Now $b$ and $d$ are one and the same set because $R(x_1)=R(x_2)$. So it is redundant to include them twice or more than once in $S$. – Ibrahim Oct 02 '21 at 01:03