What is the proper definition of a Countable Set?
Definition of a countable set
-
0Can someone change "definition" to "terminology" and add the "discrete-math" or "discrete-mathematics" tag (not sure which one exists). – 2010-08-22
-
0this question is answered by Wikipedia — voting to close – 2010-08-22
-
2And 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. – 2010-08-22
-
6@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. – 2010-08-22
-
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
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.
-
0Is 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. – 2010-08-22
-
0I 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
A non-empty set $X$ is countable if and only if there exists a surjective function $f$ from $\mathbb{N}$ onto $X$.
-
0Isn't it **bijective**? – 2010-08-22
-
1No, that would make it countably infinite. A finite set is also countable. – 2010-08-22
-
1@Dario: No. If it is bijective then the set is countably *infinite*. OP only wants a definition of *countable* which could be finite. – 2010-08-22
-
0Argh, I've been reading to quick ;) Of course you're right – 2010-08-22
-
0The Wikipedia link you give as a reference also points out (at least in the present version) that "countable" sometimes excludes finite sets. – 2010-11-25
-
0I wouldn't consider a definition that applies only to non-empty sets canonical. – 2012-05-22
-
0@Michael: There are many definitions in mathematics which "avoid" the empty set. They are considered canonical. Of course that for completeness sake one should require that *either $X$ is empty or ...*, but call me crazy I don't feel like bumping what seems to be my first post on the site. :-) – 2012-05-22
-
0I can understand that. But is there an advantage to using surjections *from* $\mathbb{N}$ instead of injections *into* $\mathbb{N}$? I guess the definitions are equivalent even without AC. – 2012-05-22
-
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
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.