What does countably infinite mean?

Question

How would you concisely explain the concept of countably infinite to a student who isn't exposed to any set theory? I am having difficulty understanding what the concept of countably infinite is, could you please help me understand.

Thank You!

Answer 1

A set $S$ is countably infinite if and only if you can label its members with the positive integers in such a way that each member of $A$ gets exactly one label, and every positive integer is used as a label; it’s exactly as if you were counting the members of $A$, except that you never come to an end. Of course this immediately tells you that the set of positive integers is countably infinite: its members are their own labels!

How about the set of non-negative integers, the positive integers together with $0$? I can give $0$ the label ‘$1$’, $1$ the label ‘$2$’, $2$ the label ‘$3$’, and so on: each non-negative integer $n$ gets the label ‘$n+1$’. Every non-negative integer gets exactly one label, and every positive integer is the label of some non-negative integers. (For instance, ‘$100$’ is the label of $99$.)

Let’s get a little fancier: what about the set $E = \{2,4,6,8,\dots\}$ of even positive integers? $E$ is also countably infinite: just label the even integer $2n$ with the positive integer $n$, so that $2$ is labelled ‘$1$’, $4$ is labelled ‘$2$’, and so on. With just a little more work we can see that the set $O = \{1,3,5,7,\dots\}$ of odd positive is countably infinite: $$\begin{align*} 1 &= 2 \cdot 1 - 1\\ 3 &= 2 \cdot 2 - 1\\ 5 &= 2 \cdot 3 - 1\\ 7 &= 2 \cdot 4 - 1\\ &\qquad\vdots \end{align*}$$ That is, the $n$-th odd positive integer is $2n-1$, so giving $2n-1$ the label $n$ will correctly label all of $O$.

One more: what about all of the integers, positive, negative, and zero? We can list them systematically as $0,1,-1,2,-2,3,-3,4,-4,\dots$ and then label each integer with its position in the list: $0$ gets the label ‘$1$’, $1$ gets the label ‘$2$’, $-1$ gets the label ‘$3$’, and so on. It takes a bit more work this time to write down a formula associating an integer with its label, but it can be done: if $n$ is a positive integer, it’s label is ‘$2n$’, and otherwise $n$ gets the label $1-2n$.

I’ll finish with a significantly more complicated example. Let $P$ be the set of all ordered pairs of positive integers. The members of $P$ can conveniently be displayed in a two-dimensional layout: $$\begin{array}{ccccc}(1,1)&(1,2)&(1,3)&(1,4)&\dots\\ (2,1)&(2,2)&(2,3)&(2,4)&\dots\\ (3,1)&(3,2)&(3,3)&(3,4)&\dots\\ (4,1)&(4,2)&(4,3)&(4,4)&\dots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{array}$$ By starting in the upper left-hand corner and weaving back and forth diagonally, you can properly label every member of $P$: $$\begin{array}{ccccccccc}(1,1)\leftrightarrow 1&\Rightarrow&(1,2)\leftrightarrow 2&&(1,3)\leftrightarrow 6&\Rightarrow&(1,4)\leftrightarrow 7&&\dots\\ &\swarrow&&\nearrow&&\swarrow&&\nearrow&\\ (2,1)\leftrightarrow 3&&(2,2)\leftrightarrow 5&&(2,3)\leftrightarrow 8&&(2,4)\leftrightarrow 14&&\dots\\ \Downarrow&\nearrow&&\swarrow&&\nearrow&&\swarrow&\\ (3,1)\leftrightarrow 4&&(3,2)\leftrightarrow 9&&(3,3)\leftrightarrow 13&&(3,4)\leftrightarrow 18&&\dots\\ &\swarrow&&\nearrow&&\swarrow&&\nearrow&\\ (4,1)\leftrightarrow 10&&(4,2)\leftrightarrow 12&&(4,3)\leftrightarrow 19&&(4,4)\leftrightarrow 25&&\dots\\ \Downarrow&\nearrow&&\swarrow&&\nearrow&&\swarrow&\\ \vdots&&\vdots&&\vdots&&\vdots&&\ddots \end{array}$$ (You should check that labels ‘$12$’, ‘$13$’, ‘$14$’, ‘$18$’, ‘$19$’, and ‘$25$’ are right.) This shows that $P$ is countably infinite. It’s possible express this correspondence by a formula, but that’s going further than necessary just to get across the idea of countably infinite.

Added: The same basic idea that I used for $P$ can be used to show that the set of rational numbers is countably infinite, though some of the technical details are rather non-trivial.