Cardinality of the set of all pairs of integers The set $S$ of all pairs of integers can be represented as $\{i \ | \ i \in \mathbb{Z} \} \times \{j\ | \ j \in \mathbb{Z}\}$. In other words, all coordinates on the cartesian plane where $x, y$ are integers.
I also know that a set is countable when $|S|\leq |\mathbb{N}^+|$. I attempted to map out a bijective function, $f : \mathbb{N}^+ \rightarrow S$.
$1 \rightarrow (1,1) \\
2 \rightarrow (1,2)\\
3 \rightarrow (1,3) \\
\quad \vdots
$
I determined from this that the natural numbers can only keep up with $(1,*)$. But there is the ordered pairs where $x=2,3,4,\cdots$ not to mention the negative integers. In other words, $|S|\geq |\mathbb{N}^+|$ and therefore $S$ is not countably infinite.
Is this correct? (I don't think it is... Something to do with my understanding of infinite sets)
 A: Natural Numbers: There are many pairing functions that map $\mathbb{N}\times \mathbb{N}$ bijectively to $\mathbb{N}$. A simple example is the mapping $f$ such that $f(a,b)=2^{a-1}(2b-1)$.  For every positive integer $y$ can be uniquely expressed as a power of $2$ times an odd integer. 
Integers: If you want a mapping $g(x,y)$ that maps $\mathbb{Z}\times \mathbb{Z}$ bijectively to $\mathbb{N}$, it is simplest to split the work into two parts. 
Let $\phi$ be any mapping that maps $\mathbb{Z}$ bijectively to $\mathbb{N}$.  For a concrete example of such a mapping, let $\phi(t)=2t+2$ if $t \ge 0$, and let $\phi(t)=-(2t+1)$ if $t \lt 0$. The non-negative integers are sent to the even integers $\ge 2$, and the negative integers are sent to the positive odd integers. 
Then the mapping $g(x,y)=f(\phi(x),\phi(y))$ works, where $f$ is any bijective map from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$. For example, we can use the mapping $f$ of the first paragraph, or the Cantor pairing function. 
Remark: For most purposes, there is no particular virtue in having an explicit bijection, as long as we can prove that a bijection exists. 
A: You simply haven’t yet found a function that works. One that does is the Cantor pairing function, which is described quite well in the Wikipedia article to which I linked.
A: Many different (correct) approaches were already explained in other answers.
Another approach, often used in computer programs (for various reasons), is to enumerate ever bigger finite sets, with some kind of natural enumeration within them. For example, visualize the plane as a set of concentric squares, and enumerate the differences between squares (the square "corridors" of width one). The first will contain only one pair $(0, 0)$, the second - 8 pairs around it, etc. Your overall enumeration basically runs ever bigger circles around the origin, except the circles are squares. It is actually not that different from Cantor's pairing, but may be easier to visualize for all four quadrants.
A: Define $\sigma: \Bbb Z \times \Bbb Z \to  \Bbb Z \times \Bbb Z$ by
$$   
    \sigma(m,n) = \left\{\begin{array}{lr}
        (1,-1), & \text{for } (m,n) = (0,0)\\
        (m, n+1), & \text{for } m \gt 0 \, \land \, -m \le n \lt m\\
        (m-1, n), & \text{for } n \gt 0 \, \land \, -n \lt m \le n\\
        (m, n-1), & \text{for } m \lt 0 \, \land \, m \lt n \le -m\\
        (m+1, n), & \text{for } n \lt 0 \, \land \, n \le m \lt -n-1\\
        (m+2,n-1), & \text{for } n \lt 0 \, \land \, m = -n-1
        \end{array}\right\} 
$$
Exercise: Show that $n \mapsto \sigma^n(0,0)$ is a bijective mapping between $\{0,1,2,3,...\}$ and $\Bbb Z \times\Bbb Z$.
