Alternative proof that the rationals are countable Does anybody know of proof that the rationals are countable using an array that starts with
1/1
2/1    1/2
3/1  2/3  3/2  1/3   etc. where you generate from p/q the next two fractions to p+q/q  and p/p+q
Why are all the rationals in the array and why are they all in reduced form?
 A: 
why are they all in reduced form?

You only have 2 construction rules.  So to construct $a/b$ you can only come from $(a-b)/b$ or $a/(b-a)$ .  And since we are restricted to positive rationals, there really is only 1 place a rational can come from, depending on whether $a > b$.  So try constructing something like $2/2$ or $3/9$ by working backwards and you'll see why it is impossible.

Why are all the rationals in the array?

First figure out how to construct all the rationals of the form $a/1$ and $1/b$.  Then note that when you do a backwards transform like $a/b \leftarrow c/d$ (like $5/7 \leftarrow 5/2$) at least one number is made smaller, but not made into zero.  That gives you a proof by descent that every positive rational is constructed.
A: Define $f:\mathbb Q^+\to \mathbb Q_{\ge 0}$ as follows:
$$
f(x) = \begin{cases}
x-1 & x \ge 1 \\
\frac1{(1/x)-1} & 0<x<1
\end{cases}
$$

Lemma: For all $x\in \mathbb Q^+$, there exists $n\in \mathbb N$ such that $f^{(n)}(x)=1$, where $f^{(n)}$ denotes iterated composition. That is, $f^{(0)}(x)=x$, while $f^{(n+1)}(x)=f(f^{(n)}(x))$ for all $n\ge 0$.
Proof idea: Write $x=p/q$ in reduced form, and prove the statement by induction on $p+q$.

We have shown that for any rational number $x$, there is a chain
$$
x\longrightarrow  f^{(1)}(x) \longrightarrow f^{(2)}(x) \longrightarrow \dots \longrightarrow f^{(n)}(x)=1 \tag{$*$}
$$
Note that if $p$ and $q$ are coprime positive integers, then
$$
f\left(\frac{p+q}{q}\right)=\frac pq,\\
f\left(\frac{p}{p+q}\right)=\frac pq.
$$
Therefore, if follow the chain in $(*)$ in reverse, you get a way to produce starting from $1/1$, and at each step moving from $f^{(k+1)}(x)=p/q$ to either $(p+q)/q$ or $p/(p+q)$, depending on whether $f^{(k)}(x)$ is greater than $1$. That is, the two maps $(p/q)\mapsto (p+q)/q$ and $(p/q)\mapsto p/(p+q)$ generate all positive rational numbers, as desired.
