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.

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!

share|improve this question
3  
    
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
add comment

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
+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
show 2 more comments

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.