Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the proper definition of a Countable Set?

share|improve this question
    
Can someone change "definition" to "terminology" and add the "discrete-math" or "discrete-mathematics" tag (not sure which one exists). –  Thomas Owens Aug 22 '10 at 20:08
    
this question is answered by Wikipedia — voting to close –  Grigory M Aug 22 '10 at 20:09
2  
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. –  Thomas Owens Aug 22 '10 at 20:10
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. –  Qiaochu Yuan Aug 22 '10 at 21:12
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! –  Pete L. Clark Aug 22 '10 at 22:16

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
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. –  Thomas Owens Aug 22 '10 at 20:06
    
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). –  Isaac Aug 22 '10 at 22:50

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

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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.