25
$\begingroup$

The standard proof that $|\mathbb{Q}| = \mathbb{|N|}$ is pictorial. I am sure everyone here has seen it. The "zig-zag". I must admit, however, that, although I was "intuitively" convinced by it, I was never entirely satisfied with it because it is not an explicit bijection $f:\mathbb{N} \to \mathbb{Q}$ given by an actual formula. The fact that the proof is correct seems "clear" to us, but this is, again, merely an appeal to intuition. One should note that some of these "proofs by picture" are simply incorrect: see Russell O'Connor's answer here .

I have two questions

Is the pictorial proof that $|\mathbb{Q}| = \mathbb{|N|}$ rigorous by the standards of modern pure mathematics?

For the sake of this question, suppose that there isn't an explicit formla, or that it's too unwieldy to use in practice. After all, even if there is a formula, most of the people who've seen the pictorial argument do not know of it.

Is there an explicit formula for the "pictorial" proof?

There's some minor issues, of course, namely the inclusion of $0$ and variations of the "zig-zag" path, but these are no big deal. A bijection $f:\mathbb{N} \to \mathbb{N} \times \mathbb{N}$ suffices; dealing with negatives, equivalent fractions, etc is trivial.

$\endgroup$
10
  • $\begingroup$ The zig-zag proof is not pictorial. You can represent it in a graph, as any function, this is all. $\endgroup$
    – Masacroso
    Aug 6, 2016 at 6:52
  • 5
    $\begingroup$ Yes, there is an explicit function for the bijection. But it's tedious, looks convuluted and it distracts from the purpose of the argument which should be simple. For n,m find the largest $\sum_{i=1}^k = k (k+1)/2 \le n+m $ then (n,m) -> k (k+1)/2 + (n-k) is the bijection. $\endgroup$
    – fleablood
    Aug 6, 2016 at 6:56
  • 1
    $\begingroup$ That should be sum < n; not <= n+m. It helps to draw a picture but: 1 => 0,0 then 2-3 => (1,0) - (0,1) and so on till $(\sum )+1$ = k (k+1)/2 +1 through $\sum $ + (k+1) maps to (k,0), (k-1,1), (k-2,2).... (0,k). That's the bijection. But it's tedious and not particularly relevant. $\endgroup$
    – fleablood
    Aug 6, 2016 at 7:21
  • $\begingroup$ Perhaps the easiest way is to let $a_k = \sum_{i=1} i $, then it's easy to show ever natural $n $ can be written uniquely as $a_k + i; 0 \le i < k+1$ so $n \rightarrow (k -1,i) $ is 1 to 1. $\endgroup$
    – fleablood
    Aug 6, 2016 at 7:36
  • 1
    $\begingroup$ A pictorial proof isn't rigorous enough but a formulaic calculation isn't nescessary if a descriptive argument can be shown to be unambiguous and consistsnt. The diagonal description as usually presented is ... borderline IMO. But if we explain we can count and group the naturals in groups each group with one more than the previous, i.e. (1)(2,3)(4,5,6)(7,8,9,10)etc. then each group has the same number of members as each of the diagonals that also increases by one, that could be rigorous enough. $\endgroup$
    – fleablood
    Aug 6, 2016 at 7:56

7 Answers 7

21
$\begingroup$

I had the same question with the same proof (the zig-zag proof you are mentioning). At some point I decided to produce a formal proof.

Define a bijective function $f\colon \mathbb N \times \mathbb N \to \mathbb N$.

First of all you notice that going zig and then zag only helps intuition. In fact you don't need a "continuous" curve, so it is easier to go zig and the zig again... (so to speak). Then it is easy to count how many points you need to fill the first $k$ diagonals (sum of a arithmetic series: $k(k+1)/2$). The couple $(n,m)$ lies on the diagonal number $k=n+m$ so you easily find: $$ f(n,m) = \frac{(n+m)(n+m+1)}{2} + m = \frac{n^2+m^2+2nm+3m+n}{2}. $$

This was a little bit shocking to me! The function I was looking for is as simple as a polynomial... I would have expected some modulus, or some strange discontinuous function.

Nevertheless the algebraic proof that $f$ is bijective is not so simple... but following the intuition of the construction it is easy to write it.

What can we learn from this? The pictorial proof is for sure the best to understand a result and to remember it. Then it might happen that the abstract mathematics is even simpler than our intuition. Not always simple mathematics corresponds to simple pictures.

$\endgroup$
2
  • 2
    $\begingroup$ However it's not necessary to come up with an explicit formula to prove the function is a bijection. E.g., an iterative or recursive description can suffice, and this is basically what the zig-zag picture does. $\endgroup$
    – Kimball
    Aug 6, 2016 at 11:01
  • 1
    $\begingroup$ @Kinball, it suffices provided it suffices. Having a fórmula makes it easy to be sure. $\endgroup$ Aug 6, 2016 at 19:46
7
$\begingroup$

I suppose if you really wanted to, you could come up with an explicit bijection associated with the "zig-zag" proof. If that turns out to be difficult, you could come up with a different "zig-zag" that may have a simpler bijection. Although, the "zig-zag" proof is really just providing some intuitive backing to this theorem:

The union of a countable number of finite sets is countable.

Thinking of each diagonal of the "zig-zag" as one of your finite sets, and noting that every rational number has to be in one of those diagonals is sufficient to prove that $|\mathbb{Q}| = |\mathbb{N}|$.


On a more general note, the whole point of a proof is to clearly and correctly convey why a theorem is true. Sometimes it is easiest to convey why through written words, especially when the proof is long, relies on lemmas or the theorems of others, or just has lots of cases. But if there is a clever reason why a theorem is true, some clever "ah-HA" that you just have to see, a "proof by picture" can be much more clear than a formal write-up of a proof. The hope is, though, that after a reader sees a pictorial proof, they should have enough intuition into why the theorem is true to write up a formal proof if they really needed.

After seeing the "zig-zag" proof, do you think you can prove that the union of a countable number of finite sets is countable?

$\endgroup$
4
  • $\begingroup$ What about a zig-zag proof that the union of a countable number of countable sets is countable? =P $\endgroup$
    – user21820
    Aug 6, 2016 at 10:28
  • $\begingroup$ @user21820, Every time I've heard the zig-zag proof it is presented as partitioning the rational numbers into finite sets indexed by the sum of their numerator and denominator. But I suppose you can think of them as being infinite sets (indexed by just the numerator or denominator), and that makes sense with the same picture. So I suppose that in this case, the same pictorial proof can inspire distinct formal proofs. :) $\endgroup$ Aug 6, 2016 at 22:23
  • $\begingroup$ Well I was trying to poke fun at the rigour of such a pictorial proof because it easily makes one think that it works the same for the union of countably many countable sets. It doesn't quite because you need the axiom of countable choice. Personally I like annotating parts of a diagram with quantifiers labelled by the order of quantification, and it would prevent such an error because we would realize that we need $\exists_1,\exists_2,...$. $\endgroup$
    – user21820
    Aug 7, 2016 at 8:40
  • 3
    $\begingroup$ @user21820,Mike Actually you need the axiom of countable choice even to prove that the union of countably many finite sets is countable. Is it obvious where countable choice comes in in the pictorial proof? It's in the picture-making itself: you need to place dots on the page, which entails a choice of ordering for the set which is relevant to the "zig"; and such a choice must be made independently for each of the countably many finite sets. Countable choice is not needed for $|\Bbb N|=|\Bbb Q|$ because the ordering is known in advance. (And this is why I don't like pictorial "proofs".) $\endgroup$ Aug 9, 2016 at 18:50
4
$\begingroup$

Munkres' "Topology" gives both the zig-zag intuition, and the actual formula for the bijection, as a good reference.

I read in an article (cannot remember the author, sadly) that proofs are not supposed to be 'entirely' rigorous. 'Proofs' try to convince the reader that it is possible to construct a completely rigorous proof. As in this case, although I too was not satisfied with the zig-zag-proof, it conveys the idea that the bijection does exists (without explicitly writing it out), and thus it is countable.

$\endgroup$
3
$\begingroup$

The point of something like the zig-zag proof is not to be rigorous in itself but instead to convince a mathematician that he or she could easily make the proof rigorous if pressed to do so by the gods of rigour.

Also, you can come up with very succinct surjections from N to Q. For example, map every natural number of the form $2^p 3^q 5^r $ to $(-1)^r p/q$. It's extremely easy now to see that if you give me a rational, there is a natural number which is mapped to it.

The downside with this is that if you are teaching countability you would need to check that "surjection from" is the same as "bijection with", which sometimes hasn't been proved by this stage.

$\endgroup$
2
  • $\begingroup$ Except that "surjection from" is not the same as "bijection with". To wit, your function is one but not the other. You can use it as a step in the way to proving a bijection, but that is hardly "the same as". $\endgroup$ Aug 7, 2016 at 10:03
  • $\begingroup$ Well of course I don't mean all surjections are bijections? For an infinite set $S$, the existence of a surjection $g : \mathbb{N} \to S$ is equivalent to the existence of a bijection betwwen $S$ and $\mathbb{N}$. $\endgroup$
    – Thompson
    Aug 7, 2016 at 16:57
1
$\begingroup$

Pictures have their strengths and weaknesses, but they're just as rigorous as any other informal type of proof — that is, they may or may not be depending on how well written it is.

And the zig-zag proof is a rather clear depiction of an explicit algorithm for enumerating the rationals.

Regarding your particular doubts, I don't think it's really the picture that's the issue — it's that the function was defined by an algorithm for producing its values, rather than as an arithmetic formula.

Formal proofs can be 'pictures' too; you can develop formal logic in a way where the basic 'data type' is something other than strings of symbols. e.g. graphs of various sorts are often useful.

$\endgroup$
1
$\begingroup$

This doesn't directly address the proof of $|\mathbb{N}|=|\mathbb{Q}|$, but the more abstract notion of pictorial proofs as found in elementary geometry:

Avigad, Dean & Mumma A Formal System for Euclid's Elements: http://repository.cmu.edu/philosophy/61/

They show that certain types of pictorial arguments that occur in Euclid's Elements, while apparently un-rigorous, can be described in a precise manner using formal rules, in a way that the conclusion follows directly from the pictorial "special case". In essence, a particular diagram can be in "general enough position" to allow rigorous conclusions to be drawn from it.

$\endgroup$
0
$\begingroup$

So... take the ordered pair $(n,m) $.

The pictorial and non rigorous concept of the "diagonal" is simply {$(j,k) | j+k=n+m; j\ge 0;k \ge 0$}. Note: there are $(n+m)+1$ terms in this diagonal

The previous diagonals had 1 term, two terms ... so on to $(n+m)$ terms. So the previous diagonals account for $\sum_{i=1}^{n+m} i = \frac {(n+m)(n+m+1)}{2} $ items.

Starting at $(0,n+m) $ end of the diagonal $(n,m) $ is the $n +1$th item of the current diagonal.

So the bijection you want is $(n,m)\rightarrow \frac {(n+m)(n+m+1)}2 + n $.

$(0,0)\implies 0$

$(0,1)\implies 1$

$(1,0) \implies 2$

$(2,0) \implies 3$

$(1,1)\implies 4$

Etc. Algebraically it's probably easy to show this is injective . Suppose (a,b) and (c,d) both map to t.

Case 1: a+b = c+d= K.

Then $\frac {K (K+1)}{2} + a = \frac {K (K+1)}2 + b$. So $a = c $. So $b = c =K -a $.

Case 2: Wolog a+b < c+d

$\frac {(a+b)(a+b+1)}2 + a \le \frac {(a+b)(a+b+1)}2 + (a+b)$

$=\frac {(a+b)(a+b+3)}2 $

$\le \frac {((c+d)-1)((c+d+1)+1)}2$

$=\frac {(c+d)(c+d +1) +(c+d) -(c+d+1)-1}2 $

$=\frac{(c+d)(c+d+1)}2 -1$

$< \frac{(c+d)(c+d+1)}2 + c $

Which is a contradiction.

So (a,b)=(c,d).

Proving it's surjective isn't nescessary though it is.

For each t there exist, k, so that $\frac {k (k+1)}2 \le t < \frac{(k+1)(k+2)}2$.

Let $n = t -\frac {k (k+1)}2 \ge 0$. Let $m=k-n = k - t + \frac {k (k+1)}2 > k - \frac {(k+1)(k+2)}2 + \frac {k (k+1)}2=k +\frac {k+1}2 (k-(k+2))=k - (k+1)=-1$. So $m \ge 0$

Then $(n,m)\rightarrow t$.

===

Anyway....

I don't think such an intensive arithmetic is nescessary. What matters is the argument that it can be done. As the diagonals increase by one each iteration, and as we can group the natural numbers into sequences of groups each increasing in terms by one, each group of natural numbers coresponds to a diagonal, and each of there natural numbers in the group corresponds to a term in the diagonal. Thus must be shown but it needn't be shown by convoluted arithmetic.

$\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.