Constructing a bijection from $\mathbb{N}$ to $\mathbb{Z}$ using primes and composites? Reviewing for an Into to Proofs final, came across the classic $f:\mathbb{N} \to \mathbb{Z}$ bijection problem in which
$f(x) = \begin{cases} 
      \displaystyle \frac{x}{2} &\mbox{if $x$ is even} \\
      -\displaystyle \frac{x+1}{2} &\mbox{if $x$ is odd}
\end{cases}$
My question is: can we establish a bijection $g: \mathbb{N} \to \mathbb{Z}$ in which we partition $\mathbb{N}$ into primes and composites, and then map the primes to the nonnegative integers and the composites to the negative integers?
I'm still trying to wrap my head around infinity, so I'm simply wondering if this is possible. To my naive self, it seems like there are more composites than there are primes, even though there are infinitely many of both (does that make sense?), so we'd map to the negative integers much more quickly than the nonnegative integers. Mapping evens and odds made sense to me because it seems like there are equally many even natural numbers compared to odd ones (even though there are infinitely many! I don't know why my brain does this).
Not looking for a construction or a proof or anything, just some insight and intuition.
 A: Yes, and the construction is quite easy.
Just enumerate all primes $p_1,p_2,...$ and all composites $c_1,c_2,...$ and then let 
$f(x) = \begin{cases} 
      \displaystyle i &\mbox{if  $x=p_i$} \\
      -\displaystyle j &\mbox{if $x=c_j$}\\
\displaystyle 0 &\mbox{if $x=1$}\\
\end{cases}$
To see that this is a bijection just take a prime or composite, and note that you may find something which it maps to, and this number is unique. (you may do this formally)
When it comes to infinity $\mathbb{N}$ (and any other set which is has a bijection to) is the smallest set possible. Thus if you take any infinite set which is a subset of $\mathbb{N} $ it will be the same size as $\mathbb{N} $ no matter how small it might look. We may even do things such as let $S$ be the set of each prime which has index $10^x$ for some $x$ when we enumerate the primes from smallest to largest, and $S$ will be the same size as $\mathbb{N} $. The trick is to understand that the finite property of "If $A\subsetneq B$ then $|A|<|B|$" does not hold at all for infinite sets. 
Also note that the rationals $\mathbb{Q}$ are the same size as $\mathbb{N} $ a construction which also is a bit tricky. The easy way to see it is that any set which we may "count up to" is the same size as $\mathbb{N} $.
A: Yes, that will work equally well -- any way to divide $\mathbb N$ into two infinite subset will work.
Since there are both infinitely many primes and infiyitely many composites, that's a valid split -- at least as long as you decide on putting $0$ and $1$ (which are neither prime nor composite) arbitrarily into one of the sets.
In order to prove that this works, the best way forwards would probably be start by proving

Lemma. Any infinite subset of $\mathbb N$ is in bijective correspondence with $\mathbb N$ itself.

Then use this lemma first on the set of primes and then on the set of composites, and negate the result for the composites.
The advantage of using odds and evens is just that it is particularly simple to write down the bijections between odds (or evens) and all of the natural numbers, such that you don't have to appeal to a general construction such as the lemma above.

In particular the lemma says that there are equally many primes as there are composites, at least if we accept that the existence of a bijection is a reasonable meaning to assign to the words "equally many" for infinite sets.
This way to use the words is commonly accepted in mathematics, but it does lead to results such as this that sound counterintuitive until you train yourself to know that "equally many" does not exactly mean the same thing here as your native intuition would expect.
An early instance of this is Galileo's paradox, which observes that according to the "bijection" definition there are as many perfect squares as there are integers, even though all perfect squares are integers and most integers are not perfect squares!
A: Of course we can. Both sets (primes and composites) are infinite and countable. 
But there is a little gap in all this: $1$ is natural but it is not prime or composite. You can map $1$ to $0$, primes to positive integers and composites to negative integers.
