I'm having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions.

1) The collection of equivalence classes w.r.t. $R$

Def: Let $R$ be an equivalence relation in a set $X$. The collection of equivalence classes w.r.t. $R$ is the set: $$[X]/R =\{S|(\exists x)(x\in X\land S=[x]/R)\}=\{[x]/R|x\in X\}$$

2) Partition

Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:
(i) $$\bigcup_{S\in\ C} S=X.$$ (ii) $$\forall S \in C, S \neq \varnothing$$ (iii) $$\forall S, S' \in C, S' \neq S \Rightarrow S \cap S' = \varnothing$$

3) Relation induced by

Def: Let $C$ be a partition of $X$. The relation induced by $C$, denoted by $X/C$, is a relation in $X$ such that $$X/C = \{(x,y) | (\exists S \in C)(\exists x \in S \land \exists y \in S)\}$$

  • 12
    $\begingroup$ There is no question mark in this post. $\endgroup$ – Asaf Karagila Nov 16 '12 at 22:26
  • $\begingroup$ I'm sorry, but some of the definition formulas are all wonky and don't seem to make sense to me (namely, the formulas for $[X]/R$ and $X/C$.). They seem to contain mistakes. $\endgroup$ – The_Sympathizer Nov 16 '12 at 22:34
  • $\begingroup$ Are you asking for clarification of the definitions, i.e., help to put into words what the definitions mean? Are you asking for what the definitions mean, intuitively? $\endgroup$ – Namaste Nov 16 '12 at 22:34
  • 1
    $\begingroup$ Im just having issues putting the definitions into words $\endgroup$ – Kristen Nov 16 '12 at 22:35
  • 1
    $\begingroup$ Do you understand my comment above? Note: Every partition of a set determines an equivalence relation on that set, and every equivalence class induces a partition of the set into equivalence classes. $\endgroup$ – Namaste Nov 16 '12 at 22:37

$\newcommand{\ms}{\mathscr}$Equivalence relations and partitions are very intimately related; indeed, it’s fair to say that they are two different ways of looking at basically the same thing.

Start with a set $A$. A partition $\ms P$ of $A$ is just a way of chopping $A$ up into pieces. More formally, it’s a collection of subsets of $A$ with a very simple property: every element of $A$ belongs to exactly one of the sets in $\ms P$. This is often expressed in a slightly more roundabout fashion: a collection $\ms P$ of non-empty subsets of $A$ is a partition of $A$ if

  1. $A=\bigcup_{P\in\ms P}P$, and
  2. if $P_1,P_2\in\ms P$ and $P_1\ne P_2$, then $P_1\cap P_2=\varnothing$, i.e., the members of $\ms P$ are pairwise disjoint.

The first of these conditions says that each element of $A$ belongs to at least one member of $\ms P$, and the second says that no element of $A$ belongs to more than one member of $\ms P$; put the two together, and you get my original definition.

We can use the partition $\ms P$ to define an associated relation $\overset{\ms P}\sim$ on $A$: for any $x,y\in A$, $x\overset{\ms P}\sim y$ if and only if $x$ and $y$ are in the same piece of the partition $\ms P$. For instance, if $A$ is a set of people, we can partition them according to their ages: the $20$-year-olds are one piece of the partition, the $50$-year-olds are another, and so on. The associated relation is simply has the same age as: $x\overset{\ms P}\sim y$ if and only if $x$ and $y$ are the same age. It’s easy to see in this case that $\overset{\ms P}\sim$ is an equivalence relation $-$ reflexive, symmetric, and transitive $-$ and it’s not hard to prove that this is always the case: if $\ms P$ is a partition of a set $A$, then $\overset{\ms P}\sim$ is an equivalence relation on $A$.

Now what are the equivalence classes of this relation $\overset{\ms P}\sim$? Fix $a\in A$. The equivalence class of $a$ is by definition $\{x\in A:a\overset{\ms P}\sim x\}$. But $a\overset{\ms P}\sim x$ just means that $a$ and $x$ are in the same piece of the partition $\ms P$, so $x$ is in the equivalence class of $a$ if and only if is in the same piece as $a$. In other words, the equivalence class of $a$ is the piece of $\ms P$ that contains $a$. And this is true for every $a\in A$, so the equivalence classes of the relation $\overset{\ms P}\sim$ are exactly the pieces of the partition $\ms P$, the ‘chunks’ into which it divides $A$.

Now set that aside for a moment, and let $R$ be an equivalence relation on $A$. For each $a\in A$ we set $[a]/R=\{x\in A:aRx\}$; this is the equivalence class of $a$, the set of things to which $a$ is related by $R$. It’s a subset of $A$. One of the first things that you prove about equivalence classes is that for any $a,b\in A$, either $aRb$, in which case $[a]/R=[b]/R$, or $a\not Rb$, in which case $[a]/R\cap[b]/R=\varnothing$: any two equivalence classes are either the same set or completely disjoint from each other. In other words, the equivalence classes chop up $A$ into pairwise disjoint pieces, and every element $a$ of $A$ belongs to exactly one of these pieces, namely $[a]/R$.

But this is exactly what it means to say that $A/R$, the collection of all of these equivalence classes, is a partition of $A$: each element of $A$ belongs to exactly one of the sets in the collection $A/R$. Just as a partition $\ms P$ of $A$ gives rise to an associated equivalence relation $\overset{\ms P}\sim$ on $A$, an equivalence relation $R$ on $A$ gives rise to an associated partition $A/R$ of $A$. What happens if we start with the partition $A/R$ and construct its associated equivalence relation $\overset{A/R}\sim$ on $A$? For any $x,y\in A$ we have by definition $x\overset{A/R}\sim y$ if and only if $x$ and $y$ are in the same piece of $A/R$. But the pieces of $A/R$ are the $R$-equivalence classes, so $x$ and $y$ are in the same piece of the partition $A/R$ if and only if $[x]/R=[y]/R$, i.e., if and only if $xRy$. That is, $x\overset{A/R}\sim y$ if and only if $xRy$, and $\overset{A/R}\sim$ and $R$ are exactly the same relation on $A$.

To recapitulate:

  1. Each partition $\ms P$ of $A$ induces an associated equivalence relation $\overset{\ms P}\sim$ on $A$, and each equivalence relation $R$ on $A$ induces an associated partition $A/R$ of $A$ into equivalences classes.

  2. These conversion operations from partition to equivalence relation and vice versa are inverses. If you start with a partition $\ms P$ of $A$, construct the equivalence relation $\overset{\ms P}\sim$ on $A$, and then construct the associated partition $A/\overset{\ms P}\sim$ of $A$, you’re back where you started: $A/\overset{\ms P}\sim=\ms P$. Similarly, if you start with an equivalence relation $R$ on $A$, construct the associated partition $A/R$ of $A$, and then build from that partition its associated equivalence relation $\overset{A/R}\sim$, you get the original relation $R$ back: $\overset{A/R}\sim=R$.

  • $\begingroup$ How would we phrase the relationship between partitions and equivalence relations, would we say they were 'dual' concepts or something like that? I know this type of thing occurs elsewhere in mathematics where there are two aspects of what is really the same 'thing'. $\endgroup$ – user50229 Jan 1 '13 at 2:53
  • $\begingroup$ @SJGreen: I can’t think of any sense in which they could be called dual notions. They’re simply two different aspects of a single phenomenon. The third aspect is the function that sends each element of $A$ to its equivalence class. The relationship amongst these three aspects is the subject of the first isomorphism theorem in its general setting. $\endgroup$ – Brian M. Scott Jan 1 '13 at 4:21
  • $\begingroup$ @user50229, partition is dual to part. There's a nice paper by David Ellerman which discusses this relation. $\endgroup$ – alancalvitti Feb 22 '13 at 20:26
  • $\begingroup$ @alancalvitti: In exactly what sense is partition dual to part? $\endgroup$ – Brian M. Scott Feb 22 '13 at 20:27
  • $\begingroup$ @BrianM.Scott, Lawvere & Rosebrugh SFM write "the dual notion (obtained by reversing the arrows) of "part" is the notion of partition (of A), ie, any surjection $p:A \twoheadrightarrow X$. (Since parts correspond to injections). $\endgroup$ – alancalvitti Feb 22 '13 at 20:35

Why? How do we know how these definitions are related?

Fix a set $S$

Consider an equivalence relation $\sim$ on $S$. Consider the equivalence classes $[a]=\{ x \in S : x \sim a \}$. By definition these are subsets of $S$. Their union is $S$ because by reflexivity $a\in[a]$ for every $a\in S$. Finally, they are disjoint because if $x \in [a]$ and $x \in [b]$ then $x \sim a$ and so $a \sim x$, by symmetry. But then $a \sim b$ by transitivity and so $a\in [b]$. Every $y \in [a]$ is also in $[b]$ again by transitivity. This means that $[a]\subseteq [b]$. Swapping $a$ and $b$, we conclude $[a]=[b]$. All this means that the equivalence classes form a partition of $S$.

Conversely, given a partition of $S$ in subsets $C_\lambda$, define an equivalence relation in $S$ by $a\sim b$ iff there is a $\lambda$ such that $a$ and $b$ are both in $C_\lambda$. Since the $C_\lambda$ cover $S$, every $a\in S$ is in one of those and so $\sim$ is reflexive. By definition, $\sim$ is symmetric. Since the $C_\lambda$ are disjoint, $\sim$ is transitive.

Note: Every partition of a set determines an equivalence relation on that set, and for every equivalence relation, the equivalence classes corresponding to that relation form a partition of the set.

To try to put into words the relationship between a partition on a set, and the equivalence relation determined by that partition (or vice versa):

Think of simple examples of an equivalence relation on a set X, and its corresponding equivalence classes (say, $\equiv \pmod 2$ on the set of integers). What are the corresponding equivalence classes? There are two: the set of even integers, and the set of odd integers.

Evens: $E = \{x \in \mathbb{Z}\mid x\equiv 0 \pmod{2}\}$, Odds: $O = \{y \in \mathbb{Z} \mid x\equiv 1\pmod{2}\}$

Is the union of the two equivalence classes equal to the set of integers? (yes). That is, $E \cup O = \mathbb{Z}$.

Is any integer in more than one of those classes? (no). That is, $E\cap O = \varnothing$.

So we have two equivalence classes whose union is the set of integers, and whose intersection is empty. Hence, we have a partition on $\mathbb{Z}$ into two sets: the set of all even integers, and the set of all odd integers.

By definition every element in a given equivalence class is related to every other element in that class, and not to any element belonging to a different equivalence class. In the example I give above, all even numbers are related (they are even i.e., $\equiv 0 \pmod{2}$), all odd numbers are related (they are all odd, i.e., $\equiv 1 \pmod{2}$), but no integer is both even and odd.

The collection of all the equivalence classes is a partition of $X$. Every $x \in X$ belongs to one and only one equivalence class.

For example, the second definition is telling you that the union of all the equivalence classes of $X$ IS $X$ (put differently, every element of X is contained in an equivalence class) and that if any two equivalence classes are not equal, then they are disjoint: their intersection is the empty set. So every element of $X$ is in one and only one equivalence class.

  • $\begingroup$ Kristen, are you confused by the notation? Or do you need help understanding equivalence classes? $\endgroup$ – Namaste Nov 17 '12 at 0:31
  • $\begingroup$ +1 Very nice detailed answer, Amy. $~~~~~~~\small{\text{miss you}}$ $\endgroup$ – mrs Aug 18 '13 at 7:30
  • $\begingroup$ @amWhy I haven't come across any of your typically great answers in a while. So I checked out your bio for an update. I do appreciate your comment, but perhaps you would also consider my (perhaps unique) circumstances. I'm 73, no math education, and passionately took up math seven years ago. I would be totally lost without this site and would be without this fulfilling part of my life. With kind regards, $\endgroup$ – user12802 Apr 21 '18 at 16:02
  • $\begingroup$ Could you help refresh my memory, @Andrew, regarding the location of the comment I left to you? $\endgroup$ – Namaste Apr 21 '18 at 16:15
  • $\begingroup$ @amWhy Sorry for being misleading, it is the remark in your bio regarding being a hw service. You are right in that is a significant aspect of what goes on here, but I think it's much more as your own illuminating answers demonstrate. Again, regards, $\endgroup$ – user12802 Apr 21 '18 at 16:19

1) If $R$ is an equivalence relation on $X$, then the equivalence class of an element $x\in X$ with respect to $R$ is the set of all elements of $X$ which are equivalent to $x$ under $R$.

The definition you have written for the set of all equivalence classes looks very strange. It surely shouldn't start with $\exists X$, since $X$ is the specific set you want to take equivalence classes in. I would just write

$$X/R = \{ [x]/R \mid x\in X \},$$ where $[x]/R$ denotes the equivalence class of $x$ with respect to $R$.

2) A partition of a set $X$ is just a collection of non-empty subsets of $X$ which are pairwise disjoint (i.e. non-intersecting) and whose union is the whole of $X$. For example, $\{ \{1,3\}, \{2,4\} \}$ is a partition of $\{1,2,3,4\}$, but $\{ \{1,2\}, \{2,3,4\} \}$ and $\{ \{1,2\}, \{2,3\} \}$ are not.

As people have mentioned in the comments, the collections equivalence classes of $X$ under an equivalence relation form a partition of $X$. Do you see why?

3) The equivalence relation generated by a partition $P$ of $X$ is simply the relation where we declare two elements of $X$ to be related if and only if they are in the same set in $P$. It's easy to check that the definition of a partition guarantees that this really is an equivalence relation.

  • $\begingroup$ I started writing this before any answers had been submitted. I guess you'd be best off reading mike4ty4's answer for the 'short answer' and Brian's answer for more detailed explanation. But I guess I'll leave this here anyway since I bothered writing it. $\endgroup$ – Tara B Nov 16 '12 at 23:13
  • $\begingroup$ (or amWhy's, now it's been expanded a bit.) $\endgroup$ – Tara B Nov 16 '12 at 23:35

The definitions of the concepts in words are

  1. The equivalence classes of an equivalence relation are subsets of the set on which the equivalence relation is defined, such that two elements are in the same equivalence class if and only if they are related by the equivalence relation.

  2. A partition of a set is a collection of subsets of the set, whose union is the whole set, and such that no two subsets share any elements in common, and none of which are the empty set.

  3. The relation induced by a partition is the relation given by "the two objects are related if they lie in the same cell of the partition" (where a "cell" is one of the subsets of the partitioned set that make up the partition.).

  • $\begingroup$ Suggestion: 'no two pairs of subsets share' --> 'no two subsets share' or 'no pair of subsets shares'. $\endgroup$ – Tara B Nov 16 '12 at 23:10
  • $\begingroup$ @Tara B: Fixed. $\endgroup$ – The_Sympathizer Nov 17 '12 at 4:45

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.