# What does countably infinite mean?

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!

-
Jeff, I retagged the post appropriately. Please note it is redundant to tag a question with both the [set-theory] and the [elementary-set-theory] tags. – Srivatsan Sep 10 '11 at 23:11

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.

-
+1 Now that you have come so far, you probably could also mention that rationals are countable. :) – Srivatsan Sep 11 '11 at 0:33
@Srivatsan: I thought about it, but making an honest job of it is a bit messy on account of the duplicates: showing that an infinite subset of a countably infinite set is countably infinite without a lot of handwaving isn’t trivial. – Brian M. Scott Sep 11 '11 at 0:37
Yes, I agree that will make the post a tad too long. Your answer is very good as it is. I suggested that because I think the countability of rationals is more mysterious at first sight than ordered pair of natural numbers. – Srivatsan Sep 11 '11 at 0:42
@Brian: The difficulty in establishing definite bijections is why I usually define countable by ‘there is an injection into $\mathbb{N}$’ or ‘there is a surjection from $\mathbb{N}$’. – Zhen Lin Sep 11 '11 at 2:04
Can't you just assign the duplicate labels (1, 5, 13), then for each member of the set [in this case 1/1=2/2=3/3] take the smallest label that applies to it, then you have a set of unique labels {1,2,3,4,6,...} - are we not able to assume that this latter set of labels can be mapped to the positive integers? Or just go "1/1, 1/2, 2/1, 3/1, ... 1/3" to "1, 2, 3, 4, ... 5" directly? Is it just the fact that you can't express it as a formula, or is there some doubt that the rationals are infinite? – Random832 Sep 11 '11 at 5:01