5
$\begingroup$

My lecturer omitted the proof in the lecture notes. From what I can gather, it's because equivalence classes partition always partition a set (the class can contain only that element or more and the elements in that class can only be in that one class so it acts as a partition). However, this, firstly, doesn't tell me why equivalence relations are the same thing as partitions and not equivalence classes, and to me it sounds like partitions cannot be arbitrary. From what I understood all they have to be are a collection of subsets $A_i$ forming some set $A$ such that:

  1. $A_i \ne \emptyset$
  2. $A_i \ \cap A_j = \emptyset , \ \ \ \text{if $j \ne i$}$
  3. $\bigcup _i A_i = A$

I don't see any of these rules demanding subtly there be an equivalence relation, and doing so sounds like it puts restrictions on the creation of a partition that I don't see in its definition. How are they equivalent?

$\endgroup$
  • $\begingroup$ Do you mean $A_i\cap A_j=\varnothing$ if $j\ne i$? $\endgroup$ – Franklin Pezzuti Dyer Nov 10 '18 at 17:07
  • $\begingroup$ @Frpzzd Good spot, thanks for pointing it out. $\endgroup$ – sangstar Nov 10 '18 at 17:09
  • 5
    $\begingroup$ Declare two things equivalent if they live in the same subset. That’s an equivalence relation. $\endgroup$ – Randall Nov 10 '18 at 17:09
  • $\begingroup$ @Randall Ah, that's a clever example. Can I use this to extend the general sameness of equivalence relations and partitions that I've been offered to accept however, or only if we consider the equivalence relation "if they live in the same subset"? $\endgroup$ – sangstar Nov 10 '18 at 17:11
  • $\begingroup$ They are equivalent: partitions and eq relations are the same concept via my remark. It’s a great learning exercise. $\endgroup$ – Randall Nov 10 '18 at 17:12
5
$\begingroup$

A partition and an equivalence relation are not the same thing; however, they can induce each other (as explained at the end of this answer). An equivalence relation $R$ on a set $A$ is a subset of $A\times A$ satisfying the following properties: $$(a,a)\in R\space\forall a\in A$$ $$(a,b)\in R\implies (b,a)\in R\space\forall a,b\in A$$ $$(a,b)\in R\space\text{and}\space (b,c)\in R\implies (a,c)\in R \space\forall a,b,c\in A$$ However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties: $$p_i\cap p_j=\varnothing\space\forall p_i,p_j\in 2^A\space\text{with}\space p_i\ne p_j$$ $$\bigcup_{i=1}^{|P|}p_i=A$$ We have that $R\subset A\times A$ and $P\subset 2^A$, so they're not even the same type of object. However, your professor probably meant that every equivalence relation on a set $A$ induces a partition of $A$, and vice versa.

More specifically, if $R$ is an equivalence relation on $A$, then the induced partition $P$ is $$P=\{\{b:(a,b)\in R\}:a\in A\}$$ and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by $$R=\{(a,b):\exists p_i\in P\space\text{s.t.}\space a,b\in p_i\}$$ In plain words: If $R$ is a given equivalence relation, then the induced partition $P$ partitions $A$ into all sets of elements which are equivalent to each other under $R$. If $P$ is a given partition, then the induced equivalence relation $R$ is the relation for which $x\sim y$ if and only if $x,y$ are in the same set of the partition P.

$\endgroup$
  • 1
    $\begingroup$ A bit ashamed to admit the notation looks a bit daunting to read and it's presenting as difficult to me. Is there a more wordsy explanation to this? Mainly the end of your answer addressing the induced partition and induced equivalence relation bit? $\endgroup$ – sangstar Nov 10 '18 at 17:25
  • $\begingroup$ @sangstar Sure, thanks for asking! I edited my question for you. $\endgroup$ – Franklin Pezzuti Dyer Nov 10 '18 at 17:28
  • $\begingroup$ Thanks! I think I hopefully understand now. Does my example illustrate this understanding? Let $V$ be a vector space over a field $F$ and let $W$ be a subspace of that space. If we define an equivalence relation $R_W$ on $V$ by $u \ R_W \ v$ if $u-v \in W$, then the set of elements which satisfy $u-v \in W$ for arbitrary $u, v \in V$ form a partition of $V$? $\endgroup$ – sangstar Nov 10 '18 at 17:30
  • 1
    $\begingroup$ @sangstar That's right! If you're familiar with a bit of elementary group theory, the sets in this induced partition are called the cosets of the subspace $W$. $\endgroup$ – Franklin Pezzuti Dyer Nov 10 '18 at 17:32
  • $\begingroup$ Ah, okay. Thank you! $\endgroup$ – sangstar Nov 10 '18 at 17:34
4
$\begingroup$

They are "the same thing" in the sense that given an equivalence relation there is a natural way to construct a partition, and given a partition there is a natural way to construct an equivalence relation, and these two natural ways invert one another. That's useful because whenever you encounter one of these objects you are free to reason about the other if that makes your argument easier.

You are right when you say that it is the equivalence classes of an equivalence relation that form a partition (that is in fact the natural thing to look at), not the equivalence relation itself.

The natural way to construct an equivalence relation from a partition is to define two elements to be equivalent just when they are in the same block of the partition.

$\endgroup$
  • $\begingroup$ I see. What if there is a defined equivalence relation $R$ that isn't defined as "is in the same partition as". Can we not then equate equivalence classes and partitions in this case? Just trying to make sure I understand you. $\endgroup$ – sangstar Nov 10 '18 at 17:21
  • $\begingroup$ @sangstar Every equivalent relation can be expressed as "is in the same partition as" for some partition; that is, every equivalence relation has an induced partition just as every partition has an induced equivalence relation. $\endgroup$ – Franklin Pezzuti Dyer Nov 10 '18 at 17:22
  • $\begingroup$ @Frpzzd I see. I'm afraid the notation in your answer is a bit difficult to read for my less experienced eyes. Is there a more wordy explanation for your answer? $\endgroup$ – sangstar Nov 10 '18 at 17:24
  • $\begingroup$ My answer says in words just what @Frpzzd 's answer says with notation. $\endgroup$ – Ethan Bolker Nov 10 '18 at 17:42
1
$\begingroup$

Here's a visual explanation.

enter image description here

Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).

$\endgroup$
  • $\begingroup$ I have no idea what your drawing means, but it looks pretty $\endgroup$ – étale-cohomology Nov 11 '18 at 1:02

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.