Consider $X$ a countably infinite set, is ${X cup x}$ with $x notin X$ countably infinite?
$begingroup$
$x$ represents an element, not a set.
Assume $S:={X cup x}$ is countably finite. This means that there is a bijection between $S$ and a subset of $mathbb{N}$. This is clearly not the case since $X$ is infinite. I don't really know how to write down that last part rigorously. How can I approach this?
Thanks in advance.
discrete-mathematics
asked Jan 20 at 19:34
ZacharyZachary
1679
$endgroup$
|
show 1 more comment
$begingroup$
$x$ represents an element, not a set.
Assume $S:={X cup x}$ is countably finite. This means that there is a bijection between $S$ and a subset of $mathbb{N}$. This is clearly not the case since $X$ is infinite. I don't really know how to write down that last part rigorously. How can I approach this?
Thanks in advance.
discrete-mathematics
asked Jan 20 at 19:34
ZacharyZachary
1679
$endgroup$
1
$begingroup$
You mean $x notin X$, not $X notin x$. Also, presumably $X cup {x}$ rather than ${X cup x}$.
$endgroup$
– Robert Israel
Jan 20 at 19:39
2
$begingroup$
Very important remark. Even if $X$ is really huge, ${X}$ is very very small. So small that it only has one element, $X$. Hence your set $S$ is countably finite (or simply finite) and it is in bijection with the subset of natural numbers consisting in just one element. The bijection is $Xcup xlongmapsto ninmathbb N$.
$endgroup$
– Dog_69
Jan 20 at 19:39
$begingroup$
I did not think about that! Thank you for your thoughtful remark. So if I was to consider $X cup x$, I could say it is countably infinite, right? How could that be proved?
$endgroup$
– Zachary
Jan 20 at 19:44
$begingroup$
@RobertIsrael I edited the question, thanks for noticing. However, I do mean ${X cup x}$.
$endgroup$
– Zachary
Jan 20 at 19:46
1
$begingroup$
@Zachary If $x$ is countable, yes. Maybe you meant $Xcup{ x}$?
$endgroup$
– J.G.
Jan 20 at 19:47
|
show 1 more comment
$begingroup$
$x$ represents an element, not a set.
Assume $S:={X cup x}$ is countably finite. This means that there is a bijection between $S$ and a subset of $mathbb{N}$. This is clearly not the case since $X$ is infinite. I don't really know how to write down that last part rigorously. How can I approach this?
Thanks in advance.
discrete-mathematics
asked Jan 20 at 19:34
ZacharyZachary
1679
$endgroup$
$x$ represents an element, not a set.
Assume $S:={X cup x}$ is countably finite. This means that there is a bijection between $S$ and a subset of $mathbb{N}$. This is clearly not the case since $X$ is infinite. I don't really know how to write down that last part rigorously. How can I approach this?
Thanks in advance.
discrete-mathematics
discrete-mathematics
asked Jan 20 at 19:34
ZacharyZachary
1679
asked Jan 20 at 19:34
ZacharyZachary
1679
edited Jan 20 at 20:04
Zachary
asked Jan 20 at 19:34
ZacharyZachary
1679
asked Jan 20 at 19:34
ZacharyZachary
1679
asked Jan 20 at 19:34
ZacharyZachary
1679
1679
1
$begingroup$
You mean $x notin X$, not $X notin x$. Also, presumably $X cup {x}$ rather than ${X cup x}$.
$endgroup$
– Robert Israel
Jan 20 at 19:39
2
$begingroup$
Very important remark. Even if $X$ is really huge, ${X}$ is very very small. So small that it only has one element, $X$. Hence your set $S$ is countably finite (or simply finite) and it is in bijection with the subset of natural numbers consisting in just one element. The bijection is $Xcup xlongmapsto ninmathbb N$.
$endgroup$
– Dog_69
Jan 20 at 19:39
$begingroup$
I did not think about that! Thank you for your thoughtful remark. So if I was to consider $X cup x$, I could say it is countably infinite, right? How could that be proved?
$endgroup$
– Zachary
Jan 20 at 19:44
$begingroup$
@RobertIsrael I edited the question, thanks for noticing. However, I do mean ${X cup x}$.
$endgroup$
– Zachary
Jan 20 at 19:46
1
$begingroup$
@Zachary If $x$ is countable, yes. Maybe you meant $Xcup{ x}$?
$endgroup$
– J.G.
Jan 20 at 19:47
|
show 1 more comment
1
$begingroup$
You mean $x notin X$, not $X notin x$. Also, presumably $X cup {x}$ rather than ${X cup x}$.
$endgroup$
– Robert Israel
Jan 20 at 19:39
2
$begingroup$
Very important remark. Even if $X$ is really huge, ${X}$ is very very small. So small that it only has one element, $X$. Hence your set $S$ is countably finite (or simply finite) and it is in bijection with the subset of natural numbers consisting in just one element. The bijection is $Xcup xlongmapsto ninmathbb N$.
$endgroup$
– Dog_69
Jan 20 at 19:39
$begingroup$
I did not think about that! Thank you for your thoughtful remark. So if I was to consider $X cup x$, I could say it is countably infinite, right? How could that be proved?
$endgroup$
– Zachary
Jan 20 at 19:44
$begingroup$
@RobertIsrael I edited the question, thanks for noticing. However, I do mean ${X cup x}$.
$endgroup$
– Zachary
Jan 20 at 19:46
1
$begingroup$
@Zachary If $x$ is countable, yes. Maybe you meant $Xcup{ x}$?
$endgroup$
– J.G.
Jan 20 at 19:47
1
1
$begingroup$
You mean $x notin X$, not $X notin x$. Also, presumably $X cup {x}$ rather than ${X cup x}$.
$endgroup$
– Robert Israel
Jan 20 at 19:39
$begingroup$
You mean $x notin X$, not $X notin x$. Also, presumably $X cup {x}$ rather than ${X cup x}$.
$endgroup$
– Robert Israel
Jan 20 at 19:39
2
2
$begingroup$
Very important remark. Even if $X$ is really huge, ${X}$ is very very small. So small that it only has one element, $X$. Hence your set $S$ is countably finite (or simply finite) and it is in bijection with the subset of natural numbers consisting in just one element. The bijection is $Xcup xlongmapsto ninmathbb N$.
$endgroup$
– Dog_69
Jan 20 at 19:39
$begingroup$
Very important remark. Even if $X$ is really huge, ${X}$ is very very small. So small that it only has one element, $X$. Hence your set $S$ is countably finite (or simply finite) and it is in bijection with the subset of natural numbers consisting in just one element. The bijection is $Xcup xlongmapsto ninmathbb N$.
$endgroup$
– Dog_69
Jan 20 at 19:39
$begingroup$
I did not think about that! Thank you for your thoughtful remark. So if I was to consider $X cup x$, I could say it is countably infinite, right? How could that be proved?
$endgroup$
– Zachary
Jan 20 at 19:44
$begingroup$
I did not think about that! Thank you for your thoughtful remark. So if I was to consider $X cup x$, I could say it is countably infinite, right? How could that be proved?
$endgroup$
– Zachary
Jan 20 at 19:44
$begingroup$
@RobertIsrael I edited the question, thanks for noticing. However, I do mean ${X cup x}$.
$endgroup$
– Zachary
Jan 20 at 19:46
$begingroup$
@RobertIsrael I edited the question, thanks for noticing. However, I do mean ${X cup x}$.
$endgroup$
– Zachary
Jan 20 at 19:46
1
1
$begingroup$
@Zachary If $x$ is countable, yes. Maybe you meant $Xcup{ x}$?
$endgroup$
– J.G.
Jan 20 at 19:47
$begingroup$
@Zachary If $x$ is countable, yes. Maybe you meant $Xcup{ x}$?
$endgroup$
– J.G.
Jan 20 at 19:47
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
As the comments point out, your notation is a little confusing. The set $S = lbrace Xcup xrbrace$ contains one element: $Xcup x$. In particular, $S$ is countable. On the other hand, the set $Xcup x$ may not be countable, even if $X$ is countable. This is because $x$ could be uncountable and disjoint from $X$. The statement you are probably looking for is the following:
Proposition. If $X$ is countable and $xnotin X$, then $Xcup lbrace xrbrace$ is countable.
In fact, something much stronger is true. If $X_1,X_2,dots $ is a sequence of countable sets (indexed over the natural numbers), then $bigcup_i^infty X_i$ is countable. To prove this, use that $mathbb Ntimesmathbb N$ is countable and construct a surjection $mathbb Ntimesmathbb Nrightarrow bigcup_i^infty X_i$. The proposition above is then the special case where $X_1 = X$, $X_2 = lbrace xrbrace$ and $X_i = varnothing$ for $i > 2$.
Addendum. Now how would you prove that $mathbb Ntimesmathbb N$ is countable? Here it may help to visualize $mathbb Ntimes mathbb N$ as the nodes of an infinite grid in the first quadrant of $mathbb R^2$. A natural way to "count" these nodes is to "spiral outwards".
answered Jan 20 at 20:19
o.h.o.h.
4516
$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%2f3081048%2fconsider-x-a-countably-infinite-set-is-x-cup-x-with-x-notin-x-count%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$
As the comments point out, your notation is a little confusing. The set $S = lbrace Xcup xrbrace$ contains one element: $Xcup x$. In particular, $S$ is countable. On the other hand, the set $Xcup x$ may not be countable, even if $X$ is countable. This is because $x$ could be uncountable and disjoint from $X$. The statement you are probably looking for is the following:
Proposition. If $X$ is countable and $xnotin X$, then $Xcup lbrace xrbrace$ is countable.
In fact, something much stronger is true. If $X_1,X_2,dots $ is a sequence of countable sets (indexed over the natural numbers), then $bigcup_i^infty X_i$ is countable. To prove this, use that $mathbb Ntimesmathbb N$ is countable and construct a surjection $mathbb Ntimesmathbb Nrightarrow bigcup_i^infty X_i$. The proposition above is then the special case where $X_1 = X$, $X_2 = lbrace xrbrace$ and $X_i = varnothing$ for $i > 2$.
Addendum. Now how would you prove that $mathbb Ntimesmathbb N$ is countable? Here it may help to visualize $mathbb Ntimes mathbb N$ as the nodes of an infinite grid in the first quadrant of $mathbb R^2$. A natural way to "count" these nodes is to "spiral outwards".
answered Jan 20 at 20:19
o.h.o.h.
4516
$endgroup$
add a comment |
$begingroup$
As the comments point out, your notation is a little confusing. The set $S = lbrace Xcup xrbrace$ contains one element: $Xcup x$. In particular, $S$ is countable. On the other hand, the set $Xcup x$ may not be countable, even if $X$ is countable. This is because $x$ could be uncountable and disjoint from $X$. The statement you are probably looking for is the following:
Proposition. If $X$ is countable and $xnotin X$, then $Xcup lbrace xrbrace$ is countable.
In fact, something much stronger is true. If $X_1,X_2,dots $ is a sequence of countable sets (indexed over the natural numbers), then $bigcup_i^infty X_i$ is countable. To prove this, use that $mathbb Ntimesmathbb N$ is countable and construct a surjection $mathbb Ntimesmathbb Nrightarrow bigcup_i^infty X_i$. The proposition above is then the special case where $X_1 = X$, $X_2 = lbrace xrbrace$ and $X_i = varnothing$ for $i > 2$.
Addendum. Now how would you prove that $mathbb Ntimesmathbb N$ is countable? Here it may help to visualize $mathbb Ntimes mathbb N$ as the nodes of an infinite grid in the first quadrant of $mathbb R^2$. A natural way to "count" these nodes is to "spiral outwards".
answered Jan 20 at 20:19
o.h.o.h.
4516
$endgroup$
add a comment |
$begingroup$
As the comments point out, your notation is a little confusing. The set $S = lbrace Xcup xrbrace$ contains one element: $Xcup x$. In particular, $S$ is countable. On the other hand, the set $Xcup x$ may not be countable, even if $X$ is countable. This is because $x$ could be uncountable and disjoint from $X$. The statement you are probably looking for is the following:
Proposition. If $X$ is countable and $xnotin X$, then $Xcup lbrace xrbrace$ is countable.
In fact, something much stronger is true. If $X_1,X_2,dots $ is a sequence of countable sets (indexed over the natural numbers), then $bigcup_i^infty X_i$ is countable. To prove this, use that $mathbb Ntimesmathbb N$ is countable and construct a surjection $mathbb Ntimesmathbb Nrightarrow bigcup_i^infty X_i$. The proposition above is then the special case where $X_1 = X$, $X_2 = lbrace xrbrace$ and $X_i = varnothing$ for $i > 2$.
Addendum. Now how would you prove that $mathbb Ntimesmathbb N$ is countable? Here it may help to visualize $mathbb Ntimes mathbb N$ as the nodes of an infinite grid in the first quadrant of $mathbb R^2$. A natural way to "count" these nodes is to "spiral outwards".
answered Jan 20 at 20:19
o.h.o.h.
4516
$endgroup$
As the comments point out, your notation is a little confusing. The set $S = lbrace Xcup xrbrace$ contains one element: $Xcup x$. In particular, $S$ is countable. On the other hand, the set $Xcup x$ may not be countable, even if $X$ is countable. This is because $x$ could be uncountable and disjoint from $X$. The statement you are probably looking for is the following:
Proposition. If $X$ is countable and $xnotin X$, then $Xcup lbrace xrbrace$ is countable.
In fact, something much stronger is true. If $X_1,X_2,dots $ is a sequence of countable sets (indexed over the natural numbers), then $bigcup_i^infty X_i$ is countable. To prove this, use that $mathbb Ntimesmathbb N$ is countable and construct a surjection $mathbb Ntimesmathbb Nrightarrow bigcup_i^infty X_i$. The proposition above is then the special case where $X_1 = X$, $X_2 = lbrace xrbrace$ and $X_i = varnothing$ for $i > 2$.
Addendum. Now how would you prove that $mathbb Ntimesmathbb N$ is countable? Here it may help to visualize $mathbb Ntimes mathbb N$ as the nodes of an infinite grid in the first quadrant of $mathbb R^2$. A natural way to "count" these nodes is to "spiral outwards".
answered Jan 20 at 20:19
o.h.o.h.
4516
edited Jan 20 at 20:29
answered Jan 20 at 20:19
o.h.o.h.
4516
answered Jan 20 at 20:19
o.h.o.h.
4516
answered Jan 20 at 20:19
o.h.o.h.
4516
4516
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%2f3081048%2fconsider-x-a-countably-infinite-set-is-x-cup-x-with-x-notin-x-count%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$
You mean $x notin X$, not $X notin x$. Also, presumably $X cup {x}$ rather than ${X cup x}$.
$endgroup$
– Robert Israel
Jan 20 at 19:39
2
$begingroup$
Very important remark. Even if $X$ is really huge, ${X}$ is very very small. So small that it only has one element, $X$. Hence your set $S$ is countably finite (or simply finite) and it is in bijection with the subset of natural numbers consisting in just one element. The bijection is $Xcup xlongmapsto ninmathbb N$.
$endgroup$
– Dog_69
Jan 20 at 19:39
$begingroup$
I did not think about that! Thank you for your thoughtful remark. So if I was to consider $X cup x$, I could say it is countably infinite, right? How could that be proved?
$endgroup$
– Zachary
Jan 20 at 19:44
$begingroup$
@RobertIsrael I edited the question, thanks for noticing. However, I do mean ${X cup x}$.
$endgroup$
– Zachary
Jan 20 at 19:46
1
$begingroup$
@Zachary If $x$ is countable, yes. Maybe you meant $Xcup{ x}$?
$endgroup$
– J.G.
Jan 20 at 19:47