What is a countable set?

Solution 1:

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

Solution 2:

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.