6
$\begingroup$

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!

  • 3
    http://en.wikipedia.org/wiki/Countable_set2011-09-10
  • 0
    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.2011-09-10

1 Answers 1

8

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.

  • 0
    +1 Now that you have come so far, you probably could also mention that rationals are countable. :)2011-09-11
  • 0
    @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.2011-09-11
  • 0
    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.2011-09-11
  • 0
    @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}$’.2011-09-11
  • 0
    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_?2011-09-11
  • 0
    @Random832: Using the smallest label that applies is indeed one way to do it, quite possibly the easiest, but doing it rigorously requires proving that recursive definitions are legitimate. It’s probably fine at an informal level, but the set theorist in me sees it as handwaving.2011-09-11
  • 0
    @Zhen Lin: I suppose that that approach might make sense in a ‘Chapter 0’ for a first abstract algebra course or the like, but I don’t care for it. In a low-level introduction it loses the intuitive underpinning of the notion of countability, and in a rigorous approach it’s not necessary, since one will *prove* that infinite subsets of a countably infinite set are infinite.2011-09-11