Understanding equivalence class, equivalence relation, partition

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)(xin Xland Xin S=[x]/R)}={[x]/R|xin X}$$

2) Partition

Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:

(i) $$bigcup_{Sin 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)(x exists in S land y exists in S)}$$

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

asked Nov 16 '12 at 22:22

Kristen

1161211

11

$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$
– amWhy
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$
– amWhy
Nov 16 '12 at 22:37

|
show 9 more comments

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)(xin Xland Xin S=[x]/R)}={[x]/R|xin X}$$

2) Partition

Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:

(i) $$bigcup_{Sin 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)(x exists in S land y exists in S)}$$

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

asked Nov 16 '12 at 22:22

Kristen

1161211

11

$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$
– amWhy
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$
– amWhy
Nov 16 '12 at 22:37

|
show 9 more comments

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)(xin Xland Xin S=[x]/R)}={[x]/R|xin X}$$

2) Partition

Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:

(i) $$bigcup_{Sin 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)(x exists in S land y exists in S)}$$

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

asked Nov 16 '12 at 22:22

Kristen

1161211

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)(xin Xland Xin S=[x]/R)}={[x]/R|xin X}$$

2) Partition

Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:

(i) $$bigcup_{Sin 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)(x exists in S land y exists in S)}$$

elementary-set-theory relations equivalence-relations set-partition

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

asked Nov 16 '12 at 22:22

Kristen

1161211

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

asked Nov 16 '12 at 22:22

Kristen

1161211

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

edited Dec 9 '17 at 7:53

Martin Sleziak

44.7k9117272

asked Nov 16 '12 at 22:22

Kristen

1161211

asked Nov 16 '12 at 22:22

Kristen

1161211

asked Nov 16 '12 at 22:22

Kristen

1161211

11

$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$
– amWhy
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$
– amWhy
Nov 16 '12 at 22:37

|
show 9 more comments

11

$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$
– amWhy
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$
– amWhy
Nov 16 '12 at 22:37

There is no question mark in this post.

– Asaf Karagila♦
Nov 16 '12 at 22:26

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.

– The_Sympathizer
Nov 16 '12 at 22:34

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?

– amWhy
Nov 16 '12 at 22:34

Im just having issues putting the definitions into words

– Kristen
Nov 16 '12 at 22:35

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.

– amWhy
Nov 16 '12 at 22:37

|
show 9 more comments

4 Answers
4

active

oldest

votes

$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

$A=bigcup_{Pinms P}P$, and

if $P_1,P_2inms P$ and $P_1ne P_2$, then $P_1cap 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,yin A$, $xoverset{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: $xoverset{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 $ain A$. The equivalence class of $a$ is by definition ${xin A:aoverset{ms P}sim x}$. But $aoverset{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 $ain 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 $ain A$ we set $[a]/R={xin 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,bin A$, either $aRb$, in which case $[a]/R=[b]/R$, or $anot Rb$, in which case $[a]/Rcap[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,yin A$ we have by definition $xoverset{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, $xoverset{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:

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.

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

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

$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

|
show 1 more comment

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 $ain[a]$ for every $ain 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 $ain [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 $asim b$ iff there is a $lambda$ such that $a$ and $b$ are both in $C_lambda$. Since the $C_lambda$ cover $S$, every $ain 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 xequiv 0 pmod{2}}$, Odds: $O = {y in mathbb{Z} mid xequiv 1pmod{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, $Ecap 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.

edited Nov 17 '12 at 0:17

answered Nov 16 '12 at 22:51

amWhy

$begingroup$
Kristen, are you confused by the notation? Or do you need help understanding equivalence classes?
$endgroup$
– amWhy
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$
– amWhy
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

|
show 1 more comment

1) If $R$ is an equivalence relation on $X$, then the equivalence class of an element $xin 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 xin 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.

edited Nov 16 '12 at 23:11

answered Nov 16 '12 at 22:57

Tara B

4,8601436

$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

add a comment |

The definitions of the concepts in words are

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.

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.

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

edited Nov 17 '12 at 4:45

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

$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

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f238940%2funderstanding-equivalence-class-equivalence-relation-partition%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

4 Answers
4

active

oldest

votes

4 Answers
4

active

oldest

votes

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

$A=bigcup_{Pinms P}P$, and

if $P_1,P_2inms P$ and $P_1ne P_2$, then $P_1cap P_2=varnothing$, i.e., the members of $ms P$ are pairwise disjoint.

To recapitulate:

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.

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

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

$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

|
show 1 more comment

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

$A=bigcup_{Pinms P}P$, and

if $P_1,P_2inms P$ and $P_1ne P_2$, then $P_1cap P_2=varnothing$, i.e., the members of $ms P$ are pairwise disjoint.

To recapitulate:

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.

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

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

$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

|
show 1 more comment

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

$A=bigcup_{Pinms P}P$, and

if $P_1,P_2inms P$ and $P_1ne P_2$, then $P_1cap P_2=varnothing$, i.e., the members of $ms P$ are pairwise disjoint.

To recapitulate:

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.

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

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

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

$A=bigcup_{Pinms P}P$, and

if $P_1,P_2inms P$ and $P_1ne P_2$, then $P_1cap P_2=varnothing$, i.e., the members of $ms P$ are pairwise disjoint.

To recapitulate:

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.

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

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

answered Nov 16 '12 at 22:56

Brian M. Scott

456k38507908

$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

|
show 1 more comment

$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

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

– user50229
Jan 1 '13 at 2:53

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

– Brian M. Scott
Jan 1 '13 at 4:21

@user50229, partition is dual to part. There's a nice paper by David Ellerman which discusses this relation.

– alancalvitti
Feb 22 '13 at 20:26

@alancalvitti: In exactly what sense is partition dual to part?

– Brian M. Scott
Feb 22 '13 at 20:27

@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).

– alancalvitti
Feb 22 '13 at 20:35

|
show 1 more comment

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

Fix a set $S$

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):

Evens: $E = {x in mathbb{Z}mid xequiv 0 pmod{2}}$, Odds: $O = {y in mathbb{Z} mid xequiv 1pmod{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, $Ecap O = varnothing$.

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

edited Nov 17 '12 at 0:17

answered Nov 16 '12 at 22:51

amWhy

$begingroup$
Kristen, are you confused by the notation? Or do you need help understanding equivalence classes?
$endgroup$
– amWhy
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$
– amWhy
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

|
show 1 more comment

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

Fix a set $S$

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):

Evens: $E = {x in mathbb{Z}mid xequiv 0 pmod{2}}$, Odds: $O = {y in mathbb{Z} mid xequiv 1pmod{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, $Ecap O = varnothing$.

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

edited Nov 17 '12 at 0:17

answered Nov 16 '12 at 22:51

amWhy

$begingroup$
Kristen, are you confused by the notation? Or do you need help understanding equivalence classes?
$endgroup$
– amWhy
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$
– amWhy
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

|
show 1 more comment

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

Fix a set $S$

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):

Evens: $E = {x in mathbb{Z}mid xequiv 0 pmod{2}}$, Odds: $O = {y in mathbb{Z} mid xequiv 1pmod{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, $Ecap O = varnothing$.

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

edited Nov 17 '12 at 0:17

answered Nov 16 '12 at 22:51

amWhy

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

Fix a set $S$

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):

Evens: $E = {x in mathbb{Z}mid xequiv 0 pmod{2}}$, Odds: $O = {y in mathbb{Z} mid xequiv 1pmod{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, $Ecap O = varnothing$.

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

edited Nov 17 '12 at 0:17

answered Nov 16 '12 at 22:51

amWhy

edited Nov 17 '12 at 0:17

answered Nov 16 '12 at 22:51

amWhy

answered Nov 16 '12 at 22:51

amWhy

answered Nov 16 '12 at 22:51

amWhy

$begingroup$
Kristen, are you confused by the notation? Or do you need help understanding equivalence classes?
$endgroup$
– amWhy
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$
– amWhy
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

|
show 1 more comment

$begingroup$
Kristen, are you confused by the notation? Or do you need help understanding equivalence classes?
$endgroup$
– amWhy
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$
– amWhy
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

Kristen, are you confused by the notation? Or do you need help understanding equivalence classes?

– amWhy
Nov 17 '12 at 0:31

+1 Very nice detailed answer, Amy. $~~~~~~~small{text{miss you}}$

– mrs
Aug 18 '13 at 7:30

@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,

– user12802
Apr 21 '18 at 16:02

Could you help refresh my memory, @Andrew, regarding the location of the comment I left to you?

– amWhy
Apr 21 '18 at 16:15

@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,

– user12802
Apr 21 '18 at 16:19

|
show 1 more comment

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

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

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?

edited Nov 16 '12 at 23:11

answered Nov 16 '12 at 22:57

Tara B

4,8601436

$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

add a comment |

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

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

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?

edited Nov 16 '12 at 23:11

answered Nov 16 '12 at 22:57

Tara B

4,8601436

$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

add a comment |

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

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

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?

edited Nov 16 '12 at 23:11

answered Nov 16 '12 at 22:57

Tara B

4,8601436

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

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

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?

edited Nov 16 '12 at 23:11

answered Nov 16 '12 at 22:57

Tara B

4,8601436

edited Nov 16 '12 at 23:11

answered Nov 16 '12 at 22:57

Tara B

4,8601436

answered Nov 16 '12 at 22:57

Tara B

4,8601436

answered Nov 16 '12 at 22:57

Tara B

4,8601436

$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

add a comment |

$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

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.

– Tara B
Nov 16 '12 at 23:13

(or amWhy's, now it's been expanded a bit.)

– Tara B
Nov 16 '12 at 23:35

add a comment |

The definitions of the concepts in words are

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.

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.

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

edited Nov 17 '12 at 4:45

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

$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

add a comment |

The definitions of the concepts in words are

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.

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.

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

edited Nov 17 '12 at 4:45

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

$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

add a comment |

The definitions of the concepts in words are

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.

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.

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

edited Nov 17 '12 at 4:45

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

The definitions of the concepts in words are

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.

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.

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

edited Nov 17 '12 at 4:45

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

edited Nov 17 '12 at 4:45

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

answered Nov 16 '12 at 23:05

The_Sympathizer

7,4852245

$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

add a comment |

$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

Suggestion: 'no two pairs of subsets share' --> 'no two subsets share' or 'no pair of subsets shares'.

– Tara B
Nov 16 '12 at 23:10

@Tara B: Fixed.

– The_Sympathizer
Nov 17 '12 at 4:45

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Mathematics Stack Exchange!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu