Union of a finite set and a countably infinite set is countably infinite
Ok, here is the problem statement:
Prove that if $S$ is any finite set of real numbers, then the union of $S$ and the integers is countably infinite.
This seems pretty obvious to me, knowing that 2 countable sets are countable. But is there some step by step way to prove this? Like do I need to prove bijectivity or something? Thanks!
elementary-set-theory
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
asked Apr 7 '13 at 23:26
user69839user69839
6327
add a comment |
Ok, here is the problem statement:
Prove that if $S$ is any finite set of real numbers, then the union of $S$ and the integers is countably infinite.
This seems pretty obvious to me, knowing that 2 countable sets are countable. But is there some step by step way to prove this? Like do I need to prove bijectivity or something? Thanks!
elementary-set-theory
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
asked Apr 7 '13 at 23:26
user69839user69839
6327
What are the options for the cardinality for our set $A=Scupmathbb Z$? It's certainly not finite, since $|A|geq |mathbb Z|$. Could it be uncountably infinite?
– Ian Coley
Apr 7 '13 at 23:30
add a comment |
Ok, here is the problem statement:
Prove that if $S$ is any finite set of real numbers, then the union of $S$ and the integers is countably infinite.
This seems pretty obvious to me, knowing that 2 countable sets are countable. But is there some step by step way to prove this? Like do I need to prove bijectivity or something? Thanks!
elementary-set-theory
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
asked Apr 7 '13 at 23:26
user69839user69839
6327
Ok, here is the problem statement:
Prove that if $S$ is any finite set of real numbers, then the union of $S$ and the integers is countably infinite.
This seems pretty obvious to me, knowing that 2 countable sets are countable. But is there some step by step way to prove this? Like do I need to prove bijectivity or something? Thanks!
elementary-set-theory
elementary-set-theory
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
asked Apr 7 '13 at 23:26
user69839user69839
6327
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
asked Apr 7 '13 at 23:26
user69839user69839
6327
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
edited Apr 7 '13 at 23:30
Zev Chonoles
109k16226422
109k16226422
asked Apr 7 '13 at 23:26
user69839user69839
6327
asked Apr 7 '13 at 23:26
user69839user69839
6327
asked Apr 7 '13 at 23:26
user69839user69839
6327
6327
What are the options for the cardinality for our set $A=Scupmathbb Z$? It's certainly not finite, since $|A|geq |mathbb Z|$. Could it be uncountably infinite?
– Ian Coley
Apr 7 '13 at 23:30
add a comment |
What are the options for the cardinality for our set $A=Scupmathbb Z$? It's certainly not finite, since $|A|geq |mathbb Z|$. Could it be uncountably infinite?
– Ian Coley
Apr 7 '13 at 23:30
What are the options for the cardinality for our set $A=Scupmathbb Z$? It's certainly not finite, since $|A|geq |mathbb Z|$. Could it be uncountably infinite?
– Ian Coley
Apr 7 '13 at 23:30
What are the options for the cardinality for our set $A=Scupmathbb Z$? It's certainly not finite, since $|A|geq |mathbb Z|$. Could it be uncountably infinite?
– Ian Coley
Apr 7 '13 at 23:30
add a comment |
2 Answers
2
active
oldest
votes
Yes, give a bijection between $Bbb N$ and $Bbb Zcup S$, that is a sequence in the latter which uses each element exactly once.
Say, $SsetminusBbb Z={s_1,..,s_k}$. Then for example this sequence gives a bijection:
$$(s_1,s_2,...,s_k,0,1,-1,2,-2,3,-3,4,-4,dots)$$
That is, $1$ will be mapped to $s_1$, $k+1$ will be mapped to $0$, $k+2$ to $1$, and so on...
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
add a comment |
It is simple to prove that the countable union of countable sets is countable:
Lay out each set in a line (if finite, just repeat over and over), and then go over the elements $e_{i j}$ diagonally: First 0, 0; then 0, 1 and 1, 0; then 2, 0 and 1, 1 and 0, 2; ... If an element has shown up already, skip it. This gives a biyection between $mathbb{N}$ and the union, unless the union is finite.
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
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%2f354351%2funion-of-a-finite-set-and-a-countably-infinite-set-is-countably-infinite%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
Yes, give a bijection between $Bbb N$ and $Bbb Zcup S$, that is a sequence in the latter which uses each element exactly once.
Say, $SsetminusBbb Z={s_1,..,s_k}$. Then for example this sequence gives a bijection:
$$(s_1,s_2,...,s_k,0,1,-1,2,-2,3,-3,4,-4,dots)$$
That is, $1$ will be mapped to $s_1$, $k+1$ will be mapped to $0$, $k+2$ to $1$, and so on...
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
add a comment |
Yes, give a bijection between $Bbb N$ and $Bbb Zcup S$, that is a sequence in the latter which uses each element exactly once.
Say, $SsetminusBbb Z={s_1,..,s_k}$. Then for example this sequence gives a bijection:
$$(s_1,s_2,...,s_k,0,1,-1,2,-2,3,-3,4,-4,dots)$$
That is, $1$ will be mapped to $s_1$, $k+1$ will be mapped to $0$, $k+2$ to $1$, and so on...
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
add a comment |
Yes, give a bijection between $Bbb N$ and $Bbb Zcup S$, that is a sequence in the latter which uses each element exactly once.
Say, $SsetminusBbb Z={s_1,..,s_k}$. Then for example this sequence gives a bijection:
$$(s_1,s_2,...,s_k,0,1,-1,2,-2,3,-3,4,-4,dots)$$
That is, $1$ will be mapped to $s_1$, $k+1$ will be mapped to $0$, $k+2$ to $1$, and so on...
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
Yes, give a bijection between $Bbb N$ and $Bbb Zcup S$, that is a sequence in the latter which uses each element exactly once.
Say, $SsetminusBbb Z={s_1,..,s_k}$. Then for example this sequence gives a bijection:
$$(s_1,s_2,...,s_k,0,1,-1,2,-2,3,-3,4,-4,dots)$$
That is, $1$ will be mapped to $s_1$, $k+1$ will be mapped to $0$, $k+2$ to $1$, and so on...
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
answered Apr 7 '13 at 23:31
BerciBerci
59.7k23672
59.7k23672
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
add a comment |
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
Thank you! I think I got it
– user69839
Apr 7 '13 at 23:34
add a comment |
It is simple to prove that the countable union of countable sets is countable:
Lay out each set in a line (if finite, just repeat over and over), and then go over the elements $e_{i j}$ diagonally: First 0, 0; then 0, 1 and 1, 0; then 2, 0 and 1, 1 and 0, 2; ... If an element has shown up already, skip it. This gives a biyection between $mathbb{N}$ and the union, unless the union is finite.
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
add a comment |
It is simple to prove that the countable union of countable sets is countable:
Lay out each set in a line (if finite, just repeat over and over), and then go over the elements $e_{i j}$ diagonally: First 0, 0; then 0, 1 and 1, 0; then 2, 0 and 1, 1 and 0, 2; ... If an element has shown up already, skip it. This gives a biyection between $mathbb{N}$ and the union, unless the union is finite.
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
add a comment |
It is simple to prove that the countable union of countable sets is countable:
Lay out each set in a line (if finite, just repeat over and over), and then go over the elements $e_{i j}$ diagonally: First 0, 0; then 0, 1 and 1, 0; then 2, 0 and 1, 1 and 0, 2; ... If an element has shown up already, skip it. This gives a biyection between $mathbb{N}$ and the union, unless the union is finite.
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
It is simple to prove that the countable union of countable sets is countable:
Lay out each set in a line (if finite, just repeat over and over), and then go over the elements $e_{i j}$ diagonally: First 0, 0; then 0, 1 and 1, 0; then 2, 0 and 1, 1 and 0, 2; ... If an element has shown up already, skip it. This gives a biyection between $mathbb{N}$ and the union, unless the union is finite.
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
answered Apr 7 '13 at 23:44
vonbrandvonbrand
19.8k63058
19.8k63058
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.
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%2f354351%2funion-of-a-finite-set-and-a-countably-infinite-set-is-countably-infinite%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
What are the options for the cardinality for our set $A=Scupmathbb Z$? It's certainly not finite, since $|A|geq |mathbb Z|$. Could it be uncountably infinite?
– Ian Coley
Apr 7 '13 at 23:30