1

How to understand the words More algebraically

When seeing one proof about the theorem that rational set is countable, I saw this

More algebraically , but less clearly, an explicit one-to-one onto map

$f:N\times N\to N$

is

$f(m,n)=\frac{(n+m-2)(n+m-1)}{2}+m$.

so, why not more analytically? The concept of function is more algebraically?

Also, better to know about how to construct $f(m,n)$ and make it more clearly?

Community
  • 1
HyperGroups
  • 1,393

2 Answers2

4

It would help to know what is being contrasted with this more algebraic argument. I suspect, however, that it’s a pictorial argument similar to the one shown in this earlier question. If so, the author’s point is that while the picture makes it very clear that there is a bijection $f$ from $\Bbb N\times\Bbb N$ to $\Bbb N$ and would even let us calculate any $f(m,n)$ by drawing a big enough picture, it doesn’t actually give us an algebraic formula for $f(m,n)$.

Now he’s giving us that algebraic formula. It’s not terribly hard to prove that it’s a formula for the bijection of the pictorial argument. It’s also not hard to prove without any reference to the pictorial argument that this function really is a bijection from $\Bbb N\times\Bbb N$ to $\Bbb N$. But it would be hard to come up with that formula out of thin air. If he had just presented the formula and proved that it’s a bijection from $\Bbb N\times\Bbb N$ to $\Bbb N$, you might well have said, ‘Fine, I see that it works, but where on earth did it come from?!’

It’s more algebraic because it actually gives an algebraic expression for $f$; it’s less clear because you actually have to work a bit to prove that it’s a bijection from $\Bbb N\times\Bbb N$ to $\Bbb N$; the pictorial argument gives you an obvious bijection, even though it isn’t immediately obvious how to express it with an algebraic formula.

Community
  • 1
Brian M. Scott
  • 616,228
  • ah, yes, there is really one picture show the diagonalization.

    ---"Fine, I see that it works, but where on earth did it come from?!"

     – HyperGroups Jul 08 '13 at 07:28
  • @HyperGroups: You might not come up with the idea of counting off by diagonals, at least not right away, but I think that it’s still a good deal less mysterious than the formula. (Of course I first saw the idea about $55$ years ago, so I may not be the best judge of how natural it is!) – Brian M. Scott Jul 08 '13 at 07:36
  • Is there a gold badge here for "consistently quite outstandingly clear explanations -- models of how to do it"? Then @BrianM.Scott should get a handful! :-) – Peter Smith Jul 08 '13 at 08:40
1

One interpretation would be that they've provided an algebraic formula (i.e. an explicit formula involving only multiplication, division, etc) for the mapping in question, instead of simply proving that the mapping exists. One might say that proving something exists without explicitly constructing it, such as in the proof of counting the rationals, is a more "analytical" thing to do, since we're simply analyzing the problem instead of getting caught up in the symbols (the algebra) of it.

icurays1
  • 17,161