Is there any correct definition for countable set? I read some book saying a set is countable if there is a bijection between it and the set of all natural numbers, while some other text says if there is an injection into the set of all natural numbers. I really am uncertain which definition is correct.
This is an issue of convenience. Sometimes it's easier to have finite sets "countable", and sometimes you prefer to have only infinite sets, because finite sets will slow down the definitions.
But the two common definitions are those:
- $A$ is countable if it is in bijection with $\Bbb N$.
- $A$ is countable if it has an injection into $\Bbb N$ (i.e. $A$ is finite, or 1 holds).
Theorem. For a set $A$ the following are equivalent:
- $A$ is finite, or there is a bijection between $A$ and $\Bbb N$.
- There exists an injection from $A$ into $\Bbb N$.
- $A$ is empty, or there exists a surjection from $\Bbb N$ onto $A$.
So even if there is a discrepancy between the definitions the difference is never too big.
I know that somebody says that a finite set is countable, but the commonest definition for a countable set is an infinite set which has the cardinality of the integers, and therefore for which there exists an injective function from the set to $\mathbb N$.
Note that there is no need to find a bijective function, since $\mathbb N$ is the smallest infinite set.