In my quest to learn elementary discrete mathematics I came across the proof mentioned here.

I started wondering about how to generate the pairs the way the informal proof does it; being used to linear algebra proofs heavy on sums.

I came up with the following not so pretty formula for the set of pairs: $$P=\bigcup_{n\in\mathbb{N}} \left( \bigcup_{i\leq n} (i, n - i + 1) \right)$$, which differs only slightly in the ordering for each diagonal.

Running it on a computer seems to lend credence to this, but will the definition given suffice to show that my $P = \mathbb{N}\times\mathbb{N}$?

  • $\begingroup$ What does $\mathbb{N} \times \mathbb{N}$ mean to you? And what does $|\mathbb{N} \times \mathbb{N}|$ mean to you? $\endgroup$ – Lee Mosher Jul 5 '16 at 20:19
  • $\begingroup$ @LeeMosher: Sorry, it is not the cardinality, I will change my answer, it is a typo. $\endgroup$ – Skurmedel Jul 5 '16 at 20:23
  • $\begingroup$ Did you try to calculate first 10 tuple for example? It simply draws a triangle in $\mathbb{N}\times \mathbb{N}$. $\endgroup$ – Levent Jul 5 '16 at 20:24

The way to prove it is to show that if I give you a pair $(a,b)$ you can find an $n$ and $i$ with $i \le n$ that corresponds. This gives $a=i, b=n-i+1$, which becomes $i=a, n=a+b-1$ As long as you don't think $0 \in \Bbb N$ this works fine. It shows that your $P$ includes all the ordered pairs. It may not do what you want, however, depending on what that is. You have shown a bijection between all pairs $(a,b)$ and pairs $(i,n)$ with $i \le n$. Often one wants a bijection between the pairs and the naturals, which you don't have.

  • $\begingroup$ Thank you, then my idea is not of much use :) But you cleared up my confusion somewhat; I for some reason thought constraining i to n would make i an "extension" of n, but it is obviously not true. If I would like to create a bijection from N to the pairs, I guess I'll have to rely solely on $n \in \mathbb{N}$ then? $\endgroup$ – Skurmedel Jul 8 '16 at 14:45
  • 1
    $\begingroup$ That is correct. You need just one parameter on the side that represents $\Bbb N$ and two on the side that represents $\Bbb N \times \Bbb N$. You can look up the Cantor pairing function to see the standard way to do it. $\endgroup$ – Ross Millikan Jul 8 '16 at 15:22

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.