# How can I prove or disprove that this formula gives me all the pairs in $\mathbb{N}\times\mathbb{N}$

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}$?

• What does $\mathbb{N} \times \mathbb{N}$ mean to you? And what does $|\mathbb{N} \times \mathbb{N}|$ mean to you? – Lee Mosher Jul 5 '16 at 20:19
• @LeeMosher: Sorry, it is not the cardinality, I will change my answer, it is a typo. – Skurmedel Jul 5 '16 at 20:23
• Did you try to calculate first 10 tuple for example? It simply draws a triangle in $\mathbb{N}\times \mathbb{N}$. – 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.
• 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? – Skurmedel Jul 8 '16 at 14:45
• 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. – Ross Millikan Jul 8 '16 at 15:22