Otdfbt

Old black and white movie: glowing black rocks slowly turn you into stone upon touch

Why don't B747s start takeoffs with full throttle?

Linux tr to convert vertical text to horizontal

Personalization conditions switching doesn`t work in Experience Editor (9.1.0, Initial Release)

Does Peach's float negate shorthop knockback multipliers?

The ring of global sections of a regular scheme

What is the purpose of building foundations?

Will TSA allow me to carry a Continuous Positive Airway Pressure (CPAP) device?

X-shaped crossword

How to make thick Asian sauces?

Humans meet a distant alien species. How do they standardize? - Units of Measure

PhD student with mental health issues and bad performance

How much water is needed to create a Katana capable of cutting flesh, bones and wood?

Responsibility for visa checking

What is the history of the check mark / tick mark?

How could a possessed body begin to rot and decay while it is still alive?

When writing an error prompt, should we end the sentence with a exclamation mark or a dot?

Metal bar on DMM PCB

Building a road to escape Earth's gravity by making a pyramid on Antartica

Do manufacturers try make their components as close to ideal ones as possible?

What's the correct term for a waitress in the Middle Ages?

Is the capacitor drawn or wired wrongly?

What happens to foam insulation board after you pour concrete slab?

Working in the USA for living expenses only; allowed on VWP?

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

6

$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

share|cite|improve this question

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

asked May 18 at 18:41

gallileo22gallileo22

1505

$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 | 

6

$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

share|cite|improve this question

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

asked May 18 at 18:41

gallileo22gallileo22

1505

$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

share|cite|improve this question

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

asked May 18 at 18:41

gallileo22gallileo22

1505

$endgroup$

share|cite|improve this question

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

asked May 18 at 18:41

gallileo22gallileo22

1505

share|cite|improve this question

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

asked May 18 at 18:41

gallileo22gallileo22

1505

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

edited May 18 at 19:12

Asaf Karagila♦

311k33445777

asked May 18 at 18:41

gallileo22gallileo22

1505

asked May 18 at 18:41

gallileo22gallileo22

1505

4 Answers
4

active

oldest

votes

14

$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.

share|cite|improve this answer

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 | 

3

$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?

share|cite|improve this answer

answered May 18 at 19:17

MariahMariah

2,4571718

$endgroup$

add a comment | 

1

$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$.

share|cite|improve this answer

answered May 18 at 19:35

WenWen

1,728417

$endgroup$

add a comment | 

0

$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.

share|cite|improve this answer

edited May 19 at 2:19

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
);



);

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

Name

Email

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

Name

Email

Required, but never shown

14

$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.

share|cite|improve this answer

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 | 

14

$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.

share|cite|improve this answer

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.

share|cite|improve this answer

answered May 18 at 19:15

Asaf Karagila♦Asaf Karagila

311k33445777

$endgroup$

share|cite|improve this answer

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

3

$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?

share|cite|improve this answer

answered May 18 at 19:17

MariahMariah

2,4571718

$endgroup$

add a comment | 

3

$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?

share|cite|improve this answer

answered May 18 at 19:17

MariahMariah

2,4571718

$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?

share|cite|improve this answer

answered May 18 at 19:17

MariahMariah

2,4571718

$endgroup$

share|cite|improve this answer

answered May 18 at 19:17

MariahMariah

2,4571718

answered May 18 at 19:17

MariahMariah

2,4571718

answered May 18 at 19:17

MariahMariah

2,4571718

1

$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$.

share|cite|improve this answer

answered May 18 at 19:35

WenWen

1,728417

$endgroup$

add a comment | 

1

$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$.

share|cite|improve this answer

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$.

share|cite|improve this answer

answered May 18 at 19:35

WenWen

1,728417

$endgroup$

share|cite|improve this answer

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

0

$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.

share|cite|improve this answer

edited May 19 at 2:19

answered May 18 at 19:15

ZestZest

314213

$endgroup$

add a comment | 

0

$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.

share|cite|improve this answer

edited May 19 at 2:19

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.

share|cite|improve this answer

edited May 19 at 2:19

answered May 18 at 19:15

ZestZest

314213

$endgroup$

share|cite|improve this answer

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