Does a bijection $f:\textbf{Z}\rightarrow \textbf{Q}$ exist? In this case, as is usual, $\textbf{Z}$ represents the set of integers and $\textbf{Q}$ represents the set of rational numbers.
I'm meant to figure out if the bijection $f:\textbf{Z}\rightarrow\textbf{Q}$ exists and, while I know that this entails proving that it is both injective and surjective, I'm stuck with how to proceed.
I've been struggling with proving bijectivity for sets in general and what I'm looking for is a framework with which to work when it comes to these sorts of problems, as my attempts to research similar problems online haven't helped.
EDIT: While I do see other problems asking similar questions, the answers I read failed to show steps that proved both injectivity and surjectivity, which is how I would like to solve the question, if possible.
 A: It is enough to find a bijection between $\mathbb{N}$ and the set $\mathbb{Q} \cap (0, 1)$ of rational numbers lying inside the unit interval. Since after we have such a bijection $f: \mathbb{N} \to \mathbb{Q} \cap (0, 1)$, we could compose this bijection with the function $x \mapsto \frac{1}{x} - 1$, which "stretches" the unit interval $(0, 1)$ to the half-line $(0, \infty)$, giving us a bijection $g: \mathbb{N} \to \mathbb{Q} \cap (0, \infty)$. I'll leave it up to you as to how to get a bijection $h: \mathbb{Z} \to \mathbb{Q}$ once being given such a $g$.
So, how to construct this first function $f$? We simply make a big list of every rational number between 0 and 1, ordered first by their denominators, and then by their numerators. We make sure to only write the fraction $p/q$ down into this list as long as $p$ and $q$ have no common factors. The start of the list looks like this:
$$ \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{3}{4}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}, \frac{1}{6}, \frac{5}{6}, \frac{1}{7}, \cdots $$
and define $f(n)$ to be the $n$th fraction in this list. You need to show that $f: \mathbb{N} \to \mathbb{Q} \cap (0, 1)$ is both injective and surjective, and there are a bunch of ways of doing this. Injectivity should follow from the fact that a positive rational has a unique representation as $p/q$ for $p, q \in \mathbb{N}$ having no common factors. Surjectivity will rely on the fact that $p/q$ appears in this list after finitely many terms.
By the way, for an example of where surjectivity would fail, consider the "list" of fractions
$$ \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \ldots, \frac{2}{3}, \frac{2}{5}, \frac{2}{7}, \ldots, \frac{3}{4}, \frac{3}{5}, \ldots $$
This list still defines a map $f: \mathbb{N} \to \mathbb{Q} \cap (0, 1)$, but there is no $n \in \mathbb{N}$ such that $f(n) = \frac{2}{3}$, since we would have to write down infinitely many terms before $\frac{2}{3}$.
A: Consider the injection $f:\mathbb{Q}\hookrightarrow \mathbb{N}$ given by $f(0)=1$, $f(a/b)=3^a 5^b$ and by $f(-a/b)=13^a 17^b$, where in each case $a/b$ is an irreducible fraction, $a> 0$ and $b>0$.
The function $f$ induces a bijection between the image $f(\mathbb{Q})$ and $\mathbb{Q}$. Therefore, if we find a bijection between $f(\mathbb{Q})$ and $\mathbb{Z}$ we are done.
We can use the following useful theorem: Every infinite subset of the natural numbers has a bijection to the whole set of natural numbers. To prove this fact you can use the well-ordering principle. In particular, $f(\mathbb{Q})\subset \mathbb{N}$ is an infinite subset of natural numbers. 
Finally, you can choose your favorite bijection between $\mathbb{N}$ and $\mathbb{Z}$. Composing all these bijections you obtain the desired bijection between $\mathbb{Z}$ and $\mathbb{Q}$.
A: Yes.  Both are countable.   See pairing function .
One of the best ways to see it is to put the (positive) rationals into an array, and use a diagonally incrementing "snaking" function.  
The same technique can be used to show the countable union of countable sets is countable. 
