Etydhv

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?

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.

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?

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) in 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.

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