4
$\begingroup$

What is the proper definition of a Countable Set?

  • 5
    "I think that it's important to capture these things here because one day, Wikipedia (or any other site) might disappear, leaving this Stack Exchange as the only repository of this knowledge on the Internet." The suggested remedy for the worry that the large number of internet sites already containing this information will "disappear" is...to post the information on another internet site? Good grief!2010-08-22

3 Answers 3

10

A plain English definition from Kenneth Rosen's "Discrete Mathematics and its Applications":

A set that is either finite or has the same cardinality as the set of positive integers is called countable.

  • 0
    I tend to use http://www.codecogs.com/latex/eqneditor.php to put together that sort of thing for here, when I don't know how (not exactly a tutorial, but I learn from it). $|S|\in\mathbb{Z}$ or $|S|=\aleph_0$ (you should be able to right-click on those and choose "show source" to see their source (which is put in dollar-signs to make it render).2010-08-22
6

A non-empty set $X$ is countable if and only if there exists a surjective function $f$ from $\mathbb{N}$ onto $X$.

http://en.wikipedia.org/wiki/Countable_set

  • 0
    @Michael: There can be some minor advantages, but this is really avoidable altogether. Without AC if $f\colon A\to B$ is surjective and $A$ can be well-ordered then $f$ admits an inverse. In particular... if $A$ is countable. :-)2012-05-22
4

It seems not to have yet been mentioned here that there is no universal agreement on the meaning of countable. "Countably infinite" is unambiguous, but some authors use "countable" to mean countably infinite, while many (perhaps most) use countable to mean finite or countably infinite, as the other answers indicate. When authors use countable to refer only to sets in bijection with $\mathbb{N}$, they often end up using the phrase "at most countable". This is seen for example in Rudin's analysis texts. Springer's online encyclopedia also defines countable to mean countably infinite.