Need Help With Elementary Proof
$begingroup$
Prop: For sets A and B, say A ~ B iff there exists a bijection from A to B. Then ~ is an equivalence relation on sets.
I understand that an equivalence relation holds the properties of reflexive, symmetric, and transitive. I am also aware of their definitions, however, I am struggling to write a proof for this proposition.
I would assume we can suppose there is a bijection between A and B, as this would imply there is a bijection between the two. This would also mean that the two sets have equal cardinality but from this point on I am completely lost, the direction of the proof seems very unclear.
A hidden answer (written proof) would be great with some visible guidance or hints so enhance my understanding.
Thank you.
discrete-mathematics
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
$endgroup$
add a comment |
$begingroup$
Prop: For sets A and B, say A ~ B iff there exists a bijection from A to B. Then ~ is an equivalence relation on sets.
I understand that an equivalence relation holds the properties of reflexive, symmetric, and transitive. I am also aware of their definitions, however, I am struggling to write a proof for this proposition.
I would assume we can suppose there is a bijection between A and B, as this would imply there is a bijection between the two. This would also mean that the two sets have equal cardinality but from this point on I am completely lost, the direction of the proof seems very unclear.
A hidden answer (written proof) would be great with some visible guidance or hints so enhance my understanding.
Thank you.
discrete-mathematics
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
$endgroup$
$begingroup$
Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.)
$endgroup$
– Ethan Bolker
Dec 16 '18 at 22:57
$begingroup$
@EthanBolker That's actually the strategy needed for the symmetric condition.
$endgroup$
– J.G.
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself.
$endgroup$
– Eevee Trainer
Dec 16 '18 at 22:58
1
$begingroup$
@J.G. Yes thanks fixed.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 23:00
add a comment |
$begingroup$
Prop: For sets A and B, say A ~ B iff there exists a bijection from A to B. Then ~ is an equivalence relation on sets.
I understand that an equivalence relation holds the properties of reflexive, symmetric, and transitive. I am also aware of their definitions, however, I am struggling to write a proof for this proposition.
I would assume we can suppose there is a bijection between A and B, as this would imply there is a bijection between the two. This would also mean that the two sets have equal cardinality but from this point on I am completely lost, the direction of the proof seems very unclear.
A hidden answer (written proof) would be great with some visible guidance or hints so enhance my understanding.
Thank you.
discrete-mathematics
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
$endgroup$
Prop: For sets A and B, say A ~ B iff there exists a bijection from A to B. Then ~ is an equivalence relation on sets.
I understand that an equivalence relation holds the properties of reflexive, symmetric, and transitive. I am also aware of their definitions, however, I am struggling to write a proof for this proposition.
I would assume we can suppose there is a bijection between A and B, as this would imply there is a bijection between the two. This would also mean that the two sets have equal cardinality but from this point on I am completely lost, the direction of the proof seems very unclear.
A hidden answer (written proof) would be great with some visible guidance or hints so enhance my understanding.
Thank you.
discrete-mathematics
discrete-mathematics
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
asked Dec 16 '18 at 22:51
Zdravstvuyte94Zdravstvuyte94
465
465
$begingroup$
Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.)
$endgroup$
– Ethan Bolker
Dec 16 '18 at 22:57
$begingroup$
@EthanBolker That's actually the strategy needed for the symmetric condition.
$endgroup$
– J.G.
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself.
$endgroup$
– Eevee Trainer
Dec 16 '18 at 22:58
1
$begingroup$
@J.G. Yes thanks fixed.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 23:00
add a comment |
$begingroup$
Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.)
$endgroup$
– Ethan Bolker
Dec 16 '18 at 22:57
$begingroup$
@EthanBolker That's actually the strategy needed for the symmetric condition.
$endgroup$
– J.G.
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself.
$endgroup$
– Eevee Trainer
Dec 16 '18 at 22:58
1
$begingroup$
@J.G. Yes thanks fixed.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 23:00
$begingroup$
Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.)
$endgroup$
– Ethan Bolker
Dec 16 '18 at 22:57
$begingroup$
Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.)
$endgroup$
– Ethan Bolker
Dec 16 '18 at 22:57
$begingroup$
@EthanBolker That's actually the strategy needed for the symmetric condition.
$endgroup$
– J.G.
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker That's actually the strategy needed for the symmetric condition.
$endgroup$
– J.G.
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself.
$endgroup$
– Eevee Trainer
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself.
$endgroup$
– Eevee Trainer
Dec 16 '18 at 22:58
1
1
$begingroup$
@J.G. Yes thanks fixed.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 23:00
$begingroup$
@J.G. Yes thanks fixed.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 23:00
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Since $f(x)=x$ bijects $A$ to $A$, $sim$ is reflexive. Write a similar proof $sim$ is symmetric, using the fact bijections have inverses; write a similar proof $sim$ is transitive, using a composition of bijections.
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
$endgroup$
add a comment |
$begingroup$
We only need to show three properties:
Reflexiveness:
Does there exist for ANY set $A$ a bijective function between the set and itself?
If so, we can say that $A sim A$.
Hint, what if there were a function that assigns $f(a)=a$ for all $a in A$, how do we call this function?
Symmetry:
If $A sim B$, there exists a bijection between these two sets. Any bijective function is also invertible, so does there exist a bijection between $B$ and $A$? if so, we can say that $B sim A$
Transivity:
Finally, if $Asim B$ and $B sim C$, we know there are bijective functions $f$ and $g$, what do we know about the composition of two bijective functions?
Good luck!
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
$begingroup$
Showing that these properties hold is a straightforward application of the definitions, with some elementary properties of bijections. So, I suspect what you are having trouble with is formulating a proper proof. I will show reflexivity as an example.
We want to show that for any set $A$, we have $A sim A$. Because of how we defined $sim$, this means that for any set $A$, we need to show that there exists a bijection $f : A rightarrow A$. How do we show this? We must construct such a function explicitly. Since we know nothing of the contents of $A$, there is really only one choice: the identity function.
Let $f : A rightarrow A$ be the function such that $f(a) = a$ for every $a in A$. We must check that $f$ is bijective. First, $f$ is injective: if $f(a) = f(b)$, then $a = f(a) = f(b) = b$, so $a = b$. Next, $f$ is surjective: if $a in A$, then there exists an element $x in A$ such that $f(x) = a$: namely, $x = a$.
So, we have shown that for any set $A$, we can construct a bijection $f : A rightarrow A$, which shows that $A sim A$. This shows the reflexivity of $sim$. Others have provided hints for the other two properties.
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
$endgroup$
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%2f3043296%2fneed-help-with-elementary-proof%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$
Since $f(x)=x$ bijects $A$ to $A$, $sim$ is reflexive. Write a similar proof $sim$ is symmetric, using the fact bijections have inverses; write a similar proof $sim$ is transitive, using a composition of bijections.
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
$endgroup$
add a comment |
$begingroup$
Since $f(x)=x$ bijects $A$ to $A$, $sim$ is reflexive. Write a similar proof $sim$ is symmetric, using the fact bijections have inverses; write a similar proof $sim$ is transitive, using a composition of bijections.
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
$endgroup$
add a comment |
$begingroup$
Since $f(x)=x$ bijects $A$ to $A$, $sim$ is reflexive. Write a similar proof $sim$ is symmetric, using the fact bijections have inverses; write a similar proof $sim$ is transitive, using a composition of bijections.
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
$endgroup$
Since $f(x)=x$ bijects $A$ to $A$, $sim$ is reflexive. Write a similar proof $sim$ is symmetric, using the fact bijections have inverses; write a similar proof $sim$ is transitive, using a composition of bijections.
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
answered Dec 16 '18 at 22:59
J.G.J.G.
30.1k23148
30.1k23148
add a comment |
add a comment |
$begingroup$
We only need to show three properties:
Reflexiveness:
Does there exist for ANY set $A$ a bijective function between the set and itself?
If so, we can say that $A sim A$.
Hint, what if there were a function that assigns $f(a)=a$ for all $a in A$, how do we call this function?
Symmetry:
If $A sim B$, there exists a bijection between these two sets. Any bijective function is also invertible, so does there exist a bijection between $B$ and $A$? if so, we can say that $B sim A$
Transivity:
Finally, if $Asim B$ and $B sim C$, we know there are bijective functions $f$ and $g$, what do we know about the composition of two bijective functions?
Good luck!
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
$begingroup$
We only need to show three properties:
Reflexiveness:
Does there exist for ANY set $A$ a bijective function between the set and itself?
If so, we can say that $A sim A$.
Hint, what if there were a function that assigns $f(a)=a$ for all $a in A$, how do we call this function?
Symmetry:
If $A sim B$, there exists a bijection between these two sets. Any bijective function is also invertible, so does there exist a bijection between $B$ and $A$? if so, we can say that $B sim A$
Transivity:
Finally, if $Asim B$ and $B sim C$, we know there are bijective functions $f$ and $g$, what do we know about the composition of two bijective functions?
Good luck!
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
$begingroup$
We only need to show three properties:
Reflexiveness:
Does there exist for ANY set $A$ a bijective function between the set and itself?
If so, we can say that $A sim A$.
Hint, what if there were a function that assigns $f(a)=a$ for all $a in A$, how do we call this function?
Symmetry:
If $A sim B$, there exists a bijection between these two sets. Any bijective function is also invertible, so does there exist a bijection between $B$ and $A$? if so, we can say that $B sim A$
Transivity:
Finally, if $Asim B$ and $B sim C$, we know there are bijective functions $f$ and $g$, what do we know about the composition of two bijective functions?
Good luck!
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
$endgroup$
We only need to show three properties:
Reflexiveness:
Does there exist for ANY set $A$ a bijective function between the set and itself?
If so, we can say that $A sim A$.
Hint, what if there were a function that assigns $f(a)=a$ for all $a in A$, how do we call this function?
Symmetry:
If $A sim B$, there exists a bijection between these two sets. Any bijective function is also invertible, so does there exist a bijection between $B$ and $A$? if so, we can say that $B sim A$
Transivity:
Finally, if $Asim B$ and $B sim C$, we know there are bijective functions $f$ and $g$, what do we know about the composition of two bijective functions?
Good luck!
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
answered Dec 16 '18 at 23:04
Wesley StrikWesley Strik
2,172424
2,172424
add a comment |
add a comment |
$begingroup$
Showing that these properties hold is a straightforward application of the definitions, with some elementary properties of bijections. So, I suspect what you are having trouble with is formulating a proper proof. I will show reflexivity as an example.
We want to show that for any set $A$, we have $A sim A$. Because of how we defined $sim$, this means that for any set $A$, we need to show that there exists a bijection $f : A rightarrow A$. How do we show this? We must construct such a function explicitly. Since we know nothing of the contents of $A$, there is really only one choice: the identity function.
Let $f : A rightarrow A$ be the function such that $f(a) = a$ for every $a in A$. We must check that $f$ is bijective. First, $f$ is injective: if $f(a) = f(b)$, then $a = f(a) = f(b) = b$, so $a = b$. Next, $f$ is surjective: if $a in A$, then there exists an element $x in A$ such that $f(x) = a$: namely, $x = a$.
So, we have shown that for any set $A$, we can construct a bijection $f : A rightarrow A$, which shows that $A sim A$. This shows the reflexivity of $sim$. Others have provided hints for the other two properties.
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
$endgroup$
add a comment |
$begingroup$
Showing that these properties hold is a straightforward application of the definitions, with some elementary properties of bijections. So, I suspect what you are having trouble with is formulating a proper proof. I will show reflexivity as an example.
We want to show that for any set $A$, we have $A sim A$. Because of how we defined $sim$, this means that for any set $A$, we need to show that there exists a bijection $f : A rightarrow A$. How do we show this? We must construct such a function explicitly. Since we know nothing of the contents of $A$, there is really only one choice: the identity function.
Let $f : A rightarrow A$ be the function such that $f(a) = a$ for every $a in A$. We must check that $f$ is bijective. First, $f$ is injective: if $f(a) = f(b)$, then $a = f(a) = f(b) = b$, so $a = b$. Next, $f$ is surjective: if $a in A$, then there exists an element $x in A$ such that $f(x) = a$: namely, $x = a$.
So, we have shown that for any set $A$, we can construct a bijection $f : A rightarrow A$, which shows that $A sim A$. This shows the reflexivity of $sim$. Others have provided hints for the other two properties.
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
$endgroup$
add a comment |
$begingroup$
Showing that these properties hold is a straightforward application of the definitions, with some elementary properties of bijections. So, I suspect what you are having trouble with is formulating a proper proof. I will show reflexivity as an example.
We want to show that for any set $A$, we have $A sim A$. Because of how we defined $sim$, this means that for any set $A$, we need to show that there exists a bijection $f : A rightarrow A$. How do we show this? We must construct such a function explicitly. Since we know nothing of the contents of $A$, there is really only one choice: the identity function.
Let $f : A rightarrow A$ be the function such that $f(a) = a$ for every $a in A$. We must check that $f$ is bijective. First, $f$ is injective: if $f(a) = f(b)$, then $a = f(a) = f(b) = b$, so $a = b$. Next, $f$ is surjective: if $a in A$, then there exists an element $x in A$ such that $f(x) = a$: namely, $x = a$.
So, we have shown that for any set $A$, we can construct a bijection $f : A rightarrow A$, which shows that $A sim A$. This shows the reflexivity of $sim$. Others have provided hints for the other two properties.
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
$endgroup$
Showing that these properties hold is a straightforward application of the definitions, with some elementary properties of bijections. So, I suspect what you are having trouble with is formulating a proper proof. I will show reflexivity as an example.
We want to show that for any set $A$, we have $A sim A$. Because of how we defined $sim$, this means that for any set $A$, we need to show that there exists a bijection $f : A rightarrow A$. How do we show this? We must construct such a function explicitly. Since we know nothing of the contents of $A$, there is really only one choice: the identity function.
Let $f : A rightarrow A$ be the function such that $f(a) = a$ for every $a in A$. We must check that $f$ is bijective. First, $f$ is injective: if $f(a) = f(b)$, then $a = f(a) = f(b) = b$, so $a = b$. Next, $f$ is surjective: if $a in A$, then there exists an element $x in A$ such that $f(x) = a$: namely, $x = a$.
So, we have shown that for any set $A$, we can construct a bijection $f : A rightarrow A$, which shows that $A sim A$. This shows the reflexivity of $sim$. Others have provided hints for the other two properties.
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
answered Dec 16 '18 at 23:05
SamboSambo
2,3112532
2,3112532
add a comment |
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%2f3043296%2fneed-help-with-elementary-proof%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$
Hint: To prove symmetry, you must show there's a bijection from $B$ to $A$ when you know there is one from $A$ to $B$. Can you figure out what is should be? Rewrite the other two conditions (reflexive,, transitive) in terms of the existence of bijection, and find one. (I'm pretty sure this question is an exact duplicate of another on this site.)
$endgroup$
– Ethan Bolker
Dec 16 '18 at 22:57
$begingroup$
@EthanBolker That's actually the strategy needed for the symmetric condition.
$endgroup$
– J.G.
Dec 16 '18 at 22:58
$begingroup$
@EthanBolker Isn't that symmetry you stated in the opening of your post? Reflexivity would be essentially showing each set is bijective with itself.
$endgroup$
– Eevee Trainer
Dec 16 '18 at 22:58
1
$begingroup$
@J.G. Yes thanks fixed.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 23:00