Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set
Hint, do you know the argument for the countability of the rational numbers?  

Just enumerate every pair $a,b$ of natural numbers and output the $b$ if $P(a,b)$ is true.

Other way, can you construct a machine that given a $b$, answers YES if there is an $a$ such that $P(a,b)$ is true?