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 a countable set?

In Wikipedia we read this definition:

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

Now, what is the cardinality of $\mathbb{N}$? $\mathbb{N}$ contains an infinity of numbers so its cardinality should be $\infty$, isn't it? So a countable set could contain an infinity of elements? In this case, in which way is it countable?

share|improve this question
    
$\{1,2,3\}$ is a subset of the naturals, but it certainly isn't infinite. Countable means "at most countably infinite". This particular question has been answered numerous times on this site and others. –  EuYu Oct 1 '12 at 19:24
4  
A countable set can be infinite. But mathematicians have a way to make distinctions between different sizes of infinity, so one symbol $\infty$ is not enough to describe how many elements an infinite set has. –  Michael Greinecker Oct 1 '12 at 19:24
    
The official definition is some variant of the one you quoted. However, countable" is also often used as a technically wrong abbreviation for "countably infinite." In ordinary language, words can change meaning over time. That may be happening with "countable." –  André Nicolas Oct 1 '12 at 20:39
    
@ineff: Perhaps it is better to say the cardinality of $\mathbb N$ is $\aleph_0$. –  GEdgar Oct 1 '12 at 21:29

5 Answers 5

up vote 3 down vote accepted

If two sets are "of the same cardinality", that means that their elements can be paired off one-by-one against each other. As soon as we start doing this with a few different sets, we see that not all infinite sets are "of the same cardinality" in this sense. For example, $\Bbb R$ and $\Bbb N$ can NOT be paired off one-by-one against each other. In other words, there are different sizes of infinity.

The word "countable" just means that a set is EITHER finite, OR is of the smallest type of infinity (like $\Bbb N$). It's "uncountable" if it's a larger infinity - that is, it's too big to be paired off one-by-one against $\Bbb N$.

share|improve this answer

If we said countable set we mean that the set is in one-to-one corresponding with set of Natural numbers, so we can arrangment the element of the countable set is a sequence form and easy we can deal with it.

share|improve this answer

God can count a countable set :-) That is to say, less metaphorically, the members of a countable set $A$ can be "counted off" in the perhaps unending sequence $a_0, a_1, a_2, a_3, \ldots$ with any given member of $A$ appearing eventually. Even less metaphorically, to say $A$ is countable is to say there is a one-one correspondence between $A$ and some subset of $\mathbb{N}$ (so trivially, by definition, $\mathbb{N}$ itself counts as countable).

Cantor's theorem shows that there are, however, infinite sets which are not countable in this sense (as another visit to Wikipedia will reveal).

share|improve this answer

$A$ is countable iff there is a bijective (1-1 and onto) mapping $f: A \to \mathbb{N}$, where $\mathbb{N}$ is the set of all natural numbers.

share|improve this answer
    
Yes, you are right. One can drop "onto" property and it is fine. –  kalvotom Oct 1 '12 at 21:21

What is "countable"? Well, we can count the members of a set with two elements, and we can count the members of a set with $42$ elements. In fact for every natural number $n$ we can [theoretically] count the members of a set of size $n$.

In fact we know that a set is of size $n$ if we counted its element and ended up counting all the way up to $n$, but not more.

Mathematics, however, is a lot more than finite objects. Let us consider an interesting property of the natural numbers which makes them countable, mathematically at least. Note that despite being infinite in size, we can still count every member at a finite step. Indeed if we had counted all the natural numbers then we have counted all the finite numbers, but not more.

For this reason if a set is such that for every element we can label a unique natural number, and we will exhaust all the elements by the time we exhausted all the natural numbers -- in such case we say that the set is countable. We can count it as the natural numbers.

For example, the integers (negative, positive and zero) are countable. In a slightly more difficult argument so are all the fractions. However not all infinite sets are countable, the real numbers (all the decimal numbers, if you like) are uncountable, they cannot be put in such list and the natural numbers would exhaust way before the real numbers have.

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.