Prove that $sim$ is an equivalence relation on the set $A$
Let $A$ be a nonempty set and $C$ is a partition of $A$.
A relation $sim$ is defined as:
$$For x, y in A, xsim y if and only if there exists U in C such that x in U and y in U .$$
I have to prove that $sim$ is an equivalence relation on the set $A$. Earlier in this problem, I had to prove that $sim$ was an equivalence relation on $A = { a, b, c, d, e}$ (it was part a of this 4 part problem). In this case, the set $A$ is being generalized. I'm confused on how to prove this without having specific "examples" that I could use like I did in part a of this question.
equivalence-relations set-partition
asked Nov 30 at 0:43
Claire
556
add a comment |
Let $A$ be a nonempty set and $C$ is a partition of $A$.
A relation $sim$ is defined as:
$$For x, y in A, xsim y if and only if there exists U in C such that x in U and y in U .$$
I have to prove that $sim$ is an equivalence relation on the set $A$. Earlier in this problem, I had to prove that $sim$ was an equivalence relation on $A = { a, b, c, d, e}$ (it was part a of this 4 part problem). In this case, the set $A$ is being generalized. I'm confused on how to prove this without having specific "examples" that I could use like I did in part a of this question.
equivalence-relations set-partition
asked Nov 30 at 0:43
Claire
556
Your reference to "earlier in this problem" is confusing. Are you sure it's the same $A$ and relation here as there? Your question is straightforward if you omit the last sentence: check the properties you need for an equivalence relation, edit the question to tell us where you are stuck.
– Ethan Bolker
Nov 30 at 0:48
I meant earlier in the problem that I was assigned for homework, this part that I'm asking a question about is for part c of the 4 part question. The last sentence is referring to what I had to do in part a of the question. The difference between part a and part c is that the set is being generalized in part c.
– Claire
Nov 30 at 0:50
2
You will need to know the definition of a partition. The properties of an equivalence relation should follow almost immediately. For example, $sim$ will be reflexive because for any $xin A$ you will have by definition of partitions some $Uin C$ such that $xin U$. It is clear that given that $xin U$ it follows that simultaneously $color{red}{x}in U$ and $color{blue}{x}in U$ so $color{red}{x}sim color{blue}{x}$. (Color is of course not necessary here, but it feels silly to just repeat $xin U$ four times in a row and have it be clear why I would do so).
– JMoravitz
Nov 30 at 0:51
add a comment |
Let $A$ be a nonempty set and $C$ is a partition of $A$.
A relation $sim$ is defined as:
$$For x, y in A, xsim y if and only if there exists U in C such that x in U and y in U .$$
I have to prove that $sim$ is an equivalence relation on the set $A$. Earlier in this problem, I had to prove that $sim$ was an equivalence relation on $A = { a, b, c, d, e}$ (it was part a of this 4 part problem). In this case, the set $A$ is being generalized. I'm confused on how to prove this without having specific "examples" that I could use like I did in part a of this question.
equivalence-relations set-partition
asked Nov 30 at 0:43
Claire
556
Let $A$ be a nonempty set and $C$ is a partition of $A$.
A relation $sim$ is defined as:
$$For x, y in A, xsim y if and only if there exists U in C such that x in U and y in U .$$
I have to prove that $sim$ is an equivalence relation on the set $A$. Earlier in this problem, I had to prove that $sim$ was an equivalence relation on $A = { a, b, c, d, e}$ (it was part a of this 4 part problem). In this case, the set $A$ is being generalized. I'm confused on how to prove this without having specific "examples" that I could use like I did in part a of this question.
equivalence-relations set-partition
equivalence-relations set-partition
asked Nov 30 at 0:43
Claire
556
asked Nov 30 at 0:43
Claire
556
edited Nov 30 at 0:52
asked Nov 30 at 0:43
Claire
556
asked Nov 30 at 0:43
Claire
556
asked Nov 30 at 0:43
Claire
556
556
Your reference to "earlier in this problem" is confusing. Are you sure it's the same $A$ and relation here as there? Your question is straightforward if you omit the last sentence: check the properties you need for an equivalence relation, edit the question to tell us where you are stuck.
– Ethan Bolker
Nov 30 at 0:48
I meant earlier in the problem that I was assigned for homework, this part that I'm asking a question about is for part c of the 4 part question. The last sentence is referring to what I had to do in part a of the question. The difference between part a and part c is that the set is being generalized in part c.
– Claire
Nov 30 at 0:50
2
You will need to know the definition of a partition. The properties of an equivalence relation should follow almost immediately. For example, $sim$ will be reflexive because for any $xin A$ you will have by definition of partitions some $Uin C$ such that $xin U$. It is clear that given that $xin U$ it follows that simultaneously $color{red}{x}in U$ and $color{blue}{x}in U$ so $color{red}{x}sim color{blue}{x}$. (Color is of course not necessary here, but it feels silly to just repeat $xin U$ four times in a row and have it be clear why I would do so).
– JMoravitz
Nov 30 at 0:51
add a comment |
Your reference to "earlier in this problem" is confusing. Are you sure it's the same $A$ and relation here as there? Your question is straightforward if you omit the last sentence: check the properties you need for an equivalence relation, edit the question to tell us where you are stuck.
– Ethan Bolker
Nov 30 at 0:48
I meant earlier in the problem that I was assigned for homework, this part that I'm asking a question about is for part c of the 4 part question. The last sentence is referring to what I had to do in part a of the question. The difference between part a and part c is that the set is being generalized in part c.
– Claire
Nov 30 at 0:50
2
You will need to know the definition of a partition. The properties of an equivalence relation should follow almost immediately. For example, $sim$ will be reflexive because for any $xin A$ you will have by definition of partitions some $Uin C$ such that $xin U$. It is clear that given that $xin U$ it follows that simultaneously $color{red}{x}in U$ and $color{blue}{x}in U$ so $color{red}{x}sim color{blue}{x}$. (Color is of course not necessary here, but it feels silly to just repeat $xin U$ four times in a row and have it be clear why I would do so).
– JMoravitz
Nov 30 at 0:51
Your reference to "earlier in this problem" is confusing. Are you sure it's the same $A$ and relation here as there? Your question is straightforward if you omit the last sentence: check the properties you need for an equivalence relation, edit the question to tell us where you are stuck.
– Ethan Bolker
Nov 30 at 0:48
Your reference to "earlier in this problem" is confusing. Are you sure it's the same $A$ and relation here as there? Your question is straightforward if you omit the last sentence: check the properties you need for an equivalence relation, edit the question to tell us where you are stuck.
– Ethan Bolker
Nov 30 at 0:48
I meant earlier in the problem that I was assigned for homework, this part that I'm asking a question about is for part c of the 4 part question. The last sentence is referring to what I had to do in part a of the question. The difference between part a and part c is that the set is being generalized in part c.
– Claire
Nov 30 at 0:50
I meant earlier in the problem that I was assigned for homework, this part that I'm asking a question about is for part c of the 4 part question. The last sentence is referring to what I had to do in part a of the question. The difference between part a and part c is that the set is being generalized in part c.
– Claire
Nov 30 at 0:50
2
2
You will need to know the definition of a partition. The properties of an equivalence relation should follow almost immediately. For example, $sim$ will be reflexive because for any $xin A$ you will have by definition of partitions some $Uin C$ such that $xin U$. It is clear that given that $xin U$ it follows that simultaneously $color{red}{x}in U$ and $color{blue}{x}in U$ so $color{red}{x}sim color{blue}{x}$. (Color is of course not necessary here, but it feels silly to just repeat $xin U$ four times in a row and have it be clear why I would do so).
– JMoravitz
Nov 30 at 0:51
You will need to know the definition of a partition. The properties of an equivalence relation should follow almost immediately. For example, $sim$ will be reflexive because for any $xin A$ you will have by definition of partitions some $Uin C$ such that $xin U$. It is clear that given that $xin U$ it follows that simultaneously $color{red}{x}in U$ and $color{blue}{x}in U$ so $color{red}{x}sim color{blue}{x}$. (Color is of course not necessary here, but it feels silly to just repeat $xin U$ four times in a row and have it be clear why I would do so).
– JMoravitz
Nov 30 at 0:51
add a comment |
1 Answer
1
active
oldest
votes
This follows directly by definition of partition. A partition of a set $A$, $C$ is a class of sets $U_alpha$ so that every element of a $A$ is in some $U_alpha$ and the $U_alpha$ are disjoint.
Reflexive says:
There exists a $U$ so that $ain U$ and $a in U$.
By definition of partition there is some $U$ so that for each $ain A$ there is a $U$ so that $ain U$. (and therefore $a in U$).
Symmetric says:
If there exists a $U$ so that $a,b in U$ then there exists a $U$ so that $b,a in U$.
(Don't need to say anything more.)
Transitive says:
If there exists a $U$ so that $a,b in U$ and and $V$ so that $b,cin V$ then there is a $W$ so that $a,c in W$.
By definition of partition, the partitioning sets are disjoint. So if $bin U$ and $b in V$ then $U= V$. So if there exists a $U$ so that $a,b in U$ and if there exists a $V$ so that $b,c in V$ then $U=V$ and $a,b,c in V$.
answered Nov 30 at 1:19
fleablood
68.1k22684
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
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%2f3019461%2fprove-that-sim-is-an-equivalence-relation-on-the-set-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
This follows directly by definition of partition. A partition of a set $A$, $C$ is a class of sets $U_alpha$ so that every element of a $A$ is in some $U_alpha$ and the $U_alpha$ are disjoint.
Reflexive says:
There exists a $U$ so that $ain U$ and $a in U$.
By definition of partition there is some $U$ so that for each $ain A$ there is a $U$ so that $ain U$. (and therefore $a in U$).
Symmetric says:
If there exists a $U$ so that $a,b in U$ then there exists a $U$ so that $b,a in U$.
(Don't need to say anything more.)
Transitive says:
If there exists a $U$ so that $a,b in U$ and and $V$ so that $b,cin V$ then there is a $W$ so that $a,c in W$.
By definition of partition, the partitioning sets are disjoint. So if $bin U$ and $b in V$ then $U= V$. So if there exists a $U$ so that $a,b in U$ and if there exists a $V$ so that $b,c in V$ then $U=V$ and $a,b,c in V$.
answered Nov 30 at 1:19
fleablood
68.1k22684
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
add a comment |
This follows directly by definition of partition. A partition of a set $A$, $C$ is a class of sets $U_alpha$ so that every element of a $A$ is in some $U_alpha$ and the $U_alpha$ are disjoint.
Reflexive says:
There exists a $U$ so that $ain U$ and $a in U$.
By definition of partition there is some $U$ so that for each $ain A$ there is a $U$ so that $ain U$. (and therefore $a in U$).
Symmetric says:
If there exists a $U$ so that $a,b in U$ then there exists a $U$ so that $b,a in U$.
(Don't need to say anything more.)
Transitive says:
If there exists a $U$ so that $a,b in U$ and and $V$ so that $b,cin V$ then there is a $W$ so that $a,c in W$.
By definition of partition, the partitioning sets are disjoint. So if $bin U$ and $b in V$ then $U= V$. So if there exists a $U$ so that $a,b in U$ and if there exists a $V$ so that $b,c in V$ then $U=V$ and $a,b,c in V$.
answered Nov 30 at 1:19
fleablood
68.1k22684
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
add a comment |
This follows directly by definition of partition. A partition of a set $A$, $C$ is a class of sets $U_alpha$ so that every element of a $A$ is in some $U_alpha$ and the $U_alpha$ are disjoint.
Reflexive says:
There exists a $U$ so that $ain U$ and $a in U$.
By definition of partition there is some $U$ so that for each $ain A$ there is a $U$ so that $ain U$. (and therefore $a in U$).
Symmetric says:
If there exists a $U$ so that $a,b in U$ then there exists a $U$ so that $b,a in U$.
(Don't need to say anything more.)
Transitive says:
If there exists a $U$ so that $a,b in U$ and and $V$ so that $b,cin V$ then there is a $W$ so that $a,c in W$.
By definition of partition, the partitioning sets are disjoint. So if $bin U$ and $b in V$ then $U= V$. So if there exists a $U$ so that $a,b in U$ and if there exists a $V$ so that $b,c in V$ then $U=V$ and $a,b,c in V$.
answered Nov 30 at 1:19
fleablood
68.1k22684
This follows directly by definition of partition. A partition of a set $A$, $C$ is a class of sets $U_alpha$ so that every element of a $A$ is in some $U_alpha$ and the $U_alpha$ are disjoint.
Reflexive says:
There exists a $U$ so that $ain U$ and $a in U$.
By definition of partition there is some $U$ so that for each $ain A$ there is a $U$ so that $ain U$. (and therefore $a in U$).
Symmetric says:
If there exists a $U$ so that $a,b in U$ then there exists a $U$ so that $b,a in U$.
(Don't need to say anything more.)
Transitive says:
If there exists a $U$ so that $a,b in U$ and and $V$ so that $b,cin V$ then there is a $W$ so that $a,c in W$.
By definition of partition, the partitioning sets are disjoint. So if $bin U$ and $b in V$ then $U= V$. So if there exists a $U$ so that $a,b in U$ and if there exists a $V$ so that $b,c in V$ then $U=V$ and $a,b,c in V$.
answered Nov 30 at 1:19
fleablood
68.1k22684
answered Nov 30 at 1:19
fleablood
68.1k22684
answered Nov 30 at 1:19
fleablood
68.1k22684
answered Nov 30 at 1:19
fleablood
68.1k22684
68.1k22684
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
add a comment |
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
To the proposer: The definition of a partition C of a set A requires that for all $ain A$ there is EXACTLY ONE $Uin C$ such that $ain U.$
– DanielWainfleet
Nov 30 at 1:44
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3019461%2fprove-that-sim-is-an-equivalence-relation-on-the-set-a%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
Your reference to "earlier in this problem" is confusing. Are you sure it's the same $A$ and relation here as there? Your question is straightforward if you omit the last sentence: check the properties you need for an equivalence relation, edit the question to tell us where you are stuck.
– Ethan Bolker
Nov 30 at 0:48
I meant earlier in the problem that I was assigned for homework, this part that I'm asking a question about is for part c of the 4 part question. The last sentence is referring to what I had to do in part a of the question. The difference between part a and part c is that the set is being generalized in part c.
– Claire
Nov 30 at 0:50
2
You will need to know the definition of a partition. The properties of an equivalence relation should follow almost immediately. For example, $sim$ will be reflexive because for any $xin A$ you will have by definition of partitions some $Uin C$ such that $xin U$. It is clear that given that $xin U$ it follows that simultaneously $color{red}{x}in U$ and $color{blue}{x}in U$ so $color{red}{x}sim color{blue}{x}$. (Color is of course not necessary here, but it feels silly to just repeat $xin U$ four times in a row and have it be clear why I would do so).
– JMoravitz
Nov 30 at 0:51