Why does an injection from a set to a countable set imply that set is countable?An injection from an infinite set $X$ to $mathbbNimplies X$ is countable.Show that a set is countableEvery infinite set has an infinite countable subset?Show that there exists a bijection from a set that is countable and infinite into natural numbers.Surjective function from a countable setexistence of injection from countable sets to u countable setsProve that $ T $ is at most countableProve a set is countableProve that if $X$ is and infinite set and $Y$ is countable or finite, then $|X cup Y| = |X|$Prove that set $ mathbbZ×mathbbQ$ is countably infinite by constructing a bijection from that set to the natural numbers
How to reverse input order?
Do photons bend spacetime or not?
The roles understanding in the agile development / Is the PO always right?
Does pair production happen even when the photon is around a neutron?
What is the function of the corrugations on a section of the Space Shuttle's external tank?
Where have Brexit voters gone?
I know that there is a preselected candidate for a position to be filled at my department. What should I do?
NIntegrate doesn't evaluate
Python program to take in two strings and print the larger string
Pirate democracy at its finest
Of strange atmospheres - the survivable but unbreathable
What was the idiom for something that we take without a doubt?
What is a Power on Reset IC?
Why does the hash of infinity have the digits of π?
Why were helmets and other body armour not commonplace in the 1800s?
What does $!# mean in Shell scripting?
Do I need full recovery mode when I have multiple daily backup?
Who decides how to classify a novel?
First Match - awk
A steel cutting sword?
Parallel fifths in the orchestra
How to cut a climbing rope?
USPS Back Room - Trespassing?
Is it possible to remotely hack the GPS system and disable GPS service worldwide?
Why does an injection from a set to a countable set imply that set is countable?
An injection from an infinite set $X$ to $mathbbNimplies X$ is countable.Show that a set is countableEvery infinite set has an infinite countable subset?Show that there exists a bijection from a set that is countable and infinite into natural numbers.Surjective function from a countable setexistence of injection from countable sets to u countable setsProve that $ T $ is at most countableProve a set is countableProve that if $X$ is and infinite set and $Y$ is countable or finite, then $|X cup Y| = |X|$Prove that set $ mathbbZ×mathbbQ$ is countably infinite by constructing a bijection from that set to the natural numbers
$begingroup$
I'm reading a proof, and it concludes that a set $A$ is countable after finding an injection from $A$ to a countable set. Why is this true? I thought that we need to find a bijection from $A$ to a countable set to prove $A$ is countable.
Shouldn't $A$ be at most countable?
functions elementary-set-theory
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
asked May 18 at 18:41
gallileo22gallileo22
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I'm reading a proof, and it concludes that a set $A$ is countable after finding an injection from $A$ to a countable set. Why is this true? I thought that we need to find a bijection from $A$ to a countable set to prove $A$ is countable.
Shouldn't $A$ be at most countable?
functions elementary-set-theory
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
asked May 18 at 18:41
gallileo22gallileo22
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
4
$begingroup$
See Countable set : "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set."
$endgroup$
– Mauro ALLEGRANZA
May 18 at 18:42
4
$begingroup$
I have voted to close this question for lacking context. To better answer your question, it would be necessary to know how the authors of the text you are reading have defined "countable". Some authors define it to mean "of cardinality equal to the natural numbers," while others define it to mean "of cardinality less than or equal to the natural numbers". A citation to the work you are reading would go a long way towards establishing context. That being said, I think that if you carefully read the definitions provided to you, the question answers itself.
$endgroup$
– Xander Henderson
May 18 at 20:54
add a comment |
$begingroup$
I'm reading a proof, and it concludes that a set $A$ is countable after finding an injection from $A$ to a countable set. Why is this true? I thought that we need to find a bijection from $A$ to a countable set to prove $A$ is countable.
Shouldn't $A$ be at most countable?
functions elementary-set-theory
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
asked May 18 at 18:41
gallileo22gallileo22
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I'm reading a proof, and it concludes that a set $A$ is countable after finding an injection from $A$ to a countable set. Why is this true? I thought that we need to find a bijection from $A$ to a countable set to prove $A$ is countable.
Shouldn't $A$ be at most countable?
functions elementary-set-theory
functions elementary-set-theory
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
asked May 18 at 18:41
gallileo22gallileo22
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
asked May 18 at 18:41
gallileo22gallileo22
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
edited May 18 at 19:12
Asaf Karagila♦
311k33445777
311k33445777
asked May 18 at 18:41
gallileo22gallileo22
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked May 18 at 18:41
gallileo22gallileo22
1385
asked May 18 at 18:41
gallileo22gallileo22
1385
1385
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
gallileo22 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
4
$begingroup$
See Countable set : "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set."
$endgroup$
– Mauro ALLEGRANZA
May 18 at 18:42
4
$begingroup$
I have voted to close this question for lacking context. To better answer your question, it would be necessary to know how the authors of the text you are reading have defined "countable". Some authors define it to mean "of cardinality equal to the natural numbers," while others define it to mean "of cardinality less than or equal to the natural numbers". A citation to the work you are reading would go a long way towards establishing context. That being said, I think that if you carefully read the definitions provided to you, the question answers itself.
$endgroup$
– Xander Henderson
May 18 at 20:54
add a comment |
4
$begingroup$
See Countable set : "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set."
$endgroup$
– Mauro ALLEGRANZA
May 18 at 18:42
4
$begingroup$
I have voted to close this question for lacking context. To better answer your question, it would be necessary to know how the authors of the text you are reading have defined "countable". Some authors define it to mean "of cardinality equal to the natural numbers," while others define it to mean "of cardinality less than or equal to the natural numbers". A citation to the work you are reading would go a long way towards establishing context. That being said, I think that if you carefully read the definitions provided to you, the question answers itself.
$endgroup$
– Xander Henderson
May 18 at 20:54
4
4
$begingroup$
See Countable set : "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set."
$endgroup$
– Mauro ALLEGRANZA
May 18 at 18:42
$begingroup$
See Countable set : "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set."
$endgroup$
– Mauro ALLEGRANZA
May 18 at 18:42
4
4
$begingroup$
I have voted to close this question for lacking context. To better answer your question, it would be necessary to know how the authors of the text you are reading have defined "countable". Some authors define it to mean "of cardinality equal to the natural numbers," while others define it to mean "of cardinality less than or equal to the natural numbers". A citation to the work you are reading would go a long way towards establishing context. That being said, I think that if you carefully read the definitions provided to you, the question answers itself.
$endgroup$
– Xander Henderson
May 18 at 20:54
$begingroup$
I have voted to close this question for lacking context. To better answer your question, it would be necessary to know how the authors of the text you are reading have defined "countable". Some authors define it to mean "of cardinality equal to the natural numbers," while others define it to mean "of cardinality less than or equal to the natural numbers". A citation to the work you are reading would go a long way towards establishing context. That being said, I think that if you carefully read the definitions provided to you, the question answers itself.
$endgroup$
– Xander Henderson
May 18 at 20:54
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Unfortunately, there is no uniform agreement to the meaning of "countable". Specifically, does it mean only countably infinite, or do we include also finite sets?
Well. The answer depends on context, convenience, and author. Sometimes it's easier to separate the finite and infinite, and sometimes it's clearer if we lump them together.
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
$endgroup$
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
5
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
1
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
add a comment |
$begingroup$
If $B$ is countable denote it $B = b_n_n in mathbbN$.
If $f : A to B$ is injective for all $a in A$ there is a $b_n = a$. Since the map is injective two different elements in $A$ map to different points in $B$, so can you see how to enumerate $A$ now?
answered May 18 at 19:17
MariahMariah
2,2151718
$endgroup$
add a comment |
$begingroup$
Use induction! Well, more conveniently, in well ordering-principle form.
Suppose that $f:Ato N'$ is a bijection (basically $N'$ is the range of $A$) where $N'subseteq mathbbN$. Now we consider elements in $N'$. Take the smallest element in $N'$ (which exists by the well-ordering principle), say $x_1$. Then consider the second smallest element (which exists because $N'backslashx_1$ is a set), and call this $x_2$. Repeat with $x_3$, etc. (if we ever run out of elements in $N'$ then we know $A$ is finite which is fine).
Now we know that $f:Ato x_i: iinmathbbN$ is a bijection. This is good news, because this is a bijection from $A$ to $mathbbN$ if you think about it carefully. In other words, ordering our set $N'$ from smallest to largest makes it a bijection to $N$.
answered May 18 at 19:35
WenWen
1,728417
$endgroup$
add a comment |
$begingroup$
Consider this:
Let $A$ be an arbitrary set, $M$ be a countable set and $f:A to M$ injective.
It holds that the preimage $f^-1(m_i) subset A$ of each $m_i in M$ ($i=1,2,...$) is a single pointed set.
In other words: each individual element $m_i in M$ has an individual preimage $f^-1(m_i) = a_i subset A$
Since $M = bigcup_i^nm_i$ was countable, $$f^-1(M) = f^-1left(bigcup_i^nm_iright) = left(bigcup_if^-1m_iright)= bigcup_i=1^na_i = A$$ is countable itself.
answered May 18 at 19:15
ZestZest
314213
$endgroup$
add a comment |
Your Answer
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
);
);
gallileo22 is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3230912%2fwhy-does-an-injection-from-a-set-to-a-countable-set-imply-that-set-is-countable%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Unfortunately, there is no uniform agreement to the meaning of "countable". Specifically, does it mean only countably infinite, or do we include also finite sets?
Well. The answer depends on context, convenience, and author. Sometimes it's easier to separate the finite and infinite, and sometimes it's clearer if we lump them together.
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
$endgroup$
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
5
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
1
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
add a comment |
$begingroup$
Unfortunately, there is no uniform agreement to the meaning of "countable". Specifically, does it mean only countably infinite, or do we include also finite sets?
Well. The answer depends on context, convenience, and author. Sometimes it's easier to separate the finite and infinite, and sometimes it's clearer if we lump them together.
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
$endgroup$
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
5
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
1
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
add a comment |
$begingroup$
Unfortunately, there is no uniform agreement to the meaning of "countable". Specifically, does it mean only countably infinite, or do we include also finite sets?
Well. The answer depends on context, convenience, and author. Sometimes it's easier to separate the finite and infinite, and sometimes it's clearer if we lump them together.
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
$endgroup$
Unfortunately, there is no uniform agreement to the meaning of "countable". Specifically, does it mean only countably infinite, or do we include also finite sets?
Well. The answer depends on context, convenience, and author. Sometimes it's easier to separate the finite and infinite, and sometimes it's clearer if we lump them together.
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
answered May 18 at 19:15
Asaf Karagila♦Asaf Karagila
311k33445777
311k33445777
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
5
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
1
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
add a comment |
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
5
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
1
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
$begingroup$
every finite set is countable.
$endgroup$
– Zest
May 18 at 19:19
5
5
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Yes. Except for when you define countable sets as those sets which are in bijection with $omega$.
$endgroup$
– Asaf Karagila♦
May 18 at 19:20
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
Honestly, I'm not sure why people downvoted this. The question is literally asking about the confusion whether or not an injection or a bijection is enough to prove a set is countable. This is literally about the definition of being countable.
$endgroup$
– Asaf Karagila♦
May 18 at 19:49
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
$begingroup$
it wasn't me though. my answer got downvoted too.
$endgroup$
– Zest
May 18 at 19:53
1
1
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
$begingroup$
If you want to be really technical, you would also have to prove that there are no infinite sets that are strictly smaller than $mathbbN$ (which is actually an interesting proof in its own right, but I'm not sure if that's what OP is asking for).
$endgroup$
– Kevin
May 19 at 4:24
add a comment |
$begingroup$
If $B$ is countable denote it $B = b_n_n in mathbbN$.
If $f : A to B$ is injective for all $a in A$ there is a $b_n = a$. Since the map is injective two different elements in $A$ map to different points in $B$, so can you see how to enumerate $A$ now?
answered May 18 at 19:17
MariahMariah
2,2151718
$endgroup$
add a comment |
$begingroup$
If $B$ is countable denote it $B = b_n_n in mathbbN$.
If $f : A to B$ is injective for all $a in A$ there is a $b_n = a$. Since the map is injective two different elements in $A$ map to different points in $B$, so can you see how to enumerate $A$ now?
answered May 18 at 19:17
MariahMariah
2,2151718
$endgroup$
add a comment |
$begingroup$
If $B$ is countable denote it $B = b_n_n in mathbbN$.
If $f : A to B$ is injective for all $a in A$ there is a $b_n = a$. Since the map is injective two different elements in $A$ map to different points in $B$, so can you see how to enumerate $A$ now?
answered May 18 at 19:17
MariahMariah
2,2151718
$endgroup$
If $B$ is countable denote it $B = b_n_n in mathbbN$.
If $f : A to B$ is injective for all $a in A$ there is a $b_n = a$. Since the map is injective two different elements in $A$ map to different points in $B$, so can you see how to enumerate $A$ now?
answered May 18 at 19:17
MariahMariah
2,2151718
answered May 18 at 19:17
MariahMariah
2,2151718
answered May 18 at 19:17
MariahMariah
2,2151718
answered May 18 at 19:17
MariahMariah
2,2151718
2,2151718
add a comment |
add a comment |
$begingroup$
Use induction! Well, more conveniently, in well ordering-principle form.
Suppose that $f:Ato N'$ is a bijection (basically $N'$ is the range of $A$) where $N'subseteq mathbbN$. Now we consider elements in $N'$. Take the smallest element in $N'$ (which exists by the well-ordering principle), say $x_1$. Then consider the second smallest element (which exists because $N'backslashx_1$ is a set), and call this $x_2$. Repeat with $x_3$, etc. (if we ever run out of elements in $N'$ then we know $A$ is finite which is fine).
Now we know that $f:Ato x_i: iinmathbbN$ is a bijection. This is good news, because this is a bijection from $A$ to $mathbbN$ if you think about it carefully. In other words, ordering our set $N'$ from smallest to largest makes it a bijection to $N$.
answered May 18 at 19:35
WenWen
1,728417
$endgroup$
add a comment |
$begingroup$
Use induction! Well, more conveniently, in well ordering-principle form.
Suppose that $f:Ato N'$ is a bijection (basically $N'$ is the range of $A$) where $N'subseteq mathbbN$. Now we consider elements in $N'$. Take the smallest element in $N'$ (which exists by the well-ordering principle), say $x_1$. Then consider the second smallest element (which exists because $N'backslashx_1$ is a set), and call this $x_2$. Repeat with $x_3$, etc. (if we ever run out of elements in $N'$ then we know $A$ is finite which is fine).
Now we know that $f:Ato x_i: iinmathbbN$ is a bijection. This is good news, because this is a bijection from $A$ to $mathbbN$ if you think about it carefully. In other words, ordering our set $N'$ from smallest to largest makes it a bijection to $N$.
answered May 18 at 19:35
WenWen
1,728417
$endgroup$
add a comment |
$begingroup$
Use induction! Well, more conveniently, in well ordering-principle form.
Suppose that $f:Ato N'$ is a bijection (basically $N'$ is the range of $A$) where $N'subseteq mathbbN$. Now we consider elements in $N'$. Take the smallest element in $N'$ (which exists by the well-ordering principle), say $x_1$. Then consider the second smallest element (which exists because $N'backslashx_1$ is a set), and call this $x_2$. Repeat with $x_3$, etc. (if we ever run out of elements in $N'$ then we know $A$ is finite which is fine).
Now we know that $f:Ato x_i: iinmathbbN$ is a bijection. This is good news, because this is a bijection from $A$ to $mathbbN$ if you think about it carefully. In other words, ordering our set $N'$ from smallest to largest makes it a bijection to $N$.
answered May 18 at 19:35
WenWen
1,728417
$endgroup$
Use induction! Well, more conveniently, in well ordering-principle form.
Suppose that $f:Ato N'$ is a bijection (basically $N'$ is the range of $A$) where $N'subseteq mathbbN$. Now we consider elements in $N'$. Take the smallest element in $N'$ (which exists by the well-ordering principle), say $x_1$. Then consider the second smallest element (which exists because $N'backslashx_1$ is a set), and call this $x_2$. Repeat with $x_3$, etc. (if we ever run out of elements in $N'$ then we know $A$ is finite which is fine).
Now we know that $f:Ato x_i: iinmathbbN$ is a bijection. This is good news, because this is a bijection from $A$ to $mathbbN$ if you think about it carefully. In other words, ordering our set $N'$ from smallest to largest makes it a bijection to $N$.
answered May 18 at 19:35
WenWen
1,728417
answered May 18 at 19:35
WenWen
1,728417
answered May 18 at 19:35
WenWen
1,728417
answered May 18 at 19:35
WenWen
1,728417
1,728417
add a comment |
add a comment |
$begingroup$
Consider this:
Let $A$ be an arbitrary set, $M$ be a countable set and $f:A to M$ injective.
It holds that the preimage $f^-1(m_i) subset A$ of each $m_i in M$ ($i=1,2,...$) is a single pointed set.
In other words: each individual element $m_i in M$ has an individual preimage $f^-1(m_i) = a_i subset A$
Since $M = bigcup_i^nm_i$ was countable, $$f^-1(M) = f^-1left(bigcup_i^nm_iright) = left(bigcup_if^-1m_iright)= bigcup_i=1^na_i = A$$ is countable itself.
answered May 18 at 19:15
ZestZest
314213
$endgroup$
add a comment |
$begingroup$
Consider this:
Let $A$ be an arbitrary set, $M$ be a countable set and $f:A to M$ injective.
It holds that the preimage $f^-1(m_i) subset A$ of each $m_i in M$ ($i=1,2,...$) is a single pointed set.
In other words: each individual element $m_i in M$ has an individual preimage $f^-1(m_i) = a_i subset A$
Since $M = bigcup_i^nm_i$ was countable, $$f^-1(M) = f^-1left(bigcup_i^nm_iright) = left(bigcup_if^-1m_iright)= bigcup_i=1^na_i = A$$ is countable itself.
answered May 18 at 19:15
ZestZest
314213
$endgroup$
add a comment |
$begingroup$
Consider this:
Let $A$ be an arbitrary set, $M$ be a countable set and $f:A to M$ injective.
It holds that the preimage $f^-1(m_i) subset A$ of each $m_i in M$ ($i=1,2,...$) is a single pointed set.
In other words: each individual element $m_i in M$ has an individual preimage $f^-1(m_i) = a_i subset A$
Since $M = bigcup_i^nm_i$ was countable, $$f^-1(M) = f^-1left(bigcup_i^nm_iright) = left(bigcup_if^-1m_iright)= bigcup_i=1^na_i = A$$ is countable itself.
answered May 18 at 19:15
ZestZest
314213
$endgroup$
Consider this:
Let $A$ be an arbitrary set, $M$ be a countable set and $f:A to M$ injective.
It holds that the preimage $f^-1(m_i) subset A$ of each $m_i in M$ ($i=1,2,...$) is a single pointed set.
In other words: each individual element $m_i in M$ has an individual preimage $f^-1(m_i) = a_i subset A$
Since $M = bigcup_i^nm_i$ was countable, $$f^-1(M) = f^-1left(bigcup_i^nm_iright) = left(bigcup_if^-1m_iright)= bigcup_i=1^na_i = A$$ is countable itself.
answered May 18 at 19:15
ZestZest
314213
edited May 19 at 2:19
answered May 18 at 19:15
ZestZest
314213
answered May 18 at 19:15
ZestZest
314213
answered May 18 at 19:15
ZestZest
314213
314213
add a comment |
add a comment |
gallileo22 is a new contributor. Be nice, and check out our Code of Conduct.
gallileo22 is a new contributor. Be nice, and check out our Code of Conduct.
gallileo22 is a new contributor. Be nice, and check out our Code of Conduct.
gallileo22 is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3230912%2fwhy-does-an-injection-from-a-set-to-a-countable-set-imply-that-set-is-countable%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
4
$begingroup$
See Countable set : "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set."
$endgroup$
– Mauro ALLEGRANZA
May 18 at 18:42
4
$begingroup$
I have voted to close this question for lacking context. To better answer your question, it would be necessary to know how the authors of the text you are reading have defined "countable". Some authors define it to mean "of cardinality equal to the natural numbers," while others define it to mean "of cardinality less than or equal to the natural numbers". A citation to the work you are reading would go a long way towards establishing context. That being said, I think that if you carefully read the definitions provided to you, the question answers itself.
$endgroup$
– Xander Henderson
May 18 at 20:54