Mixing
Mapping between a finite set and the set of natural numbers
0
$begingroup$
In one of the exercise I'm doing, I have to prove that some finite set is countable. Yet in the same book the definition of countability of a set A is that there exists a 1-to-1 mapping of A onto the set J of natural numbers. How can this be possible?
real-analysis
asked Jan 9 at 21:50
Josh NgJosh Ng
977
$endgroup$
|
show 3 more comments
0
$begingroup$
In one of the exercise I'm doing, I have to prove that some finite set is countable. Yet in the same book the definition of countability of a set A is that there exists a 1-to-1 mapping of A onto the set J of natural numbers. How can this be possible?
real-analysis
asked Jan 9 at 21:50
Josh NgJosh Ng
977
$endgroup$
1
$begingroup$
You can't. Some books include finite sets as countable and some do not. The definition you have shown excludes them. You can show there is an injection of a finite set into the naturals, but not a bijection with them. You have understood the concept, which is the important thing.
$endgroup$
– Ross Millikan
Jan 9 at 21:58
$begingroup$
According to this books definition that is a contradiction. Finite is "at most countable". However many text (I think most but I don't have the numbers to back me) consider "countable" to mean either "finite" (after all you can count a finite set, can't you) or "countably infinite". This book seems to have inconsistently mixed the two. Assume the book meant "at most countable".
$endgroup$
– fleablood
Jan 9 at 22:11
$begingroup$
"In one of the exercise I'm doing, I have to prove that some finite set is countable." Can you quote the exact problem. If you know the set is finite then by definition is "at most countable". Are you sure the set is finite? Or is that part of what you need to show?
$endgroup$
– fleablood
Jan 9 at 22:14
$begingroup$
Here's the problem being typed out: Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable. Hint: Fix $delta > 0$, and pick $x_1 in X$. Having chosen $x_1,...,x_j in X$, choose $x_{j+1} in X$, if possible, so that $d(x_i,x_{j+1}) geq delta$, for $i=1,...,j$. Show that this process must stop after a finite number of steps, and that X can therefore be covered by finitely many neighborhoods of radius $delta$. Take $delta = 1/n (n = 1, 2, 3...)$ and consider the centers of the corresponding neighborhoods.
$endgroup$
– Josh Ng
Jan 9 at 22:31
$begingroup$
If we follow the hint, then as δ→0, E grows in size. If E is the set that we need to find, then I can see here that this procedure could potentially make E infinite and we might be able to prove the countability of E. But because of the property of X (which is also mentioned in the hint), I assume E is always finite?
$endgroup$
– Josh Ng
Jan 9 at 22:33
|
show 3 more comments
0
0
0
$begingroup$
In one of the exercise I'm doing, I have to prove that some finite set is countable. Yet in the same book the definition of countability of a set A is that there exists a 1-to-1 mapping of A onto the set J of natural numbers. How can this be possible?
real-analysis
asked Jan 9 at 21:50
Josh NgJosh Ng
977
$endgroup$
In one of the exercise I'm doing, I have to prove that some finite set is countable. Yet in the same book the definition of countability of a set A is that there exists a 1-to-1 mapping of A onto the set J of natural numbers. How can this be possible?
real-analysis
real-analysis
asked Jan 9 at 21:50
Josh NgJosh Ng
977
asked Jan 9 at 21:50
Josh NgJosh Ng
977
asked Jan 9 at 21:50
Josh NgJosh Ng
977
asked Jan 9 at 21:50
Josh NgJosh Ng
977
asked Jan 9 at 21:50
Josh NgJosh Ng
977
977
1
$begingroup$
You can't. Some books include finite sets as countable and some do not. The definition you have shown excludes them. You can show there is an injection of a finite set into the naturals, but not a bijection with them. You have understood the concept, which is the important thing.
$endgroup$
– Ross Millikan
Jan 9 at 21:58
$begingroup$
According to this books definition that is a contradiction. Finite is "at most countable". However many text (I think most but I don't have the numbers to back me) consider "countable" to mean either "finite" (after all you can count a finite set, can't you) or "countably infinite". This book seems to have inconsistently mixed the two. Assume the book meant "at most countable".
$endgroup$
– fleablood
Jan 9 at 22:11
$begingroup$
"In one of the exercise I'm doing, I have to prove that some finite set is countable." Can you quote the exact problem. If you know the set is finite then by definition is "at most countable". Are you sure the set is finite? Or is that part of what you need to show?
$endgroup$
– fleablood
Jan 9 at 22:14
$begingroup$
Here's the problem being typed out: Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable. Hint: Fix $delta > 0$, and pick $x_1 in X$. Having chosen $x_1,...,x_j in X$, choose $x_{j+1} in X$, if possible, so that $d(x_i,x_{j+1}) geq delta$, for $i=1,...,j$. Show that this process must stop after a finite number of steps, and that X can therefore be covered by finitely many neighborhoods of radius $delta$. Take $delta = 1/n (n = 1, 2, 3...)$ and consider the centers of the corresponding neighborhoods.
$endgroup$
– Josh Ng
Jan 9 at 22:31
$begingroup$
If we follow the hint, then as δ→0, E grows in size. If E is the set that we need to find, then I can see here that this procedure could potentially make E infinite and we might be able to prove the countability of E. But because of the property of X (which is also mentioned in the hint), I assume E is always finite?
$endgroup$
– Josh Ng
Jan 9 at 22:33
|
show 3 more comments
1
$begingroup$
You can't. Some books include finite sets as countable and some do not. The definition you have shown excludes them. You can show there is an injection of a finite set into the naturals, but not a bijection with them. You have understood the concept, which is the important thing.
$endgroup$
– Ross Millikan
Jan 9 at 21:58
$begingroup$
According to this books definition that is a contradiction. Finite is "at most countable". However many text (I think most but I don't have the numbers to back me) consider "countable" to mean either "finite" (after all you can count a finite set, can't you) or "countably infinite". This book seems to have inconsistently mixed the two. Assume the book meant "at most countable".
$endgroup$
– fleablood
Jan 9 at 22:11
$begingroup$
"In one of the exercise I'm doing, I have to prove that some finite set is countable." Can you quote the exact problem. If you know the set is finite then by definition is "at most countable". Are you sure the set is finite? Or is that part of what you need to show?
$endgroup$
– fleablood
Jan 9 at 22:14
$begingroup$
Here's the problem being typed out: Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable. Hint: Fix $delta > 0$, and pick $x_1 in X$. Having chosen $x_1,...,x_j in X$, choose $x_{j+1} in X$, if possible, so that $d(x_i,x_{j+1}) geq delta$, for $i=1,...,j$. Show that this process must stop after a finite number of steps, and that X can therefore be covered by finitely many neighborhoods of radius $delta$. Take $delta = 1/n (n = 1, 2, 3...)$ and consider the centers of the corresponding neighborhoods.
$endgroup$
– Josh Ng
Jan 9 at 22:31
$begingroup$
If we follow the hint, then as δ→0, E grows in size. If E is the set that we need to find, then I can see here that this procedure could potentially make E infinite and we might be able to prove the countability of E. But because of the property of X (which is also mentioned in the hint), I assume E is always finite?
$endgroup$
– Josh Ng
Jan 9 at 22:33
1
1
$begingroup$
You can't. Some books include finite sets as countable and some do not. The definition you have shown excludes them. You can show there is an injection of a finite set into the naturals, but not a bijection with them. You have understood the concept, which is the important thing.
$endgroup$
– Ross Millikan
Jan 9 at 21:58
$begingroup$
You can't. Some books include finite sets as countable and some do not. The definition you have shown excludes them. You can show there is an injection of a finite set into the naturals, but not a bijection with them. You have understood the concept, which is the important thing.
$endgroup$
– Ross Millikan
Jan 9 at 21:58
$begingroup$
According to this books definition that is a contradiction. Finite is "at most countable". However many text (I think most but I don't have the numbers to back me) consider "countable" to mean either "finite" (after all you can count a finite set, can't you) or "countably infinite". This book seems to have inconsistently mixed the two. Assume the book meant "at most countable".
$endgroup$
– fleablood
Jan 9 at 22:11
$begingroup$
According to this books definition that is a contradiction. Finite is "at most countable". However many text (I think most but I don't have the numbers to back me) consider "countable" to mean either "finite" (after all you can count a finite set, can't you) or "countably infinite". This book seems to have inconsistently mixed the two. Assume the book meant "at most countable".
$endgroup$
– fleablood
Jan 9 at 22:11
$begingroup$
"In one of the exercise I'm doing, I have to prove that some finite set is countable." Can you quote the exact problem. If you know the set is finite then by definition is "at most countable". Are you sure the set is finite? Or is that part of what you need to show?
$endgroup$
– fleablood
Jan 9 at 22:14
$begingroup$
"In one of the exercise I'm doing, I have to prove that some finite set is countable." Can you quote the exact problem. If you know the set is finite then by definition is "at most countable". Are you sure the set is finite? Or is that part of what you need to show?
$endgroup$
– fleablood
Jan 9 at 22:14
$begingroup$
Here's the problem being typed out: Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable. Hint: Fix $delta > 0$, and pick $x_1 in X$. Having chosen $x_1,...,x_j in X$, choose $x_{j+1} in X$, if possible, so that $d(x_i,x_{j+1}) geq delta$, for $i=1,...,j$. Show that this process must stop after a finite number of steps, and that X can therefore be covered by finitely many neighborhoods of radius $delta$. Take $delta = 1/n (n = 1, 2, 3...)$ and consider the centers of the corresponding neighborhoods.
$endgroup$
– Josh Ng
Jan 9 at 22:31
$begingroup$
Here's the problem being typed out: Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable. Hint: Fix $delta > 0$, and pick $x_1 in X$. Having chosen $x_1,...,x_j in X$, choose $x_{j+1} in X$, if possible, so that $d(x_i,x_{j+1}) geq delta$, for $i=1,...,j$. Show that this process must stop after a finite number of steps, and that X can therefore be covered by finitely many neighborhoods of radius $delta$. Take $delta = 1/n (n = 1, 2, 3...)$ and consider the centers of the corresponding neighborhoods.
$endgroup$
– Josh Ng
Jan 9 at 22:31
$begingroup$
If we follow the hint, then as δ→0, E grows in size. If E is the set that we need to find, then I can see here that this procedure could potentially make E infinite and we might be able to prove the countability of E. But because of the property of X (which is also mentioned in the hint), I assume E is always finite?
$endgroup$
– Josh Ng
Jan 9 at 22:33
$begingroup$
If we follow the hint, then as δ→0, E grows in size. If E is the set that we need to find, then I can see here that this procedure could potentially make E infinite and we might be able to prove the countability of E. But because of the property of X (which is also mentioned in the hint), I assume E is always finite?
$endgroup$
– Josh Ng
Jan 9 at 22:33
|
show 3 more comments
0
active
oldest
votes
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%2f3067990%2fmapping-between-a-finite-set-and-the-set-of-natural-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3067990%2fmapping-between-a-finite-set-and-the-set-of-natural-numbers%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 can't. Some books include finite sets as countable and some do not. The definition you have shown excludes them. You can show there is an injection of a finite set into the naturals, but not a bijection with them. You have understood the concept, which is the important thing.
$endgroup$
– Ross Millikan
Jan 9 at 21:58
$begingroup$
According to this books definition that is a contradiction. Finite is "at most countable". However many text (I think most but I don't have the numbers to back me) consider "countable" to mean either "finite" (after all you can count a finite set, can't you) or "countably infinite". This book seems to have inconsistently mixed the two. Assume the book meant "at most countable".
$endgroup$
– fleablood
Jan 9 at 22:11
$begingroup$
"In one of the exercise I'm doing, I have to prove that some finite set is countable." Can you quote the exact problem. If you know the set is finite then by definition is "at most countable". Are you sure the set is finite? Or is that part of what you need to show?
$endgroup$
– fleablood
Jan 9 at 22:14
$begingroup$
Here's the problem being typed out: Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable. Hint: Fix $delta > 0$, and pick $x_1 in X$. Having chosen $x_1,...,x_j in X$, choose $x_{j+1} in X$, if possible, so that $d(x_i,x_{j+1}) geq delta$, for $i=1,...,j$. Show that this process must stop after a finite number of steps, and that X can therefore be covered by finitely many neighborhoods of radius $delta$. Take $delta = 1/n (n = 1, 2, 3...)$ and consider the centers of the corresponding neighborhoods.
$endgroup$
– Josh Ng
Jan 9 at 22:31
$begingroup$
If we follow the hint, then as δ→0, E grows in size. If E is the set that we need to find, then I can see here that this procedure could potentially make E infinite and we might be able to prove the countability of E. But because of the property of X (which is also mentioned in the hint), I assume E is always finite?
$endgroup$
– Josh Ng
Jan 9 at 22:33