1
$\begingroup$

Picture from Biggs' Discrete Mathematics

During some set theory exercises I came across the proof that the rationals are countably infinite. It used what appears to be a common proof where all the pairs are listed and a zig-zagging path is taking through them, starting with $(1,1), (1,2), (2,1)...$ and so forth.

Of course I am tasked with proving all kinds of related things and my first snag is the following: Is the path taken, or maybe better put, is the enumeration strategy important?

I'm guessing it is, if you would just list all pairs $\sum_{i=1} (1,i)$ first, you would never reach $(2,1), (2,2)...(3,1)...$ and such. From a computational perspective, this makes sense to me. Intuitively, not so much, since we are already dealing with infinites.

But the way my textbook does it, you have a diagonal of pairs, starting with $(1,1)$ that grows and as such all the rows get even "exposure". Is this reasoning correct?

Note, my textbook doesn't count 0 as a natural number.

$\endgroup$
3
  • $\begingroup$ You ask "is the enumeration strategy important?" What is important is that the enumeration strategy be explicitly defined, and that its definition be used to prove that what you have is, in fact, an enumeration. You are free to use other enumeration strategies, as long as you can prove what has to be proved. $\endgroup$
    – Lee Mosher
    Jul 5 '16 at 20:10
  • $\begingroup$ @LeeMosher: But suppose the strategy is to first lists all pairs (1, 1), (1, 2), (1, 3)... then (2, 1), (2, 2), (2, 3)... couldn't one argue that you would never reach (2, 1), (2, 2), ... because you are stucking listing the pairs (1, j) forever? I am probably deeply confused and wrong so the question is probably ill-posed :). $\endgroup$
    – Skurmedel
    Jul 5 '16 at 20:31
  • $\begingroup$ The trouble with that strategy is that it does not work, and you cannot prove what has to be proved, for pretty much the reasons you say. $\endgroup$
    – Lee Mosher
    Jul 5 '16 at 21:04
3
$\begingroup$

The important thing is that you can show that you will reach any given pair $(i,j)$ in a finite number of steps. This is what shows that you are counting all of the pairs (as opposed to leaving some out).

If all you did is show that there are countably many pairs of the form $(1,j)$ then you have only proved that there at least that many numbers in the rationals, not that at most there are that many.

$\endgroup$
3
  • $\begingroup$ Thanks, I guess your first paragraph is what I am trying to get at. The first strategy I had in mind was to list all pairs (1,j), then (2,j), but that wouldn't actually show that you could reach, say (3,5) in a finite amount of steps? $\endgroup$
    – Skurmedel
    Jul 5 '16 at 20:22
  • $\begingroup$ Exactly. It would take an infinite amount of steps to get there $\endgroup$
    – soandos
    Jul 5 '16 at 20:32
  • $\begingroup$ Thanks, then you have helped me :) $\endgroup$
    – Skurmedel
    Jul 5 '16 at 20:39
2
$\begingroup$

For the traditional bijection with the positive integers you only get one free trip to infinity. The bijection you proposed requires infinitely many trips to infinity. In set theory ordered mappings beyond infinity are associated with "ordinal" numbers.
Ordinal $\omega$ maps to {1 .. $\infty$}. The sequence {2 .. $\infty$, 1} would be $\omega+1$. The sequence {2, 4, 6, 8, .. $\infty$, 1, 3, 5, 7, $\infty$} makes two trips to infinity and is mapped to $\omega + \omega = 2\cdot\omega = 2\omega$. The mapping you described is represented by $\omega \cdot\omega = \omega^2$.

If you know that $\omega^2$ is countable then you've proved the rationals are countable. But that requires knowledge beyond a typical countability proof.

$\endgroup$
1
  • 2
    $\begingroup$ This is an important point provided with no explanation for the reader who may not be familiar with ordinals at all. If you explain what you're talking about and what you mean, this might be a very helpful answer. $\endgroup$
    – Mark S.
    Jul 13 '16 at 20:09
1
$\begingroup$

The specific enumeration isn't important - there are lots of others that would work equally well and have all the same properties as far as the set theory is concerned. What is important is that the enumeration given hits each rational at some finite stage. The enumeration you suggest only enumerates (2, 1) after infinitely many rationals have already been enumerated.

But you could easily use a "backwards" enumeration that does (1,2) before (2,1), or one that goes back to (3, 1) after (1, 2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.