This is an oddly worded problem. For one thing any infinite subset of a denumerable set is denumerable.

As for the construction, any equivalence relation on a set defines a partition of the set.

So if you can define an equivalence relation on with a denumerable collection of infinite equivalence classes that will also do for your set.

Here is a suggestion.

Two positive integers are related if they are powers of the same prime or neither is a power of a prime.

Examples: .

Can you prove that is an equivalence relation?