Need help solving proof involving equivalence relation
$begingroup$
Prop: Let ~ be an equivalence relation on a set A, and a, b ∈ A. If a ~ b, then [a] = [b] and if a ≁ b, then [a] ∩ [b] = ∅.
What I understand so far: an equivalence relation has to have 3 properties: reflexive, symmetric, and transitivity. Both a and b are elements of the set A and the questions asking if a and b's cardinality are equal and if a is not an equivalence relation to b, then the intersection of there cardinality must be equal to the empty set.
However I don't quite understand how to write a proof for this proposition, an elementary proof would be absolutely amazing alongside some explanation.
Thank you for all the support math.StackExchange members!
discrete-mathematics
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
$endgroup$
add a comment |
$begingroup$
Prop: Let ~ be an equivalence relation on a set A, and a, b ∈ A. If a ~ b, then [a] = [b] and if a ≁ b, then [a] ∩ [b] = ∅.
What I understand so far: an equivalence relation has to have 3 properties: reflexive, symmetric, and transitivity. Both a and b are elements of the set A and the questions asking if a and b's cardinality are equal and if a is not an equivalence relation to b, then the intersection of there cardinality must be equal to the empty set.
However I don't quite understand how to write a proof for this proposition, an elementary proof would be absolutely amazing alongside some explanation.
Thank you for all the support math.StackExchange members!
discrete-mathematics
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
$endgroup$
1
$begingroup$
It's not asking about cardinality.
$endgroup$
– Randall
Dec 16 '18 at 2:15
$begingroup$
that would explain my confusion as the cardinality of an element makes absolutely no sense. I don't quite understand what the question is asking..
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:16
1
$begingroup$
$[a]$ is the equivalence class of $a$ under the relation.
$endgroup$
– Randall
Dec 16 '18 at 2:17
$begingroup$
$[a]={ x in A | x sim a }$ ... does that help?
$endgroup$
– Bram28
Dec 16 '18 at 2:33
$begingroup$
Not really, sorry.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 3:00
add a comment |
$begingroup$
Prop: Let ~ be an equivalence relation on a set A, and a, b ∈ A. If a ~ b, then [a] = [b] and if a ≁ b, then [a] ∩ [b] = ∅.
What I understand so far: an equivalence relation has to have 3 properties: reflexive, symmetric, and transitivity. Both a and b are elements of the set A and the questions asking if a and b's cardinality are equal and if a is not an equivalence relation to b, then the intersection of there cardinality must be equal to the empty set.
However I don't quite understand how to write a proof for this proposition, an elementary proof would be absolutely amazing alongside some explanation.
Thank you for all the support math.StackExchange members!
discrete-mathematics
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
$endgroup$
Prop: Let ~ be an equivalence relation on a set A, and a, b ∈ A. If a ~ b, then [a] = [b] and if a ≁ b, then [a] ∩ [b] = ∅.
What I understand so far: an equivalence relation has to have 3 properties: reflexive, symmetric, and transitivity. Both a and b are elements of the set A and the questions asking if a and b's cardinality are equal and if a is not an equivalence relation to b, then the intersection of there cardinality must be equal to the empty set.
However I don't quite understand how to write a proof for this proposition, an elementary proof would be absolutely amazing alongside some explanation.
Thank you for all the support math.StackExchange members!
discrete-mathematics
discrete-mathematics
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 2:14
Zdravstvuyte94Zdravstvuyte94
465
465
1
$begingroup$
It's not asking about cardinality.
$endgroup$
– Randall
Dec 16 '18 at 2:15
$begingroup$
that would explain my confusion as the cardinality of an element makes absolutely no sense. I don't quite understand what the question is asking..
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:16
1
$begingroup$
$[a]$ is the equivalence class of $a$ under the relation.
$endgroup$
– Randall
Dec 16 '18 at 2:17
$begingroup$
$[a]={ x in A | x sim a }$ ... does that help?
$endgroup$
– Bram28
Dec 16 '18 at 2:33
$begingroup$
Not really, sorry.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 3:00
add a comment |
1
$begingroup$
It's not asking about cardinality.
$endgroup$
– Randall
Dec 16 '18 at 2:15
$begingroup$
that would explain my confusion as the cardinality of an element makes absolutely no sense. I don't quite understand what the question is asking..
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:16
1
$begingroup$
$[a]$ is the equivalence class of $a$ under the relation.
$endgroup$
– Randall
Dec 16 '18 at 2:17
$begingroup$
$[a]={ x in A | x sim a }$ ... does that help?
$endgroup$
– Bram28
Dec 16 '18 at 2:33
$begingroup$
Not really, sorry.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 3:00
1
1
$begingroup$
It's not asking about cardinality.
$endgroup$
– Randall
Dec 16 '18 at 2:15
$begingroup$
It's not asking about cardinality.
$endgroup$
– Randall
Dec 16 '18 at 2:15
$begingroup$
that would explain my confusion as the cardinality of an element makes absolutely no sense. I don't quite understand what the question is asking..
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:16
$begingroup$
that would explain my confusion as the cardinality of an element makes absolutely no sense. I don't quite understand what the question is asking..
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:16
1
1
$begingroup$
$[a]$ is the equivalence class of $a$ under the relation.
$endgroup$
– Randall
Dec 16 '18 at 2:17
$begingroup$
$[a]$ is the equivalence class of $a$ under the relation.
$endgroup$
– Randall
Dec 16 '18 at 2:17
$begingroup$
$[a]={ x in A | x sim a }$ ... does that help?
$endgroup$
– Bram28
Dec 16 '18 at 2:33
$begingroup$
$[a]={ x in A | x sim a }$ ... does that help?
$endgroup$
– Bram28
Dec 16 '18 at 2:33
$begingroup$
Not really, sorry.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 3:00
$begingroup$
Not really, sorry.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 3:00
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose $[a]cap[b] neq emptyset$. Then there is a $c in [a]cap[b]$. Then, by the definition of equivalence classes and intersection, $asim c land csim b$. By the transitivity of equivalence relations, $asim b$: contradiction.
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
$endgroup$
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
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%2f3042164%2fneed-help-solving-proof-involving-equivalence-relation%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
$begingroup$
Suppose $[a]cap[b] neq emptyset$. Then there is a $c in [a]cap[b]$. Then, by the definition of equivalence classes and intersection, $asim c land csim b$. By the transitivity of equivalence relations, $asim b$: contradiction.
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
$endgroup$
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
add a comment |
$begingroup$
Suppose $[a]cap[b] neq emptyset$. Then there is a $c in [a]cap[b]$. Then, by the definition of equivalence classes and intersection, $asim c land csim b$. By the transitivity of equivalence relations, $asim b$: contradiction.
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
$endgroup$
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
add a comment |
$begingroup$
Suppose $[a]cap[b] neq emptyset$. Then there is a $c in [a]cap[b]$. Then, by the definition of equivalence classes and intersection, $asim c land csim b$. By the transitivity of equivalence relations, $asim b$: contradiction.
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
$endgroup$
Suppose $[a]cap[b] neq emptyset$. Then there is a $c in [a]cap[b]$. Then, by the definition of equivalence classes and intersection, $asim c land csim b$. By the transitivity of equivalence relations, $asim b$: contradiction.
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
edited Dec 17 '18 at 0:04
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
answered Dec 16 '18 at 2:30
Lucas HenriqueLucas Henrique
1,036414
1,036414
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
add a comment |
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
I don't understand that proof, I guess equivalence classes are confusing me a bit here.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:59
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
$begingroup$
Then you need to study the definitions of each of reflexive, symmetric, and transitive as properties of relations. When you have an equivalence relation the set is divided into equivalence classes. All the elements in a class are related and no elements that are in different classes are related.
$endgroup$
– Ross Millikan
Dec 16 '18 at 3:01
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%2f3042164%2fneed-help-solving-proof-involving-equivalence-relation%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
1
$begingroup$
It's not asking about cardinality.
$endgroup$
– Randall
Dec 16 '18 at 2:15
$begingroup$
that would explain my confusion as the cardinality of an element makes absolutely no sense. I don't quite understand what the question is asking..
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 2:16
1
$begingroup$
$[a]$ is the equivalence class of $a$ under the relation.
$endgroup$
– Randall
Dec 16 '18 at 2:17
$begingroup$
$[a]={ x in A | x sim a }$ ... does that help?
$endgroup$
– Bram28
Dec 16 '18 at 2:33
$begingroup$
Not really, sorry.
$endgroup$
– Zdravstvuyte94
Dec 16 '18 at 3:00