Find an explicit surjection $f : \mathbb{Z_+} \to \mathbb{Z_+} \times \mathbb{Z_+}$ 
Find an explicit surjection $f : \mathbb{Z_+} \to \mathbb{Z_+} \times \mathbb{Z_+}$

I was recently posed this question by a fellow Math.SE user on the main chat room, and I had two ideas.

Idea 1 (Which I think is incorrect)
Define $f$ such that $f(x) = ((x, i))_{i \in \mathbb{Z_+}}$
The idea here was to define a function for a specific $x \in \mathbb{Z_+}$ and have the function range over all $i \in \mathbb{Z_+}$, which as I thought would define a surjective function from $\mathbb{Z_+}$ to $\mathbb{Z_+} \times \mathbb{Z_+}$

Idea 2
Define $f$ such that $f(x) = ((x, y))_{y\ \leq \ x}$ and $y \in \mathbb{Z_+}$. The idea here, was to use a sort of diagonolisation argument to define a surjective function.
In this case $f(3) = \{(3, 0), (3, 1), (3, 2), (3, 3)\}$ (or at least that's what I'm hoping the function would produce)

Are either of the functions I defined surjective? Are they even correct? The notation I had used bugged me a bit, and I'm not even sure if I've defined (or even it's possible to define functions this way) correctly.
 A: Just to be clear, a function $f : \mathbb{Z_+} \to \mathbb{Z_+}\!\! \times \mathbb{Z_+}$ takes a number $n$ and outputs a pair $f(n)=(a,b)$.
Your functions (and in particular the second one) does not output a pair of numbers, but rather a set of pairs! Thus it isn't even a function with the right codomain.
One quite standard idea you could try is drawing the codomain $\mathbb{Z_+}\!\! \times \mathbb{Z_+}$ as a grid and trying to come up with some way to enumerate the nodes/points in the grid.
A: I like this method of creating a surjection because it can be easily extended to tuples of arbitrary size. Define $ g : \mathbb{Z}_+ \times \mathbb{Z}_+ \to \mathbb{Z}_+  $.$$ g(a,b) = 2^a3^b$$
Then we can define $$f(n) = \begin{cases} 
(a,b) \text{ such that } g(a,b) = n & \text{if } \exists g(a,b) = n \\ 
(1,1) & \text{ otherwise} \end{cases}$$
A: Here is another idea. First we partition $\mathbb Z^+\times\mathbb Z^+$ as follows:
$$S_1=\{(1,1)\} \\ S_2=\{(1,2),(2,2),(2,1)\} \\ S_3=\{(1,3),(2,3),(3,3),(3,2),(3,1)\} \\ \vdots \\ S_k=\{(1,k),\ldots,(k,k),(k,k-1),\ldots,(k,1)\} \\ \vdots$$
The idea is to map $1$ to $(1,1)$, $2,3,4$ to the elements of $S_2$, $5,\ldots,9$ to the elements of $S_3$, and so on.
Notice that this will map $1^2$ to $(1,1)$, $2^2$ to $(2,1)$, $3^2$ to $(3,1)$, and so on. Also, $1$ maps to $(1,1)$, $3$ to $(2,2)$, $7$ to $(3,3)$; in general $k^2-k+1$ to $(k,k)$. Thus, given $n\in\mathbb Z^+$, let $k\in\mathbb Z^+$ be such that $(k-1)^2 < n\le k^2$; then
$$f(n)\ =\ \begin{cases}(n-(k-1)^2,k) & \text{if} & (k-1)^2<n\le k^2-k+1 \\\\ (k,k^2-n+1) & \text{if} & k^2-k+1<n\le k^2\end{cases}$$
In either case $f(n)\in S_k$. $f$ is a bijection and therefore a surjection.
A: Others pointed out problems in your solution, but let me provide a simple alternative: Notice that every $n \in \mathbb{Z_+}$ can be uniquely written in a form $n=2^{a-1}(2b-1)$ for $a,b \in \mathbb{Z_+}$, so we can map $n$ to $(a,b)$, which gives us a bijection. So we have $1 \to (1,1)$, $2\to (2,1)$, $3\to (1,2), \dots$ and so on.
A: $$\newcommand{\<}{<_{\text{new}}}$$
An element of $\mathbb Z^+\times\mathbb Z^+$ is a tuple of the form $(a,b)$, where each $a,b\in\mathbb Z^+$.  You gave a function from $\mathbb Z^+$ to sets of tuples, so the power set of $\mathbb Z^+\times\mathbb Z^+$.
Note that I'll be interpreting $\mathbb Z^+$ as $\mathbb Z_{\geq 1}$.  If you mean $\mathbb Z_{\geq 0}$, this only requires slight modifications to the general concept.
Instead of finding an explicit surjection, I'll give an ordering of the elements of $\mathbb Z^+\times\mathbb Z^+$.  This is actually enough to give an explicit surjection, but I find it easier to work with.
First, let the $d$th diagonal of $\mathbb Z^+\times\mathbb Z^+$ be all elements $(a,b)$ such that $a+b = d$.  So, the $4$ diagonal contains $(3,1),(2,2),(1,3)$.
Now, given any two elements $(a_1,b_1),(a_2,b_2)$, we'll say that $(a_1,b_1)\<(a_2,b_2)$ if $a_1+b_1<a_2+b_2$ (so, an element is less than another element if it's part of a smaller diagonal).  This compares tons of different numbers, but isn't yet complete (which is bigger, $(3,1)$ or $(2,2)$?).
To address this, we'll change the ordering the following way.  We now say that $(a_1,b_1)\<(a_2,b_2)$ if either of the following hold:


*

*$a_1+b_1<a_2+b_2$

*$a_1+b_1 = a_2+b_2$ and $b_1<b_2$
This second condition is essentially saying "if two elements are in the same diagonal, pick the one farther to the top left as being "smaller").
You should be able to convince yourself that under this definition, we always have that either $(a_1,a_2)\<(a_2,b_2)$, $(a_2,b_2)\<(a_1,b_1)$, or we have that $(a_1,b_1) = (a_2,b_2)$.
This defines something called a total order on $\mathbb Z^+\times\mathbb Z^+$ (sort of, I'd actually have to go through with non-strict inequalities to formally do that, but it's very easily doable).
A total order on a set $S$ essentially means that, given any two elements $u,v\in S$, we have that either $u<v$, $v<u$, or $v = u$ (what we convinced ourselves of before).
Now, because this defines a total order, if we say that $(1,1)$ is the smallest element of $\mathbb Z^+\times\mathbb Z^+$, it follows that $(2,1)$ is the second smallest element, $(1,2)$ is the third smallest, etc.  Now, define $f(t):\mathbb Z^+\to\mathbb Z^+\times\mathbb Z^+$ as $t$ goes to the $t$th smallest element under $\<$.  This is a surjection.
Note that this works, but if we defined a different total order (where $(1,x)<(2,x)<(3,x)$, and $(1,x)<(1,y)$ if $x<y$), we'd run into issues. The reason for this is that under the total order I defined, any $(a,b)$ has finitely many elements smaller than it.  This isn't true for the one defined earlier in this paragraph.  
As we have that each element only has finitely many elements smaller than it, we can figure out that each element is the $t$th smallest element for some finite $t$, and thus if $u$ is the $t$th smallest element, then $f(t)= u$.  We can do this for any element $u$, so $f$ is a surjection.
A: One way to do this, is to consider the sum of the components of an element in $\mathbb{Z}^+ \times \mathbb{Z}^+$. 
The elements whose components sum to $2$ are: $(1,1)$;
The elements whose components sum to $3$ are: $(1,2),(2,1)$;
The elements whose components sum to $4$ are: $(1,3),(2,2),(3,1)$;
The elements whose components sum to $5$ are: $(1,4),(2,3),(3,2),(4,1)$;
...
So we could try to map $1$ to $(1,1)$, $2$ to $(1,2)$, $3$ to $(2,1)$, $4$ to $(1,3)$, etc. An explicit map for this is given by (after long, boring, painful calculations):
$$\begin{align}f: \mathbb{Z}^+ \to \mathbb{Z}^+ \times \mathbb{Z}^+: n \mapsto &\; (n - \frac{1}{2}\left\lfloor\frac{\sqrt{8n-7}-1}{2}\right\rfloor^2 -  \frac{1}{2}\left\lfloor\frac{\sqrt{8n-7}-1}{2}\right\rfloor,\\&\;\;\;\; 2 - n + \frac{1}{2}\left\lfloor\frac{\sqrt{8n-7}-1}{2}\right\rfloor^2 +  \frac{3}{2}\left\lfloor\frac{\sqrt{8n-7}-1}{2}\right\rfloor)\end{align}$$
Note: I'd definitely not recommend doing this calculation, however, it is an "explicit" surjection as required.
