Why are partitions and equivalence relations the same thing?
$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:
- $A_i ne emptyset$
- $A_i cap A_j = emptyset , textif $j ne i$$
- $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?
elementary-number-theory equivalence-relations set-partition
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
$endgroup$
|
show 2 more comments
$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:
- $A_i ne emptyset$
- $A_i cap A_j = emptyset , textif $j ne i$$
- $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?
elementary-number-theory equivalence-relations set-partition
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
$endgroup$
$begingroup$
Do you mean $A_icap A_j=varnothing$ if $jne i$?
$endgroup$
– Frpzzd
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
|
show 2 more comments
$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:
- $A_i ne emptyset$
- $A_i cap A_j = emptyset , textif $j ne i$$
- $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?
elementary-number-theory equivalence-relations set-partition
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
$endgroup$
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:
- $A_i ne emptyset$
- $A_i cap A_j = emptyset , textif $j ne i$$
- $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?
elementary-number-theory equivalence-relations set-partition
elementary-number-theory equivalence-relations set-partition
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
edited Nov 11 '18 at 2:46
Martin Sleziak
44.7k8117272
44.7k8117272
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
asked Nov 10 '18 at 17:06
sangstarsangstar
854214
854214
$begingroup$
Do you mean $A_icap A_j=varnothing$ if $jne i$?
$endgroup$
– Frpzzd
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
|
show 2 more comments
$begingroup$
Do you mean $A_icap A_j=varnothing$ if $jne i$?
$endgroup$
– Frpzzd
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
$begingroup$
Do you mean $A_icap A_j=varnothing$ if $jne i$?
$endgroup$
– Frpzzd
Nov 10 '18 at 17:07
$begingroup$
Do you mean $A_icap A_j=varnothing$ if $jne i$?
$endgroup$
– Frpzzd
Nov 10 '18 at 17:07
$begingroup$
@Frpzzd Good spot, thanks for pointing it out.
$endgroup$
– sangstar
Nov 10 '18 at 17:09
$begingroup$
@Frpzzd Good spot, thanks for pointing it out.
$endgroup$
– sangstar
Nov 10 '18 at 17:09
5
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$
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$
@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
$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
|
show 2 more comments
3 Answers
3
active
oldest
votes
$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 $Atimes A$ satisfying the following properties:
$$(a,a)in Rspaceforall ain A$$
$$(a,b)in Rimplies (b,a)in Rspaceforall a,bin A$$
$$(a,b)in Rspacetextandspace (b,c)in Rimplies (a,c)in R spaceforall a,b,cin A$$
However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties:
$$p_icap p_j=varnothingspaceforall p_i,p_jin 2^Aspacetextwithspace p_ine p_j$$
$$bigcup_i=1^p_i=A$$
We have that $Rsubset Atimes A$ and $Psubset 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:ain A$$
and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by
$$R=(a,b):exists p_iin Pspacetexts.t.space a,bin 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 $xsim y$ if and only if $x,y$ are in the same set of the partition P.
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
$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$
– Frpzzd
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$
– Frpzzd
Nov 10 '18 at 17:32
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
add a comment |
$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.
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
$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$
– Frpzzd
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
add a comment |
$begingroup$
Here's a visual explanation.
Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
$endgroup$
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2992845%2fwhy-are-partitions-and-equivalence-relations-the-same-thing%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 $Atimes A$ satisfying the following properties:
$$(a,a)in Rspaceforall ain A$$
$$(a,b)in Rimplies (b,a)in Rspaceforall a,bin A$$
$$(a,b)in Rspacetextandspace (b,c)in Rimplies (a,c)in R spaceforall a,b,cin A$$
However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties:
$$p_icap p_j=varnothingspaceforall p_i,p_jin 2^Aspacetextwithspace p_ine p_j$$
$$bigcup_i=1^p_i=A$$
We have that $Rsubset Atimes A$ and $Psubset 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:ain A$$
and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by
$$R=(a,b):exists p_iin Pspacetexts.t.space a,bin 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 $xsim y$ if and only if $x,y$ are in the same set of the partition P.
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
$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$
– Frpzzd
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$
– Frpzzd
Nov 10 '18 at 17:32
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
add a comment |
$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 $Atimes A$ satisfying the following properties:
$$(a,a)in Rspaceforall ain A$$
$$(a,b)in Rimplies (b,a)in Rspaceforall a,bin A$$
$$(a,b)in Rspacetextandspace (b,c)in Rimplies (a,c)in R spaceforall a,b,cin A$$
However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties:
$$p_icap p_j=varnothingspaceforall p_i,p_jin 2^Aspacetextwithspace p_ine p_j$$
$$bigcup_i=1^p_i=A$$
We have that $Rsubset Atimes A$ and $Psubset 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:ain A$$
and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by
$$R=(a,b):exists p_iin Pspacetexts.t.space a,bin 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 $xsim y$ if and only if $x,y$ are in the same set of the partition P.
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
$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$
– Frpzzd
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$
– Frpzzd
Nov 10 '18 at 17:32
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
add a comment |
$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 $Atimes A$ satisfying the following properties:
$$(a,a)in Rspaceforall ain A$$
$$(a,b)in Rimplies (b,a)in Rspaceforall a,bin A$$
$$(a,b)in Rspacetextandspace (b,c)in Rimplies (a,c)in R spaceforall a,b,cin A$$
However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties:
$$p_icap p_j=varnothingspaceforall p_i,p_jin 2^Aspacetextwithspace p_ine p_j$$
$$bigcup_i=1^p_i=A$$
We have that $Rsubset Atimes A$ and $Psubset 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:ain A$$
and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by
$$R=(a,b):exists p_iin Pspacetexts.t.space a,bin 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 $xsim y$ if and only if $x,y$ are in the same set of the partition P.
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
$endgroup$
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 $Atimes A$ satisfying the following properties:
$$(a,a)in Rspaceforall ain A$$
$$(a,b)in Rimplies (b,a)in Rspaceforall a,bin A$$
$$(a,b)in Rspacetextandspace (b,c)in Rimplies (a,c)in R spaceforall a,b,cin A$$
However, a partition $P$ of $A$ is a subset of $2^A$ satisfying the following two properties:
$$p_icap p_j=varnothingspaceforall p_i,p_jin 2^Aspacetextwithspace p_ine p_j$$
$$bigcup_i=1^p_i=A$$
We have that $Rsubset Atimes A$ and $Psubset 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:ain A$$
and if $P$ is a partition of $A$, then the induced equivalence relation $R$ is defined by
$$R=(a,b):exists p_iin Pspacetexts.t.space a,bin 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 $xsim y$ if and only if $x,y$ are in the same set of the partition P.
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
edited Nov 10 '18 at 17:28
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
answered Nov 10 '18 at 17:14
FrpzzdFrpzzd
22.4k840108
22.4k840108
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$
– Frpzzd
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$
– Frpzzd
Nov 10 '18 at 17:32
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
add a comment |
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$
– Frpzzd
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$
– Frpzzd
Nov 10 '18 at 17:32
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
1
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$
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$
– Frpzzd
Nov 10 '18 at 17:28
$begingroup$
@sangstar Sure, thanks for asking! I edited my question for you.
$endgroup$
– Frpzzd
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
$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
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$
– Frpzzd
Nov 10 '18 at 17:32
$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$
– Frpzzd
Nov 10 '18 at 17:32
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
$begingroup$
Ah, okay. Thank you!
$endgroup$
– sangstar
Nov 10 '18 at 17:34
add a comment |
$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.
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
$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$
– Frpzzd
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
add a comment |
$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.
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
$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$
– Frpzzd
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
add a comment |
$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.
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
$endgroup$
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.
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
answered Nov 10 '18 at 17:12
Ethan BolkerEthan Bolker
42.1k548111
42.1k548111
$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$
– Frpzzd
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
add a comment |
$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$
– Frpzzd
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
$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$
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$
– Frpzzd
Nov 10 '18 at 17:22
$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$
– Frpzzd
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$
@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
$begingroup$
My answer says in words just what @Frpzzd 's answer says with notation.
$endgroup$
– Ethan Bolker
Nov 10 '18 at 17:42
add a comment |
$begingroup$
Here's a visual explanation.
Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
$endgroup$
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
add a comment |
$begingroup$
Here's a visual explanation.
Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
$endgroup$
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
add a comment |
$begingroup$
Here's a visual explanation.
Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
$endgroup$
Here's a visual explanation.
Note that the nodes in the first three panels should have had edges to themselves as well (from reflexivity of equivalence relations).
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
answered Nov 10 '18 at 21:17
rlmsrlms
2741317
2741317
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
add a comment |
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
$begingroup$
I have no idea what your drawing means, but it looks pretty
$endgroup$
– étale-cohomology
Nov 11 '18 at 1:02
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2992845%2fwhy-are-partitions-and-equivalence-relations-the-same-thing%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Do you mean $A_icap A_j=varnothing$ if $jne i$?
$endgroup$
– Frpzzd
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