Mixing
Proving Cardinality of Sets?
$begingroup$
Me and my study buddies are having a tough time with this problem and need help. It's probably a lot simpler than we're making it out to be but we need help.
Please prove that the sets E = {even integers}, $mathbb{N}$, and $mathbb{Z}$ are infinite sets and that they have the same cardinality.
discrete-mathematics
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
$endgroup$
add a comment |
$begingroup$
Me and my study buddies are having a tough time with this problem and need help. It's probably a lot simpler than we're making it out to be but we need help.
Please prove that the sets E = {even integers}, $mathbb{N}$, and $mathbb{Z}$ are infinite sets and that they have the same cardinality.
discrete-mathematics
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
$endgroup$
add a comment |
$begingroup$
Me and my study buddies are having a tough time with this problem and need help. It's probably a lot simpler than we're making it out to be but we need help.
Please prove that the sets E = {even integers}, $mathbb{N}$, and $mathbb{Z}$ are infinite sets and that they have the same cardinality.
discrete-mathematics
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
$endgroup$
Me and my study buddies are having a tough time with this problem and need help. It's probably a lot simpler than we're making it out to be but we need help.
Please prove that the sets E = {even integers}, $mathbb{N}$, and $mathbb{Z}$ are infinite sets and that they have the same cardinality.
discrete-mathematics
discrete-mathematics
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
asked Jan 31 at 1:22
Wade KemmsiesWade Kemmsies
333
333
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Hints:
To show the sets are infinite, a contradiction will always be nice. Suppose they're finite, and try to derive a contradiction. For example, you could argue that $Bbb N$ has only $n$ elements, for $n$ finite. Let those elements be ${1,2,3,...,n}$. But $n+1$ is also a natural number, showing a contradiction.
Another way to do this would be to establish bijections between each of the groups. I imagine it's given that the cardinality of either the naturals or integers is $aleph_0$ at this point in your coursework - in that case, any other set bijective with either also has that cardinality. What remains is to establish and prove that such a function is indeed bijective.
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
$endgroup$
add a comment |
$begingroup$
To show that two sets have the same cardinality, you need two find a bijective map between them.
In your case, there exist bijections between E and $mathbb{N}$ and between $mathbb{Z}$ and $mathbb{N}$. Hence $E$ and $mathbb{Z}$ have the same cardinality as $mathbb{N}$. One usually says that a set that has the same cardinality as $mathbb{N}$ is countable.
The bijection between $mathbb{N}$ and $E$ is given by $n mapsto 2n$ and the bijection between $mathbb{N}$ and $mathbb{Z}$ is given by $n mapsto frac{n}{2}$ if $n$ is an even number and $n mapsto frac{-(n+1)}{2}$ if $n$ is an odd number.
I'll let you check that theses maps are actually bijections ;)
answered Jan 31 at 1:29
riri92riri92
2018
$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%2f3094360%2fproving-cardinality-of-sets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hints:
To show the sets are infinite, a contradiction will always be nice. Suppose they're finite, and try to derive a contradiction. For example, you could argue that $Bbb N$ has only $n$ elements, for $n$ finite. Let those elements be ${1,2,3,...,n}$. But $n+1$ is also a natural number, showing a contradiction.
Another way to do this would be to establish bijections between each of the groups. I imagine it's given that the cardinality of either the naturals or integers is $aleph_0$ at this point in your coursework - in that case, any other set bijective with either also has that cardinality. What remains is to establish and prove that such a function is indeed bijective.
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
$endgroup$
add a comment |
$begingroup$
Hints:
To show the sets are infinite, a contradiction will always be nice. Suppose they're finite, and try to derive a contradiction. For example, you could argue that $Bbb N$ has only $n$ elements, for $n$ finite. Let those elements be ${1,2,3,...,n}$. But $n+1$ is also a natural number, showing a contradiction.
Another way to do this would be to establish bijections between each of the groups. I imagine it's given that the cardinality of either the naturals or integers is $aleph_0$ at this point in your coursework - in that case, any other set bijective with either also has that cardinality. What remains is to establish and prove that such a function is indeed bijective.
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
$endgroup$
add a comment |
$begingroup$
Hints:
To show the sets are infinite, a contradiction will always be nice. Suppose they're finite, and try to derive a contradiction. For example, you could argue that $Bbb N$ has only $n$ elements, for $n$ finite. Let those elements be ${1,2,3,...,n}$. But $n+1$ is also a natural number, showing a contradiction.
Another way to do this would be to establish bijections between each of the groups. I imagine it's given that the cardinality of either the naturals or integers is $aleph_0$ at this point in your coursework - in that case, any other set bijective with either also has that cardinality. What remains is to establish and prove that such a function is indeed bijective.
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
$endgroup$
Hints:
To show the sets are infinite, a contradiction will always be nice. Suppose they're finite, and try to derive a contradiction. For example, you could argue that $Bbb N$ has only $n$ elements, for $n$ finite. Let those elements be ${1,2,3,...,n}$. But $n+1$ is also a natural number, showing a contradiction.
Another way to do this would be to establish bijections between each of the groups. I imagine it's given that the cardinality of either the naturals or integers is $aleph_0$ at this point in your coursework - in that case, any other set bijective with either also has that cardinality. What remains is to establish and prove that such a function is indeed bijective.
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
answered Jan 31 at 1:26
Eevee TrainerEevee Trainer
10k31740
10k31740
add a comment |
add a comment |
$begingroup$
To show that two sets have the same cardinality, you need two find a bijective map between them.
In your case, there exist bijections between E and $mathbb{N}$ and between $mathbb{Z}$ and $mathbb{N}$. Hence $E$ and $mathbb{Z}$ have the same cardinality as $mathbb{N}$. One usually says that a set that has the same cardinality as $mathbb{N}$ is countable.
The bijection between $mathbb{N}$ and $E$ is given by $n mapsto 2n$ and the bijection between $mathbb{N}$ and $mathbb{Z}$ is given by $n mapsto frac{n}{2}$ if $n$ is an even number and $n mapsto frac{-(n+1)}{2}$ if $n$ is an odd number.
I'll let you check that theses maps are actually bijections ;)
answered Jan 31 at 1:29
riri92riri92
2018
$endgroup$
add a comment |
$begingroup$
To show that two sets have the same cardinality, you need two find a bijective map between them.
In your case, there exist bijections between E and $mathbb{N}$ and between $mathbb{Z}$ and $mathbb{N}$. Hence $E$ and $mathbb{Z}$ have the same cardinality as $mathbb{N}$. One usually says that a set that has the same cardinality as $mathbb{N}$ is countable.
The bijection between $mathbb{N}$ and $E$ is given by $n mapsto 2n$ and the bijection between $mathbb{N}$ and $mathbb{Z}$ is given by $n mapsto frac{n}{2}$ if $n$ is an even number and $n mapsto frac{-(n+1)}{2}$ if $n$ is an odd number.
I'll let you check that theses maps are actually bijections ;)
answered Jan 31 at 1:29
riri92riri92
2018
$endgroup$
add a comment |
$begingroup$
To show that two sets have the same cardinality, you need two find a bijective map between them.
In your case, there exist bijections between E and $mathbb{N}$ and between $mathbb{Z}$ and $mathbb{N}$. Hence $E$ and $mathbb{Z}$ have the same cardinality as $mathbb{N}$. One usually says that a set that has the same cardinality as $mathbb{N}$ is countable.
The bijection between $mathbb{N}$ and $E$ is given by $n mapsto 2n$ and the bijection between $mathbb{N}$ and $mathbb{Z}$ is given by $n mapsto frac{n}{2}$ if $n$ is an even number and $n mapsto frac{-(n+1)}{2}$ if $n$ is an odd number.
I'll let you check that theses maps are actually bijections ;)
answered Jan 31 at 1:29
riri92riri92
2018
$endgroup$
To show that two sets have the same cardinality, you need two find a bijective map between them.
In your case, there exist bijections between E and $mathbb{N}$ and between $mathbb{Z}$ and $mathbb{N}$. Hence $E$ and $mathbb{Z}$ have the same cardinality as $mathbb{N}$. One usually says that a set that has the same cardinality as $mathbb{N}$ is countable.
The bijection between $mathbb{N}$ and $E$ is given by $n mapsto 2n$ and the bijection between $mathbb{N}$ and $mathbb{Z}$ is given by $n mapsto frac{n}{2}$ if $n$ is an even number and $n mapsto frac{-(n+1)}{2}$ if $n$ is an odd number.
I'll let you check that theses maps are actually bijections ;)
answered Jan 31 at 1:29
riri92riri92
2018
answered Jan 31 at 1:29
riri92riri92
2018
answered Jan 31 at 1:29
riri92riri92
2018
answered Jan 31 at 1:29
riri92riri92
2018
2018
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%2f3094360%2fproving-cardinality-of-sets%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
