2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ As with any such difference, there are two possibilities: either 1) those definitions are equivalent, i.e. you can prove that any set that is countable under one definition will be countable under the other definition and vice versa, or 2) two different authors are using the same word to have different meanings, which happens all the time and can be confusing, but in no way affects the validity of the mathematics. $\endgroup$ – Zev Chonoles Mar 29 '13 at 15:05
  • 2
    $\begingroup$ there's no real definition, but there's a natural one ;) $\endgroup$ – suissidle Mar 29 '13 at 15:11
  • 2
    $\begingroup$ In natural languages, words can gradually change in meaning. This seems to be happening with "countable." The meaning in Cantor's time was finite or in one to one correspondence with the naturals. In current usage, "countable" is often used as an abbreviation for "countably infinite," even when the official definition includes the finites. $\endgroup$ – André Nicolas Mar 29 '13 at 16:12
  • $\begingroup$ @André Nicolas: The usage I'm familiar with is that countable includes finite and one says countably infinite when needed. I suppose now I'll have to say both at most countable and countably infinite (just to be safe), in the same way that I decided over 20 years ago to never use the subset $\subset$ symbol, but instead use $\subseteq$ for subset and use the version with $\neq$ attached for proper subset. Likewise with increasing -- I generally use non-decreasing and strictly increasing instead. BTW, in old literature denumerable was often used for countably infinite, I think. $\endgroup$ – Dave L. Renfro Mar 29 '13 at 17:13
  • $\begingroup$ @Dave: You are correct on all accounts. Old books used 'denumerable' for countably infinite, and it's always best to be safe than sorry. $\endgroup$ – Asaf Karagila Mar 29 '13 at 22:23
10
$\begingroup$

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:

  1. $A$ is countable if it is in bijection with $\Bbb N$.
  2. $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:

  1. $A$ is finite, or there is a bijection between $A$ and $\Bbb N$.
  2. There exists an injection from $A$ into $\Bbb N$.
  3. $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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Or, at least, $\Bbb N$ is a minimal infinite set, even if it isn't necessarily injectable into all other infinite sets. $\endgroup$ – Cameron Buie Mar 29 '13 at 15:29
  • $\begingroup$ Is there a proof that $\mathbb N$ is the smallest infinite set? $\endgroup$ – Jonathan Rich Mar 29 '13 at 15:29
  • $\begingroup$ I thought it is so by construction, if we may say such a thing $\endgroup$ – mau Mar 29 '13 at 15:43
  • 2
    $\begingroup$ I don’t agree that countably infinite is the most common definition of countable. It is at most roughly tied with what I consider the default meaning, ‘having cardinality at most $\omega$’. $\endgroup$ – Brian M. Scott Mar 29 '13 at 16:38
  • $\begingroup$ $\Bbb{N}$ is always injectable into an infinite set assuming the axiom of choice, which OP is likely to assume. $\endgroup$ – Yoni Rozenshein Mar 29 '13 at 16:41

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.