Intereting Posts

Inverse function of a polynomial and its derivative
$C \otimes A \cong C \otimes B$ does not imply $A \cong B$
Topological spaces as model-theoretic structures — definitions?
Why is this $0 = 1$ proof wrong?
Functions $f(x)/g(x), g(x)/h(x),h(x)/f(x)$ are constant
Prove that we always have $ 2n \mid \varphi(m^n+p^n) $
Maximal ideal/ Prime ideal
If $f=F'$ and $|f|$ is Riemann integrable, how to show that $f$ is Riemann integrable?
Applications of Gauss sums
If $G$ is a group and $N$ is a nontrivial normal subgroup, can $G/N \cong G$?
Proving $\sqrt{a+\sqrt{b}}=\sqrt{m}+\sqrt{n}\iff a^{2}-b$ is a square
Explicit example of countable transitive model of $\sf ZF$
Probability distribution for finding two values in stages
Properties of matrices changing with the parity of matrix dimension
Understanding the proof that $L_\infty$ norm is equal to $\max\{f(x_i)\}$

How would you prove the Cantor Pairing Function bijective? I only know how to prove a bijection by showing (1) If $f(x) = f(y)$, then $x=y$ and (2) There exists an $x$ such that $f(x) = y$

How would you show that for a function like the Cantor pairing function?

- Uncountable chains
- Show A is countable infinity
- For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$
- How can one rigorously determine the cardinality of an infinite dimensional vector space?
- The cardinality of a countable union of countable sets, without the axiom of choice
- Cardinal number subtraction

- Yablo's paradox? a paradox without self-reference
- Axiom of Choice: Can someone explain the fallacy in this reasoning?
- Cartesian product of large sets
- Does any uncountable set contain two disjoint uncountable sets?
- Why infinite cardinalities are not “dense”?
- What is a countable set?
- If A is an infinite set and B is at most countable set, prove that A and $A \cup B$ have the same cardinality
- Name for collection of sets whose intersection is empty but where sets are not necessarily pairwise disjoint
- Help with a proof. Countable sets.
- Do there exist bijections between the following sets?

It can be done exactly as you suggest: by proving (1) that if $\pi(m,n)=\pi(p,q)$, then $\langle m,n\rangle=\langle p,q\rangle$, and (2) that for each $m\in\mathbb{N}$ there is a pair $\langle p,q\rangle\in\mathbb{N}\times\mathbb{N}$ such that $\pi(p,q)=m$, where $$\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}:\langle m,n\rangle\mapsto \frac12(m+n)(m+n+1)+n$$ (where I’m using the version of the pairing function given in the Wikipedia article that you cite).

(1) Suppose that $\pi(m,n)=\pi(p,q)$, i.e., that $$\frac12(m+n)(m+n+1)+n=\frac12(p+q)(p+q+1)+q\;.\tag{1}$$ The first step is to show that $m+n=p+q$, so suppose not. We may as well assume that $m+n<p+q$. For convenience let $a=m+n$ and $d=(p+q)-a$, so that $(1)$ becomes $$\frac{a(a+1)}2+n=\frac{(a+d)(a+d+1)}2+q\;.$$

Then $$\begin{align*}

n-q&=\frac{(a+d)(a+d+1)}2-\frac{a(a+1)}2\\

&=ad+\frac{d(d+1)}2\\

&\ge a+1\;,

\end{align*}$$

so $n>a+q\ge a=m+n\ge n$, which is absurd. Thus, $m+n=p+q$, and $(1)$ immediately implies that $n=q$ and hence also $m=p$. This establishes that $\pi$ is injective.

(2) This is exactly the calculation given here. The article doesn’t prove (1) explicitly because in the process of uniquely reconstructing $\langle x,y\rangle$ from $z=\pi(x,y)$ it implicitly shows (1).

Claim: $f: (m,n) \mapsto n + \frac12 (m+n)(m+n+1)$ is bijective.

Proof: It’s enough to show that $f$ is invertible because if there is an inverse function $g$ then injectivity and surjectivity both directly follow from $f \circ g = \mathrm{id}$.

To invert $f$ we introduce the following variables:

$$ z = f(m,n) = n + \frac12 (m+n)(m+n+1)$$

$$ w = m + n$$

so that $z = n + \frac{w^2 + w}{2}$. Next we also introduce

$$ t = \frac{w^2 + w}{2}$$

It is not clear to me how we figured out what we introduce. But after we introduce $t$ and $w$ it is clear that $n = z -t$ and $m = w-n$ where $z$ is known so that if we can write $w$ and $t$ as functions of $z$ we are done.

We observer that from $t = \frac{w^2 + w}{2}$ we get $w^2 + w – 2t = 0$ from which we obtain $w = \frac{-1 \pm \sqrt{1 + 8t}}{2} $ and since $w \in \mathbb N$ it is clear that only $$w = \frac{-1 + \sqrt{1 + 8t}}{2}$$

is a solution. Now we have $w$ as a function of $t$. From this we can reach our goal of writing $w$ as a function of $z$. To this end, we introduce $h(t) = w = \frac{-1 + \sqrt{1 + 8t}}{2}$ and observe that $h$ is strictly increasing on $\mathbb R_{\geq 0}$ with $h^{-1}(\omega) = t = \frac{w^2 + w}{2}$.

Also, $t \leq t + n < t + w + 1$ which is the same as $\frac{w^2 + w}{2} \leq z < \frac{(w+1)^2 + (w+1)}{2}$. Which is the same as

$$ h^{-1}(w) \leq z < h^{-1}(w+1)$$

From which we get

$$ w \leq h(z) < w+1$$

which is the same as

$$ w \leq \frac{-1 + \sqrt{1 + 8z}}{2} < w + 1$$

Now we’re almost there. We know that $w \in \mathbb N$ hence $$ w = \left \lfloor \frac{-1 + \sqrt{1 + 8z}}{2} \right \rfloor$$

Now we have $w$ as a function of $z$ which is what we wanted. From this we get $n$ and $m$ (as functions of $z$).

I will denote the pairing function by $f$. We will show that pairs $(x,y)$ with a particular value of the sum $x+y$ is mapped bijectively to a certain interval, and then that the intervals for different value of the sum do not overlap, and that their union is everything.

Let $m$ be a natural number and suppose $m=x+y$. The least value that $f(x,y)$ can take is $\frac{m(m+1)}{2}$ (if $x=m$) and the largest value it can take is $\frac{m(m+1)}{2}+m$ (if $y=m$). It can also take all values in between. It is thus easy to see that the $m+1$ pairs $(x,y)$ with sum $m$ are mapped bijectively to an interval.

If $x+y=m+1$ then the least possible value of $f(x,y)$ is $\frac{(m+1)(m+2)}{2}$. We can check that $\frac{(m+1)(m+2)}{2} – (\frac{m(m+1)}{2}+m)=1$ so the intervals for the different value of the sum do not overlap and it is easy to see that their union is $\mathbb{N}$.

- Is there a name for a group having a normal subgroup for every divisor of the order?
- How to draw ellipse and circle tangent to each other?
- Non-Noetherian rings with an ideal not containing a product of prime ideals
- Closed form for $\sum_{n=1}^\infty\frac{(-1)^n n^4 H_n}{2^n}$
- Spectrum of Laplace operator with potential acting on $L^2(\mathbb R)$ is discrete
- Prove this : $\left(a\cos\alpha\right)^n + \left(b\sin\alpha\right)^n = p^n$
- Derivatives of the Riemann zeta function at $s=0$
- Deriving the sub-differential of the nuclear norm
- How do I prove the following result in number theory?
- Prove that $(x^2-x^3)(x^4-x) = \sqrt{5}$, where $x= \cos(2\pi/5)+i\sin(2\pi/5)$
- Line bundles of the circle
- Equivalent of the countable axiom of choice?
- Derivation of Gradshteyn and Ryzhik integral 3.876.1 (in question)
- continuous linear functional on a reflexive Banach space attains its norm
- If $p$ is an odd prime, does every Sylow $p$-subgroup contain an element not in any other Sylow $p$-subgroup?