4
$\begingroup$

What is the proper definition of a Countable Set?

$\endgroup$
  • $\begingroup$ Can someone change "definition" to "terminology" and add the "discrete-math" or "discrete-mathematics" tag (not sure which one exists). $\endgroup$ – Thomas Owens Aug 22 '10 at 20:08
  • $\begingroup$ this question is answered by Wikipedia — voting to close $\endgroup$ – Grigory M Aug 22 '10 at 20:09
  • 2
    $\begingroup$ And although I can't vote, this is my opposition to closing - it's a valid question. 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. I think a good answer would provide a link to Wikipedia and other sources and quote the relevant material from each. $\endgroup$ – Thomas Owens Aug 22 '10 at 20:10
  • 6
    $\begingroup$ @Thomas: I cannot accept this as a good reason not to close a question. This site would become incredibly bloated if we archived definitions of every mathematical term someone could possibly ask about. $\endgroup$ – Qiaochu Yuan Aug 22 '10 at 21:12
  • 5
    $\begingroup$ "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! $\endgroup$ – Pete L. Clark Aug 22 '10 at 22:16
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there some kind of tutorial on how to use the cool markup for mathematics? I want to express the fact that this can be represented as |S| exists within the set of positive integers or |S| = aleph sub 0 for a countably infinite set S. $\endgroup$ – Thomas Owens Aug 22 '10 at 20:06
  • $\begingroup$ I tend to use 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). $\endgroup$ – Isaac Aug 22 '10 at 22:50
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Isn't it bijective? $\endgroup$ – Dario Aug 22 '10 at 20:02
  • 1
    $\begingroup$ No, that would make it countably infinite. A finite set is also countable. $\endgroup$ – Asaf Karagila Aug 22 '10 at 20:03
  • 1
    $\begingroup$ @Dario: No. If it is bijective then the set is countably infinite. OP only wants a definition of countable which could be finite. $\endgroup$ – kennytm Aug 22 '10 at 20:03
  • $\begingroup$ Argh, I've been reading to quick ;) Of course you're right $\endgroup$ – Dario Aug 22 '10 at 20:21
  • $\begingroup$ The Wikipedia link you give as a reference also points out (at least in the present version) that "countable" sometimes excludes finite sets. $\endgroup$ – Jonas Meyer Nov 25 '10 at 17:32
4
$\begingroup$

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.

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