Proof about sets and their cardinality
0
$begingroup$
Let A,B be finite sets. Assume size(A)=size(B) and A$subseteq$B then A=B.
Proof: Since size(A)=size(B), then there exists a one to one correspondence between the two sets. Assume that A$neq$B, that means that $exists$ b$in$B such that f(a)$neq$b that means that the function is not surjective, which is a contradiction.
Is this proof correct? Furthermore, is there another way to prove it? Am I correct to say that the same proof works for countable sets?
elementary-set-theory logic
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
$endgroup$
|
show 8 more comments
0
$begingroup$
Let A,B be finite sets. Assume size(A)=size(B) and A$subseteq$B then A=B.
Proof: Since size(A)=size(B), then there exists a one to one correspondence between the two sets. Assume that A$neq$B, that means that $exists$ b$in$B such that f(a)$neq$b that means that the function is not surjective, which is a contradiction.
Is this proof correct? Furthermore, is there another way to prove it? Am I correct to say that the same proof works for countable sets?
elementary-set-theory logic
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
$endgroup$
$begingroup$
The statement is simply wrong for countable sets which are not finite. For example $mathbb{N}subseteqmathbb{Z}$ and they have the same cardinality. But they are not equal.
$endgroup$
– Mark
Jan 9 at 21:42
$begingroup$
Oh thanks so much!. That was helpful. Out of curiosity, am I correct to say that my proof is correct for finite sets?
$endgroup$
– mathsssislife
Jan 9 at 21:43
$begingroup$
It is fine if you really know that it is true that one to one function between two finite sets of the same size is surjective. This is not something absolutely trivial.
$endgroup$
– Mark
Jan 9 at 21:44
$begingroup$
I was mainly thinking of what it means for two sets to have the same size (cardinality). By definition, two sets have the same size if there exists a bijective map between them (one to one correspondence). Hence if I assume A$neq$B then that means $exists$ b$in$B such that f(a)$neq$b which means that the function is not surjective, hence a contradiction? Can two finite sets have the size but not be bijective?
$endgroup$
– mathsssislife
Jan 9 at 21:50
$begingroup$
@mathsssislife I like your proof. :)
$endgroup$
– irchans
Jan 9 at 21:52
|
show 8 more comments
0
0
0
$begingroup$
Let A,B be finite sets. Assume size(A)=size(B) and A$subseteq$B then A=B.
Proof: Since size(A)=size(B), then there exists a one to one correspondence between the two sets. Assume that A$neq$B, that means that $exists$ b$in$B such that f(a)$neq$b that means that the function is not surjective, which is a contradiction.
Is this proof correct? Furthermore, is there another way to prove it? Am I correct to say that the same proof works for countable sets?
elementary-set-theory logic
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
$endgroup$
Let A,B be finite sets. Assume size(A)=size(B) and A$subseteq$B then A=B.
Proof: Since size(A)=size(B), then there exists a one to one correspondence between the two sets. Assume that A$neq$B, that means that $exists$ b$in$B such that f(a)$neq$b that means that the function is not surjective, which is a contradiction.
Is this proof correct? Furthermore, is there another way to prove it? Am I correct to say that the same proof works for countable sets?
elementary-set-theory logic
elementary-set-theory logic
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
edited Jan 9 at 23:39
Andrés E. Caicedo
65.1k8158247
65.1k8158247
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
asked Jan 9 at 21:37
mathsssislifemathsssislife
326
326
$begingroup$
The statement is simply wrong for countable sets which are not finite. For example $mathbb{N}subseteqmathbb{Z}$ and they have the same cardinality. But they are not equal.
$endgroup$
– Mark
Jan 9 at 21:42
$begingroup$
Oh thanks so much!. That was helpful. Out of curiosity, am I correct to say that my proof is correct for finite sets?
$endgroup$
– mathsssislife
Jan 9 at 21:43
$begingroup$
It is fine if you really know that it is true that one to one function between two finite sets of the same size is surjective. This is not something absolutely trivial.
$endgroup$
– Mark
Jan 9 at 21:44
$begingroup$
I was mainly thinking of what it means for two sets to have the same size (cardinality). By definition, two sets have the same size if there exists a bijective map between them (one to one correspondence). Hence if I assume A$neq$B then that means $exists$ b$in$B such that f(a)$neq$b which means that the function is not surjective, hence a contradiction? Can two finite sets have the size but not be bijective?
$endgroup$
– mathsssislife
Jan 9 at 21:50
$begingroup$
@mathsssislife I like your proof. :)
$endgroup$
– irchans
Jan 9 at 21:52
|
show 8 more comments
$begingroup$
The statement is simply wrong for countable sets which are not finite. For example $mathbb{N}subseteqmathbb{Z}$ and they have the same cardinality. But they are not equal.
$endgroup$
– Mark
Jan 9 at 21:42
$begingroup$
Oh thanks so much!. That was helpful. Out of curiosity, am I correct to say that my proof is correct for finite sets?
$endgroup$
– mathsssislife
Jan 9 at 21:43
$begingroup$
It is fine if you really know that it is true that one to one function between two finite sets of the same size is surjective. This is not something absolutely trivial.
$endgroup$
– Mark
Jan 9 at 21:44
$begingroup$
I was mainly thinking of what it means for two sets to have the same size (cardinality). By definition, two sets have the same size if there exists a bijective map between them (one to one correspondence). Hence if I assume A$neq$B then that means $exists$ b$in$B such that f(a)$neq$b which means that the function is not surjective, hence a contradiction? Can two finite sets have the size but not be bijective?
$endgroup$
– mathsssislife
Jan 9 at 21:50
$begingroup$
@mathsssislife I like your proof. :)
$endgroup$
– irchans
Jan 9 at 21:52
$begingroup$
The statement is simply wrong for countable sets which are not finite. For example $mathbb{N}subseteqmathbb{Z}$ and they have the same cardinality. But they are not equal.
$endgroup$
– Mark
Jan 9 at 21:42
$begingroup$
The statement is simply wrong for countable sets which are not finite. For example $mathbb{N}subseteqmathbb{Z}$ and they have the same cardinality. But they are not equal.
$endgroup$
– Mark
Jan 9 at 21:42
$begingroup$
Oh thanks so much!. That was helpful. Out of curiosity, am I correct to say that my proof is correct for finite sets?
$endgroup$
– mathsssislife
Jan 9 at 21:43
$begingroup$
Oh thanks so much!. That was helpful. Out of curiosity, am I correct to say that my proof is correct for finite sets?
$endgroup$
– mathsssislife
Jan 9 at 21:43
$begingroup$
It is fine if you really know that it is true that one to one function between two finite sets of the same size is surjective. This is not something absolutely trivial.
$endgroup$
– Mark
Jan 9 at 21:44
$begingroup$
It is fine if you really know that it is true that one to one function between two finite sets of the same size is surjective. This is not something absolutely trivial.
$endgroup$
– Mark
Jan 9 at 21:44
$begingroup$
I was mainly thinking of what it means for two sets to have the same size (cardinality). By definition, two sets have the same size if there exists a bijective map between them (one to one correspondence). Hence if I assume A$neq$B then that means $exists$ b$in$B such that f(a)$neq$b which means that the function is not surjective, hence a contradiction? Can two finite sets have the size but not be bijective?
$endgroup$
– mathsssislife
Jan 9 at 21:50
$begingroup$
I was mainly thinking of what it means for two sets to have the same size (cardinality). By definition, two sets have the same size if there exists a bijective map between them (one to one correspondence). Hence if I assume A$neq$B then that means $exists$ b$in$B such that f(a)$neq$b which means that the function is not surjective, hence a contradiction? Can two finite sets have the size but not be bijective?
$endgroup$
– mathsssislife
Jan 9 at 21:50
$begingroup$
@mathsssislife I like your proof. :)
$endgroup$
– irchans
Jan 9 at 21:52
$begingroup$
@mathsssislife I like your proof. :)
$endgroup$
– irchans
Jan 9 at 21:52
|
show 8 more comments
1 Answer
1
active
oldest
votes
0
$begingroup$
You don't need a one-to-one correspondence, you can just do the following.
Suppose $|A|=|B|$ and $Asubseteq B$. Assume that $Aneq B$. Then there exists $bin B$ such that $bnotin A$. But every element of $A$ is in $B$, which implies that $|A|leq |B|-1$, so $|A|<|B|$, a contradiction.
answered Jan 9 at 21:47
DaveDave
8,76711033
$endgroup$
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
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%2f3067977%2fproof-about-sets-and-their-cardinality%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
0
$begingroup$
You don't need a one-to-one correspondence, you can just do the following.
Suppose $|A|=|B|$ and $Asubseteq B$. Assume that $Aneq B$. Then there exists $bin B$ such that $bnotin A$. But every element of $A$ is in $B$, which implies that $|A|leq |B|-1$, so $|A|<|B|$, a contradiction.
answered Jan 9 at 21:47
DaveDave
8,76711033
$endgroup$
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
|
show 3 more comments
0
$begingroup$
You don't need a one-to-one correspondence, you can just do the following.
Suppose $|A|=|B|$ and $Asubseteq B$. Assume that $Aneq B$. Then there exists $bin B$ such that $bnotin A$. But every element of $A$ is in $B$, which implies that $|A|leq |B|-1$, so $|A|<|B|$, a contradiction.
answered Jan 9 at 21:47
DaveDave
8,76711033
$endgroup$
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
|
show 3 more comments
0
0
0
$begingroup$
You don't need a one-to-one correspondence, you can just do the following.
Suppose $|A|=|B|$ and $Asubseteq B$. Assume that $Aneq B$. Then there exists $bin B$ such that $bnotin A$. But every element of $A$ is in $B$, which implies that $|A|leq |B|-1$, so $|A|<|B|$, a contradiction.
answered Jan 9 at 21:47
DaveDave
8,76711033
$endgroup$
You don't need a one-to-one correspondence, you can just do the following.
Suppose $|A|=|B|$ and $Asubseteq B$. Assume that $Aneq B$. Then there exists $bin B$ such that $bnotin A$. But every element of $A$ is in $B$, which implies that $|A|leq |B|-1$, so $|A|<|B|$, a contradiction.
answered Jan 9 at 21:47
DaveDave
8,76711033
answered Jan 9 at 21:47
DaveDave
8,76711033
answered Jan 9 at 21:47
DaveDave
8,76711033
answered Jan 9 at 21:47
DaveDave
8,76711033
8,76711033
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
|
show 3 more comments
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
That was really helpful! Thanks!
$endgroup$
– mathsssislife
Jan 9 at 22:00
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
But do you think my proof is correct?
$endgroup$
– mathsssislife
Jan 9 at 22:08
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
It's a bit sloppy. For instance: you don't explicitly say what $f$ is; and you say that because $Aneq B$ there must exist $b$ which is not in the image of $f$ but you don't really explain why this is the case. If you amend these things I think your proof is good.
$endgroup$
– Dave
Jan 9 at 22:12
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
How would I say what f is (other than it is a bijective map) if i'm just talking about two arbitrary sets that have the same cardinality and one is a subset of another? No extra information is given, so i'm not sure what to say.
$endgroup$
– mathsssislife
Jan 9 at 22:14
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
$begingroup$
It's fine that you use the fact that finite sets of the same size have a bijection between them, I'm just saying that you never actually said that that is what $f$ is. So you should say "...then there exists a one-to-one correspondence between the two sets, call it $f$."
$endgroup$
– Dave
Jan 9 at 22:17
|
show 3 more comments
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
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%2f3067977%2fproof-about-sets-and-their-cardinality%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$
The statement is simply wrong for countable sets which are not finite. For example $mathbb{N}subseteqmathbb{Z}$ and they have the same cardinality. But they are not equal.
$endgroup$
– Mark
Jan 9 at 21:42
$begingroup$
Oh thanks so much!. That was helpful. Out of curiosity, am I correct to say that my proof is correct for finite sets?
$endgroup$
– mathsssislife
Jan 9 at 21:43
$begingroup$
It is fine if you really know that it is true that one to one function between two finite sets of the same size is surjective. This is not something absolutely trivial.
$endgroup$
– Mark
Jan 9 at 21:44
$begingroup$
I was mainly thinking of what it means for two sets to have the same size (cardinality). By definition, two sets have the same size if there exists a bijective map between them (one to one correspondence). Hence if I assume A$neq$B then that means $exists$ b$in$B such that f(a)$neq$b which means that the function is not surjective, hence a contradiction? Can two finite sets have the size but not be bijective?
$endgroup$
– mathsssislife
Jan 9 at 21:50
$begingroup$
@mathsssislife I like your proof. :)
$endgroup$
– irchans
Jan 9 at 21:52