So I understand that there are infinitely many non-prime natural numbers, and infinitely many prime natural numbers. I am able to show that there are an infinite number of non-prime natural numbers, but I don't know how to show that the entire set of non-prime natural numbers is infinite.
Consider the set $S=\{{p\in\mathbb{N}\space |\space p\space is\space prime}\}$
Assuming we already know that this set is infinite, consider the set $T=\{q\in\mathbb{N}\space|\space q=2p, where\space p\space is\space prime\}$
$T$ is then also an infinite set since it is contained in the set of all non-prime natural numbers
Thus there are an infinite number of non-prime naturals.
But how do I show that the entire set of non-prime naturals is infinite? Is it as easy as saying that it is a subset of the naturals and since the set of naturals is infinite, this set must also be infinite?
Best Answer
It looks like there's some confusion over the basic definitions here.
These are the same thing: "has infinitely many elements" and "is infinite" are just two ways of phrasing the same property.
This makes me think that you might be conflating "is infinite" with "is countable." It's certainly not true that every subset of the naturals is infinite, but it is true that every subset of the naturals is countable (or finite - some texts define "countable" as "in bijection with $\mathbb{N}$" as opposed to "in bijection with some subset of $\mathbb{N}$).
So if the problem you're trying to solve is "Show that the set of composite numbers is countable and infinite, then you've more-or-less outlined it:
It's a subset of $\mathbb{N}$, so trivially countable (in the broader sense of allowing finiteness).
The argument you give in the OP shows that it's infinite.