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

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

$\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
  • 2
    $\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 $\mathbb{N}$ (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
3
$\begingroup$

If $B$ is countable denote it $B = \{b_n\}_{n \in \mathbb{N}}$.

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?

$\endgroup$
1
$\begingroup$

Use induction! Well, more conveniently, in well ordering-principle form.

Suppose that $f:A\to N'$ is a bijection (basically $N'$ is the range of $A$) where $N'\subseteq \mathbb{N}$. 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'\backslash\{x_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:A\to \{x_i: i\in\mathbb{N}\}$ is a bijection. This is good news, because this is a bijection from $A$ to $\mathbb{N}$ if you think about it carefully. In other words, ordering our set $N'$ from smallest to largest makes it a bijection to $N$.

$\endgroup$
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^n\{m_i\}$ was countable, $$f^{-1}(M) = f^{-1}\left(\bigcup_i^n\{m_i\}\right) = \left(\bigcup_if^{-1}\{m_i\}\right)= \bigcup_{i=1}^n\{a_i\} = A$$ is countable itself.

$\endgroup$
0
$\begingroup$

To me, countable means capable of being put in a list. Thus, any set in bijection with $\omega$, or any finite set, is countable.

I think it's more about comprehension than definition. Any one is free to define anything they like (alá Smale), but are there good reasons for doing that?

The other thing to comprehend here, and which the OP indicates he does understand (but then why ask the question) is that an injection from set $A$ to set $B$ indicates that the cardinality of $A$ is less than or equal to that of $B$.

This is just personal preference, I guess, but I don't find the definition that excludes finiteness from countability as very interesting or exciting. That is, to reiterate, I really don't know who in their right mind would exclude finite sets from being considered countable. After all, countable is a descriptive and suggestive word. And it suggests that finite should be considered countable.

If you want to distinguish the two, there is always countably infinite.

But, this is all just my two cents. If you have some reason why you prefer it the other way, be my guest. To each his own.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.